Self-adjusting \(k\)-ary search trees.

*(English)*Zbl 0766.68018
Algorithms and data structures, Proc. workshop WADS ’89, Ottawa/Canada 1989, Lect. Notes Comput. Sci. 382, 381-392 (1989).

Summary: [For the entire collection see Zbl 0753.00021.]

We introduce a self-adjusting \(k\)-ary search tree scheme to implement the abstract data type DICTIONARY.

We consider a self-adjustment heuristic for \(k\)-ary search trees. We present a heuristic called \(k\)-splaying and prove that the amortized number of node READs per operation in \(k\)-ary trees maintained using this heuristic is \(O(\log_ 2 n)\). (Note: All constants in our time bounds are independent of both \(k\) and \(n\).) This is within a factor of \(O(\log_ 2 k)\) of the amortized number of node READs required for a \(B\)-tree operation. A \(k\)-ary tree maintained using the \(k\)-splay heuristic can be thought of as a self-adjusting \(B\)-tree. It differs from a \(B\)-tree in that leaves may be at different depts and the use of space is optimal. We also prove that the time efficiency of \(k\)-splay trees is comparable to that of static optimal \(k\)-ary trees. If sequence \(s\) in a static optimal tree takes time \(t\), then sequence \(s\) in any \(k\)-splay tree will take time \(O(t\log_ 2 k+n^ 2)\). These two results are \(k\)- ary analogues of two of D. D. Sleator and R. E. Tarjan’s [J. Assoc. Comput. Mach. 32, 652-686 (1985; Zbl 0631.68060)] results for splay trees. As part of our static optimality proof, we prove that for every static tree (including any static optimal tree) there is a balanced static tree which takes at most twice as much time on any sequence of search operations. This lemma allows us to improve our static optimality bound to \(O(t\log_ 2 k+n\log_ k n)\), and similarly improve D. D. Sleator and R. E. Tarjan’s [loc. cit.] static optimality result.

We introduce a self-adjusting \(k\)-ary search tree scheme to implement the abstract data type DICTIONARY.

We consider a self-adjustment heuristic for \(k\)-ary search trees. We present a heuristic called \(k\)-splaying and prove that the amortized number of node READs per operation in \(k\)-ary trees maintained using this heuristic is \(O(\log_ 2 n)\). (Note: All constants in our time bounds are independent of both \(k\) and \(n\).) This is within a factor of \(O(\log_ 2 k)\) of the amortized number of node READs required for a \(B\)-tree operation. A \(k\)-ary tree maintained using the \(k\)-splay heuristic can be thought of as a self-adjusting \(B\)-tree. It differs from a \(B\)-tree in that leaves may be at different depts and the use of space is optimal. We also prove that the time efficiency of \(k\)-splay trees is comparable to that of static optimal \(k\)-ary trees. If sequence \(s\) in a static optimal tree takes time \(t\), then sequence \(s\) in any \(k\)-splay tree will take time \(O(t\log_ 2 k+n^ 2)\). These two results are \(k\)- ary analogues of two of D. D. Sleator and R. E. Tarjan’s [J. Assoc. Comput. Mach. 32, 652-686 (1985; Zbl 0631.68060)] results for splay trees. As part of our static optimality proof, we prove that for every static tree (including any static optimal tree) there is a balanced static tree which takes at most twice as much time on any sequence of search operations. This lemma allows us to improve our static optimality bound to \(O(t\log_ 2 k+n\log_ k n)\), and similarly improve D. D. Sleator and R. E. Tarjan’s [loc. cit.] static optimality result.

##### MSC:

68P05 | Data structures |