21
правка
Изменения
Нет описания правки
=== Идея ===В обычной реализации АВЛ-дерева [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] в каждом узле мы хранили высоту этого узла. Теперь же мы будем хранить только "перекос" дерева, так Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на <mathtex>1</mathtex> (при разбалансировке вершины разность поддеревьев будет максимум <tex>2</tex>или <tex>-2</tex>), то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать разницу между высотами его правой и левой ветки - назовём его ''фактор баланса''. Таким образом в каждом узле будет хранится <mathtex>+1</mathtex> - если высота правого поддерева выше левого поддерева больше высоты правого, <mathtex>0</mathtex> - если высота левого равна высоте правоговысоты равны, и <mathtex>-1</mathtex> - если высота правое поддерево выше левого поддерева меньше высоты правого.
== Операции = Балансировка ===Все Опишем операции делаются так жебалансировки, как а именно малый поворот, большой поворот и в обычной реализации АВЛ-дерева[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], то есть мы добавили/удалили вершину, идем вверх Балансировка нам нужна для операций добавления и пересчитываем "перекосы" вершин. Нам интересна операция балансировкиудаления узла. == Балансировка ==Для исправления "перекосов" вершин в подобной ситуациифакторов баланса, достаточно знать "перекосы" факторы баланса двух(для в случае большого вращения поворота- трех) вершин перед поворотом, и исправить значения этих же вершин после поворота.
[[Файл:Avl-smallrotation.png|1000px|thumb|left|'''Первый случай: малое вращение''']]
[[Файл:Avl-bigrotation.png|1000px|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>
=== Операции ===
'''Операция добавления'''
Пусть нам надо добавить ключ <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>2</tex> или <tex>-2</tex>, то делаем балансировку. Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.
'''Операция удаления'''
Если вершина - лист, то просто удалим её, иначе найдём ближайшую по значению вершину <tex>a</tex>, поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину <tex>i</tex> из левого поддерева, то фактор баланса увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным <tex>1</tex> или <tex>-1</tex>, то это значит, что высота поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным <tex>2</tex> или <tex>-2</tex>, то делаем балансировку. Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.
