Изменения

|-

| Scapegoat-tree

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

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

| align="center" | Сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. В отличие от большинства других самобалансирующихся бинарных деревьев поиска не требует дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.