Editing Scapegoat tree (section)

{{Short description|Type of balanced binary search tree}}
{{multiple issues|
{{more footnotes|date=March 2014}}
{{refimprove|date=March 2014}}
}}
{{Infobox data structure-amortized
|name=Scapegoat tree
|type=tree
|invented_year=1989
|invented_by=[[Arne Andersson (computer scientist)|Arne Andersson]], [[Igal Galperin]], [[Ronald L. Rivest]]
|space_avg=<math>O(n)</math>
|search_avg=<math>O(\log n)</math>
|search_worst=<math>O(\log n)</math><ref name=galperin_rivest/>{{rp|165}}
|insert_avg=<math>O(\log n)</math><ref name=galperin_rivest/>{{rp|165}}
|insert_worst=<math>O(n)</math><ref name=galperin_rivest/>{{rp|167}}
|delete_avg=<math>O(\log n)</math><ref name=galperin_rivest/>{{rp|165}}
|delete_worst=<math>O(n)</math><ref name=galperin_rivest/>{{rp|167}}
}}

In [[computer science]], a '''scapegoat tree''' is a [[self-balancing binary search tree]], invented by [[Arne Andersson (computer scientist)|Arne Andersson]]<ref name=anderson1>{{Cite conference |title=Improving partial rebuilding by using simple balance criteria |url=http://user.it.uu.se/~arnea/abs/partb.html |citeseerx=10.1.1.138.4859 |journal=Journal of Algorithms |first=Arne |last=Andersson |conference=Proc. Workshop on Algorithms and Data Structures |pages=393–402 |year=1989 |publisher=Springer-Verlag |doi=10.1007/3-540-51542-9_33}}</ref> in 1989 and again by [[Igal Galperin]] and [[Ronald L. Rivest]] in 1993.<ref name=galperin_rivest>{{Cite conference |first1=Igal |last1=Galperin  |first2=Ronald L. |last2=Rivest |authorlink2=Ronald L. Rivest |title=Scapegoat trees |journal=Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |pages=165–174 |year=1993 |url=http://people.csail.mit.edu/rivest/pubs/GR93.pdf |citeseerx=10.1.1.309.9376 |isbn=0-89871-313-7 |publisher=[[Society for Industrial and Applied Mathematics]] |location=Philadelphia}}</ref>  It provides worst-case [[big O notation|<math>{\color{Blue}O(\log n)}</math>]] lookup time (with <math>n</math> as the number of entries) and <math>O(\log n)</math> [[amortized analysis|amortized]] insertion and deletion time.

Unlike most other self-balancing binary search trees which also provide worst case <math>O(\log n)</math> lookup time, scapegoat trees have no additional per-node memory overhead compared to a regular [[binary search tree]]: besides key and value, a node stores only two pointers to the child nodes. This makes scapegoat trees easier to implement and, due to [[data structure alignment]], can reduce node overhead by up to one-third.

Instead of the small incremental rebalancing operations used by most balanced tree algorithms, scapegoat trees rarely but expensively choose a "scapegoat" and completely rebuilds the subtree rooted at the scapegoat into a complete binary tree.  Thus, scapegoat trees have <math>O(n)</math> worst-case update performance.