splay tree

(redirected from Splay trees)

splay tree

A tree structure used to search a database that self adjusts. When a branch point (node) in a splay tree is accessed, it is rotated or "splayed" to the root, changing the tree's structure. Because the pointers to the most frequently accessed records are moved closer to the starting point of the tree, those records will be located faster the next time they are searched. See quad tree and binary 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.