54
правки
Изменения
Нет описания правки
* В некоторых случаях операции модификации занимают <tex>O(n)</tex>, хотя из амортизированная сложность - <tex>O(\log n)</tex>.
* За счет отсутствия необходимости хранить дополнительные данные в вершинах данное дерево оптимальнее остальных по памяти.
== Операции ==
=== Поиск ===
*<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
*<tex>k</tex> {{---}} искомый ключ в дереве.
'''Search'''(root, k):
'''if ''' root = null or root.key = k:
'''return ''' root
'''else if ''' k ≤ root.lef t.key:
'''return ''' Search(root.lef t, k)
'''else''':
'''return ''' Search(root.right, k)
=== Вставка элемента ===
Пока дерево остается <tex>\alpha</tex>-сбалансированным, выполняем модифицированную вставку элемента в дерево, которая аналогична обычной вставке в двоичное дерево, но операция <tex>InsertKey(k)</tex> будет возвращать глубину данной вершины.
Нам нужна специальная функция <tex>FindScapegoat(n)</tex>, которая позволяет найти тот элемент дерева, который испортил баланс (именно из-за этой процедуры дерево так называется. Scapegoat - "козел отпущения", который испортил баланс).
*<tex>n</tex> {{---}} узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
'''FindScapegoat'''(n):
size = 1
height = 0
'''while''' (n.parent <> null):
height = height + 1
totalSize = 1 + size + n.sibling.size()
'''if''' height > ⌊log1/α(totalSize)⌋:
'''return''' n.parent
n = n.parent
size = totalSize
== Оценка времени работы ==
