Изменения

== АВЛ-дерево с со значениями <tex> O(1) , 0, -1 </tex> бит в каждом узле ==

В обычной реализации АВЛ-дерева[http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE] в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на <tex>1</tex> (при разбалансировке вершины разность поддеревьев будет максимум <tex>2</tex> или <tex>-2</tex>), то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать разницу между высотами его правой и левой ветки - назовём его ''фактор баланса''. Таким образом в каждом узле будет хранится <tex>1</tex> - если высота правого поддерева выше левого, <tex>0</tex> - если высоты равны, и <tex>-1</tex> - если правое поддерево выше левого. 

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

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

Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота-трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины <tex>i</tex> как <tex>balance[i]</tex>. Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины <tex>a</tex>, если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения <tex>2</tex> или <tex>-2</tex> в вершине <tex>a</tex>.

|'''Малое левое вращение''' | [[Файл:avl_u1Avl_u1_old.jpgpng|2000x200px]]

'''1 вариант:''' <tex>balance[a] = -21</tex> и <tex>balance[b] = -1</tex>

'''2 вариант:''' <tex>balance[a] = -21</tex> и <tex>balance[b] = 0</tex>.

|'''Большое левое вращение''' | [[Файл:avl_u2Avl_u2_old.jpgpng|2000x200px]]

'''1 вариант:''' <tex>balance[a] = -21</tex> , <tex>balance[b] = 1</tex> и <tex>balance[c] = 1</tex>

'''2 вариант:''' <tex>balance[a] = -21</tex>, <tex>balance[b] = 1</tex> и <tex>balance[c] = -1</tex>

'''3 вариант:''' <tex>balance[a] = -21</tex>, <tex>balance[b] = 1</tex> и <tex>balance[c] = 0</tex>.

Ниже приведены примеры большого добавления и малого вращения удаления вершины с подписанными изменениями балансов факторов баланса каждой вершины, участвующей в повороте.[[Файл:Avl-smallrotationAvl_add.png|1150px|thumb|left|'''Первый случай: малое вращениеДобавление''']][[Файл:Avl-bigrotationAvl_delete.png|1150px|thumb|left|'''Второй случай: большое вращение''']]<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>