Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0766.68018
Sherk, Murray
Self-adjusting $k$-ary search trees.
(English)
[A] Algorithms and data structures, Proc. workshop WADS '89, Ottawa/Canada 1989, Lect. Notes Comput. Sci. 382, 381-392 (1989). ISBN 3-540-51542-9

Summary: [For the entire collection see Zbl 0753.00021.]\par We introduce a self-adjusting $k$-ary search tree scheme to implement the abstract data type DICTIONARY.\par 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\sb 2 n)$. (Note: All constants in our time bounds are independent of both $k$ and $n$.) This is within a factor of $O(\log\sb 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\sb 2 k+n\sp 2)$. These two results are $k$- ary analogues of two of {\it D. D. Sleator} and {\it 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\sb 2 k+n\log\sb k n)$, and similarly improve {\it D. D. Sleator} and {\it R. E. Tarjan's} [loc. cit.] static optimality result.
MSC 2000:
*68P05 Data structures

Keywords: self-adjusting $k$-ary search tree; DICTIONARY; heuristic; $k$-splaying; static optimality proof

Citations: Zbl 0753.00021; Zbl 0631.68060

Highlights
Master Server