Insertion and Search

Insertion probably has the simplest implementation. We start by doing a standard binary tree insert, then splay the newly inserted node.

Searching is slightly less simple, as we modify the tree regardless of whether the item is present in the tree or not. We start with a standard binary search, after which we perform one of two possible operations. In the case that we found the node we were looking for, we splay it and return it. Otherwise, we splay the last node that was visited while searching. This is useful later during deletion.