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:
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:
Finding all connected components in a graph G.
Finding all nodes within an individual connected component.
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:
Finding a path between 2 specified nodes, u and v of an weighted as well as unweighted graph.
Finding whether a graph is connected or not.
Computing the spanning tree of a connected graph.
and 4 others joined a min ago.
teamques10
★ 68k
pedsangini276
• 4.8k
