96
правок
Изменения
м
Нет описания правки
'''Scapegoat-tree''' {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее время поиска {{---}} <tex>O(\log N)</tex>, и амортизирующее время вставки и удаления элемента {{---}} <tex>O(\log N)</tex>.
В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
{| class="wikitable"
|-
! rowspan="2" |
! colspan="2" | Insert
! colspan="2" | Delete
! colspan="2" | Search
! colspan="2" | Память
! rowspan="2" | Описание
|-
! style="background: #ddffdd;" | Среднее
! style="background: #ffdddd;" | Худшее
! style="background: #ddffdd;" | Среднее
! style="background: #ffdddd;" | Худшее
! style="background: #ddffdd;" | Среднее
! style="background: #ffdddd;" | Худшее
! style="background: #ddffdd;" | Среднее
! style="background: #ffdddd;" | Худшее
|-
| Scapegoat-tree
| align="center" style="background: #ddffdd;" | <tex>O(log n)</tex>
| align="center" style="background: #ffdddd;" | Амортизировано <tex>O(log n)</tex>
| align="center" style="background: #ddffdd;" | <tex>O(log n)</tex>
| align="center" style="background: #ffdddd;" | Амортизировано <tex>O(log n)</tex>
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(log n)</tex>
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
| align="center" | Сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]]. В отличие от большинства других самобалансирующихся бинарных деревьев поиска не требует дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
|}
== Операции ==
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]
[[Категория:Алгоритмы и структуры данных]][[Категория:Деревья поиска]]
