scapegoat tree


Definition: A binary search tree that needs no balance information. Search time is logarithmic, and the amortized cost of update is logarithmic.

Note: I. Galperin and R. L. Rivest, Scapegoat trees, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993, pages 165-174.

Author: PEB

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 24 May 2004.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "scapegoat tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 24 May 2004. (accessed TODAY) Available from: