@InProceedings{GR93, author = { Igal Galperin and Ronald L. Rivest }, title = { Scapegoat trees }, pages = { 165--174 }, OPTurl = { http://dl.acm.org/citation.cfm?id=313559.313676 }, url = { http://doi.acm.org/10.1145/313559.313676 }, acmid = { 313676 }, booktitle = { Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms }, date = { 1993 }, editor = { Vijaya Ramachandran }, publisher = { SIAM }, isbn = { 0-89871-313-7 }, OPTyear = { 1993 }, OPTmonth = { January 25--27. }, eventdate = { 1993-01-25/1993-01-27 }, eventtitle = { SODA '93 }, venue = { Austin, Texas }, note = { Chapter 19. }, abstract = { We present an algorithm for maintaining binary search trees. The amortized complexity per \textsc{Insert} or \textsc{Delete} is $O(\log n)$ while the \emph{worst-case} cost of a \textsc{Search} is $O(\log n)$. \par Scapegoat trees, unlike most balanced-tree schemes, do not not require keeping extra data (e.g. ``colors'' or ``weights'') in the tree nodes. Each node in the tree contains only a key value and pointers to its two children. Associated with the root of the whole tree are the only two extra values needed by the scapegoat scheme: the number of nodes in the whole tree, and the maximum number of nodes in the tree since the tree was last completely rebuilt. \par In a scapegoat tree a typical rebalancing operation begins at a leaf, and successively examines higher ancestors until a node (the ``scapegoat'') is found that is so unbalanced that the entire subtree rooted at the scapegoat can be rebuilt a zero cost, in an amortized sense. Hence the name. }, }