splay tree

(redirected from Splay trees)

splay tree

A tree structure used to search a database. When a branch point (node) is accessed, it is rotated or "splayed" to the root, changing the structure of the tree. Since pointers to the most frequently accessed records are always moved closer to the starting point of the search, those records are typically located faster. See quad tree.
Mentioned in ?
References in periodicals archive ?
Binomial queues, pagodas, skew heaps, pairing heaps, and splay trees run with O(log n) time per hold operation.
Figures 2 and 3 compare the calendar queue hold time to the hold time for splay tree and linear linked list priority queue implementations.
Figure 2 shows that on the Harris minicomputer the calendar queue hold time becomes smaller than the splay tree hold time when the queue size reaches 20, and stays smaller as the queue grows.
The invention of splay trees arose out of work 1 did with two of my students, Sam Bent and Danny Sleator, at Stanford in the late 1970s.
Splay trees have even more striking theoretical properties.
On the basis of these results, Danny and I conjecture that splay trees are a universally optimum form of binary search tree in the following sense: Consider a fixed set of n items and an arbitrary sequence of m [is greater than or =] n retrievals of these items.
In addition to their intriguing theoretical properties, splay trees have potential value in practice.
The development of splay trees suggests several conclusions.
The splay tree, a self-adjusting form of binary search tree that Danny Sleator and I developed, is one such data structure.
Splay trees [2, 3] are an excellent candidate for use in this context.
Lacking this, an empirical test of my hypothesis about the relative performance of splay trees and min-max heaps must rest on their use in particular applications.