General Splay A Basic Theory and Calculus
Short Description
General Splay: A Basic Theory and Calculus. G. F. Georgakopoulos. ggeo@csd.uch.gr. D. J. M. c. Clurkin. davidmcc@csd.uch.gr. Dept. of Computer Science …
Website: www.csd.uoc.gr | Filesize: 387kb
Content
- 1 -
General Splay: A Basic Theory and Calculus
G. F. Georgakopoulos
ggeo@csd.uch.gr
D. J. McClurkin
davidmcc@csd.uch.gr
Dept. of Computer Science
University of Crete, Heraklion, Greece
1 . Introduction.
The directory problem, that of handling an on-line series of INSERT, DELETE and FIND requests, is for
most applications addressed satisfactorily by balanced search trees (BST) (see e.g., [Ov83] for a trace
of BST’s from [AVL62] and on), which guarantee O(logN) worst time for each of these operations. For
applications however in which the access frequencies are highly biased the “overbalancedness” of these
trees yields suboptimal performance. This was addressed first, statically, in the 1970’s with biased
search trees (see [Kn71], [HT71], [BST85]), and later dynamically in the 1980’s with splay trees (see
[ST85]). Splay trees achieve a logarithmic amortized cost for searching and other operations, and are
competitive w.r.t. any other static binary search tree on the same set of elements (see also [Ta85]).
However [ST85] left some important issues open, among which the most intriguing is the dynamic
optimality conjecture: Are…
Get the file Download here
Related Searches: computer science website, balanced search trees, binary search tree, splay trees, computer science university
Comments
Leave a Reply
