SELF-ADJUSTING K-ARY SEARCH-TREES

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(log(2) n) 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. (C) 1995 Academic Press, Inc.