Self-adjustingk-ary search trees and self-adjusting balanced search trees
Murray Sherk, Allan Borodin · 1989
We consider self-adjusting data structures for dictionaries allowing insertions, deletions, and membership queries. Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree maintained using the splay heuristic. Two disadvantages of the splay heuristic are that it is defined only for binary search trees and that the worst-case single operation time in an $n$-node tree is $\Theta(n)$. In the first part of this thesis, the $k$-splay heuristic for $k$-ary search trees is introduced and we prove some efficiency results indicating that effective self-adjustment can be performed in $k$-ary search trees. In the second part of the thesis, the deepsplay heuristic for binary search trees is introduced and analyzed. For trees maintained using deepsplaying, we show that the amortized operation time is logarithmic in the number of nodes, and that for any sufficiently long sequence of membership queries, the time required in a deepsplay tree is at most a constant factor more than the time required in an optimal static tree for the sequence. These two results are analogues of two of the most important splay heuristic results, and support the conjecture that deepsplay trees are optimal, to within a constant factor, on all sufficiently long request sequences. In addition, we prove that any $n$-node deepsplay tree has height $O(\sqrt{n}$ log $n)$. Experimental results suggest that the height of an $n$-node deepsplay tree is at most 4 log $n$. Thus, deepsplay tree time is apparently optimal, to within a constant factor, for worst-case single operations as well as all sufficiently long request sequences.