NIST

splay tree

(data structure)

Definition: A binary search tree in which operations that access nodes restructure the tree.

Generalization (I am a kind of ...)
binary search tree.

Aggregate child (... is a part of or used in me.)
move-to-root heuristic.

Author: CLK

Implementation

Danny Sleator's (Java and C).

More information

Daniel D. Sleator and Robert E. Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3):652-686, 1985.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 November 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Chris L. Kuszmaul, "splay tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 November 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/splaytree.html