21
правка
Изменения
Новая страница: «'''В данной модификации нам заранее будет известно количество памяти, которое мы должны в...»
'''В данной модификации нам заранее будет известно количество памяти, которое мы должны выделить на узел дерева.'''
== Идея ==
В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Теперь же мы будем хранить только "перекос" дерева, так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на 1. Таким образом в каждом узле будет хранится ''+1'' - если высота левого поддерева больше высоты правого, ''0'' - если высота левого равна высоте правого, и ''-1'' - если высота левого поддерева меньше высоты правого.
== Операции ==
Все операции делаются так же, как и в обычной реализации АВЛ-дерева[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|'''Второй случай: большое вращение''']]
== Идея ==
В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Теперь же мы будем хранить только "перекос" дерева, так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на 1. Таким образом в каждом узле будет хранится ''+1'' - если высота левого поддерева больше высоты правого, ''0'' - если высота левого равна высоте правого, и ''-1'' - если высота левого поддерева меньше высоты правого.
== Операции ==
Все операции делаются так же, как и в обычной реализации АВЛ-дерева[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|'''Второй случай: большое вращение''']]
