Изменения

В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.

|-

! colspan="2" | Insert

! colspan="2" | Delete

! colspan="2" | Search

! colspan="2" | Память

|-

! style="background: #ddffdd;" | Среднее

| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(log\ n)</tex>

| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>

|}

===Обозначения и Определения===