Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]