АВЛ-дерево с O(1) бит в каждом узле — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''В данной модификации нам заранее будет известно количество памяти, которое мы должны в...»)
(нет различий)

Версия 20:28, 2 июня 2015

В данной модификации нам заранее будет известно количество памяти, которое мы должны выделить на узел дерева.

Идея

В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Теперь же мы будем хранить только "перекос" дерева, так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на 1. Таким образом в каждом узле будет хранится +1 - если высота левого поддерева больше высоты правого, 0 - если высота левого равна высоте правого, и -1 - если высота левого поддерева меньше высоты правого.

Операции

Все операции делаются так же, как и в обычной реализации АВЛ-дерева[1], то есть мы добавили/удалили вершину, идем вверх и пересчитываем "перекосы" вершин. Нам интересна операция балансировки.

Балансировка

Для исправления "перекосов" вершин в подобной ситуации, достаточно знать "перекосы" двух(для большого вращения - трех) вершин перед поворотом, и исправить значения этих же вершин после поворота.

Первый случай: малое вращение
Второй случай: большое вращение