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.

  

Figure 4.23: An example of searching in splay trees

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.

  

Figure 4.24: An example of an insert in a splay tree

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.

  

Figure 4.25: An example of a delete in a splay tree