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


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 Wed Mar 13 12:42:46 2019.

Cite this as:
Chris L. Kuszmaul, "splay tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 17 November 2008. (accessed TODAY) Available from: