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

АВЛ-дерево с [math] O(1) [/math] бит в каждом узле

Идея

В обычной реализации АВЛ-дерева[1] в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются на [math]1[/math] (при разбалансировке вершины разность поддеревьев будет максимум [math]2[/math] или [math]-2[/math]), то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать разницу между высотами его правой и левой ветки - назовём его фактор баланса. Таким образом в каждом узле будет хранится [math]1[/math] - если высота правого поддерева выше левого, [math]0[/math] - если высоты равны, и [math]-1[/math] - если правое поддерево выше левого.

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

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

Первый случай: малое вращение

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

Операции

Операция добавления Пусть нам надо добавить ключ [math]t[/math]. Будем спускаться по дереву, как при поиске ключа [math]t[/math]. Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Пересчитываем баланс данного узла [math]a[/math]. Дальше начинаем подниматься верх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то баланс уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math], то это значит, что высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным [math]2[/math] или [math]-2[/math], то делаем балансировку. Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.

Операция удаления Если вершина - лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math], поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math], то это значит, что высота поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным [math]2[/math] или [math]-2[/math], то делаем балансировку. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.