Next: 4.6 Amortized Algorithm Analysis Up: 4.5 Splay Trees Previous: 4.5 Splay Trees

## 4.5.1 Search, Insert, Delete in Bottom-up Splaying

Search (i, t)

If item i is in tree t, return a pointer to the node containing i; otherwise return a pointer to the null node.

• Search down the root of t, looking for i
• If the search is successful and we reach a node x containing i, we complete the search by splaying at x and returning a pointer to x
• If the search is unsuccessful, i.e., we reach the null node, we splay at the last non-null node reached during the search and return a pointer to null.
• If the tree is empty, we omit any splaying operation.

Example of an unsuccessful search: See Figure 4.23.

Insert (i, t)

• Search for i. If the search is successful then splay at the node containing i.
• If the search is unsuccessful, replace the pointer to null reached during the search by a pointer to a new node x to contain i and splay the tree at x

For an example, See Figure 4.24.

Delete (i, t)

• Search for i. If the search is unsuccessful, splay at the last non-null node encountered during search.
• If the search is successful, let x be the node containing i. Assume x is not the root and let y be the parent of x. Replace x by an appropriate descendent of y in the usual fashion and then splay at y.

For an example, see Figure 4.25.

Next: 4.6 Amortized Algorithm Analysis Up: 4.5 Splay Trees Previous: 4.5 Splay Trees
eEL,CSA_Dept,IISc,Bangalore