**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.