1632
правки
Изменения
м
rollbackEdits.php mass rollback
<tex> 1/2 \leqslant \alpha \leqslant 1 </tex>;
<tex> size(left[x]) \leqslant \alpha \cdot size(x) </tex>;
<tex> size(right[x]) \leqslant \alpha \cdot size(x) </tex>, где <tex>size(left[x])</tex> и <tex>size(right[x])</tex> {{- --}} размер левого и правого поддерева вершины <tex>x</tex>.
Примечание:
Существует два подхода к балансу дерева, которые дают похожий результат. Первый {{- --}} задавать <tex>\alpha</tex>. Второй {{--- }} задать ограничение <tex>q</tex>, большее чем число элементов в дереве (чем больше ограничение, тем более несбалансированным может быть дерево), и следить, чтобы <tex>\log_{3/2}(q)</tex> был больше максимальной глубины дерева. В противном случае, необходимо произвести перебалансировку дерева.
== Свойства ==
=== Удаление элемента элемента ===
Сначала надо удалить вершину, как в обычном двоичном дереве. Потом надо проверить дерево на сбалансированность. Если дерево осталось сбалансированным, ничего делать не надо. В противном случае надо начать перебалансировку дерева.
Функция DeleteKey(k) удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
