zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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(tlog 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(tlog 2 k+nlog k n), and similarly improve D. D. Sleator and R. E. Tarjan’s [loc. cit.] static optimality result.

MSC:
68P05Data structures