• A splay tree is a self balancing binary search tree with an additional property that recently accessed elements can be re-accessed fast.

• It is said to be an efficient binary tree because it performs basic operations such as insertion, search and deletion operations in o (log n) amortized time.

• when a node in a splay tree is accessed it is rotated or 'splayed' to the root, thereby changing the structure of the tree.

• since the most frequently accessed node is always more closer to the starting point of the search, there nodes are therefore located faster.

• A simple idea behind it is that if an elements is accessed, it is likely that it will be accessed again.

• In a splay tree, operations such as insert, search, delete are combined with one basic operation called splaying.

Operations on a splay tree:

1] Splaying:

• when we access a node N, splaying is performed on N to move it to the root.

• To perform a splay operation, certain splay steps are performed where each step moves N closer to the root.

2] Insertion:

• Following are different steps to insert a new node N in a splay tree.

or Step 1 : Search N in a splay tree, if the search is successful, splay at the node N.

Step 2 : If the search is unsuccessful, add the new node N in such a way that it replaces the NULL pointer reached during the search try a pointer to new node No splay the tree at N.

3] Delete :

• To delete a node N from a splay tree, we perform following steps:

Step 1: Search for N that has to be deleted, if the search is unsuccessful, splay the tree at the last non-null node encountered during search.

Step 2 : If the search is successful and N is not the root node, then let P be the parent of N, replace N by its appropriate descendant of P, finally splay the tree at P.

Trie:

• In computer science, a trie, also called digital trie and sometimes rad ix tree or prefix tree, is a kind of search tree an addressed tree data structure that is used to store a dynamic set or associative array where the keys are usually string.

• Unlike a binary search tree, no node in the tree stored the key associated with node, unseated its position in the tree defines the key with which it is associated.

• All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.

• Values are not necessarily associated with every node , rather, values find only to be associated with leaves and with some inner nodes that correspond to keys of interest.

• In the example shown, keys are listed in the nodes and values below them, each complete English word has a arbitrary integer value associated with it.

b. Graph traversal techniques:

• By traversing a graphs we mean the method of examining the nodes and edges of the graph.

• There are 2 standard method of graph traversal and they are:

A. Breadth first search:

• It is a graph search algorithm that begins at the root node and explores all the neighboring nodes.

• Then for each of those request nodes the algorithm explores their unexplored neighbor nodes and so on, until it finds the goal.

• That is, we start examining node A, and all its neighbors of A are examined in the next step, we examine the neighbors of neighbors of A, so on and so forth.

Algorithm:

Step 1: Set status = 1 (ready state) for each node in G.

Step 2 : queue the starting node A and set its status = 2 (waiting state).

Step 3 : Repeat step 4 and 5 until queue is empty.

Step 4 : De-queue a node N, process it and set its status = 3 (processed state)

Step 5 : En-queue all the neighbors of N that are in the ready state (where status = 1) and set their status = 2 (waiting state)

Step 6 : Stop.

Application:

1. Finding all connected components in a graph G.

2. Finding all nodes within an individual connected component.

3. Finding the shortest path between 2 nodes, u and v for an weighted as well as unweighted graph.

B. Depth first search.

• The depth first search algorithm progresses by expanding the starting node of G and thus going deeper and deeper until a goal node is found, or until a node that has no children is encountered.

• When a dead end is reached, the algorithm back? returning to the most recent node that has not been completely explored.

• Dfs beings at a starting node A which becomes the current node, then it examines each node N along a path p which begins at A.

• That is, we process a neighbor of A, then a neighbor of neighbor of A and so on.

• During the execution of the algorithm, if we reach a path that has a node N that has already been processed, then we backpack to the current node, otherwise, we un visited node becomes the current node.

Algorithm:

Step 1: Set status = 1 (ready state) for each node in graph G.

Step 2: Push the starting node A on the stack and set its status = 2 (waiting state)

Step 3: Repeat step 4 and 5 until stack is empty.

Step 4 : Pop the top node N. process it and set its status = 3 (processed state)

Step 5: Push on to the stack all the neighbor of N that are in ready state (which status = D and set their status = 2 (waiting state)

Step 6 : Stop.

Applications:

1. Finding a path between 2 specified nodes, u and v of an weighted as well as unweighted graph.

2. Finding whether a graph is connected or not.

3. Computing the spanning tree of a connected graph.