Self-Adjusting k-ary Search Trees

✍ Scribed by M. Sherk

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 994 KB
• Volume: 19
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1995.1026

✦ Synopsis

We present an online self-adjusting (k)-ary search tree, the (k)-splay tree, as a generalization of the binary splay tree. We prove a (k)-ary analogue of Sleator and Tarjan's splay tree access lemma using a considerably more complicated argument based on their technique. This lemma is used to prove that the amortized number of node accesses per operation in a (k)-splay tree with (n) keys is (O\left(\log _{2} n\right)) and that, to within a factor of (\log _{2} k, k)-splay trees are statistically optimal with respect to node accesses, i.e., in an amortized sense as good as any offline static (k)-ary tree. We also show how to maintain optimal use of node space in the presence of insertions and deletions. Like the (B)-tree, the (k)-splay tree makes effective use of (k)-ary branching and secondary storage. Unlike the splay tree and the (B)-tree, the (k)-splay tree may be optimal among all (k)-ary trees in an amortized sense with respect to node accesses. 1995 Academic Press, Inc.