Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In a splay tree, doing $m$ sequential search operations for the same key that is in the tree has a time complexity in $O(n+m)$ where n is the number of nodes in the tree. Since the first search has a worst-case complexity of $O(n)$ and afterwards the node we're looking for is the new root, so further search operations take $O(1)$ time.
How could we prove that $m$ sequential search operations for the same key that is not in the tree also has a time complexity in $O(n+m)$?
In a BST, a lookup for an key that isn't present traces out a path through that tree that ends at either that key's successor or that key's predecessor. We'll use this property to get the desired $O(m + n)$ bound.
To begin with, suppose that what you're searching for is smaller than all other keys in the tree or bigger than all the keys in the tree. In that case, the first lookup will terminate at either the smallest or largest key in the tree, splaying it to the root in time $O(n)$. From that point, each search will be performed by starting at the root and either walking off the tree to the left or walking off the tree to the right, taking time $O(1)$, for a net total of $O(m + n)$ work done with the accesses.
Otherwise, the key $x$ we're looking for is sandwiched between keys $p$ and $s$, representing the key's predecessor or successor. This means that $p < x < s$. Consider the first two searches for $x$. The first one will terminate either at $p$ or at $s$, splaying it up to the root. Assume WLOG that it's $p$. The second search will then begin at $p$ and end at $s$, which splays $s$ up to the root. Let's think about what that process looks like. Specifically, focus on the very last splay step that takes $s$ up to the root. It can't be a zig-zig or zag-zag step, since if that were the case there would have to be a key $t$ sandwiched between $p$ and $s$, which is impossible because $p$ is $s$'s predecessor and $s$ is $p$'s successor. Therefore, the last splay operation that carries $s$ up to the root must either be a zig-zag step or a zig step (or one of the mirrors). Either way, the final splay step consists of rotating $s$ directly over $p$. That means that the tree now has $s$ as the root with $p$ as its left child. Importantly, $p$ has no right child, since if $p$ had a right child $t$ then we'd have $p < t < s$, which is impossible because $p$ is $s$'s predecessor.
Now, think about the next lookup. It will start at $s$, then move left to $p$, then move right from $p$ off the tree. We then splay $p$ up to the root. This requires only two node visits and one rotation and takes time $O(1)$. We now have $p$ as the root with $s$ as the right child. And, analogously to before, $s$ will not have a left child because $p$ is its predecessor. A search for $x$ now starts at $p$, moves right to $s$, then moves left off the tree, splaying $s$ back up to the root with $p$ as its right child. That process takes time $O(1)$ as well.
Overall, the first two splays to pull $s$ and $p$ up to the top of the tree take time $O(n)$, and each successive search takes time $O(1)$, toggling between whether $s$ or $p$ is the tree root. This makes the overall time spent $O(m + n)$.
