Изменения
→Удаление вершины
== Описание дерева ==
=== Структура АА-дерева ===
{{Определение
|definition='''Уровень вершины''' (англ. ''Level'') {{---}} вертикальная высота соответствующей вершины.
}}
Для представления АА-дерева в памяти будем использовать следующую структуру:
[[Файл: Rb3.png]]
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин (получающиеся из соответствующего правила: , чтобы проверить соблюдается ли главное правило «одна правая одноуровневая связь (горизонтальное ребро)»: это устранение горизонтальная связь». То есть мы должны проверить нет ли левой горизонтальной связи , как на одном уровне первом рисунке ниже и устранение нет ли двух последовательных правых горизонтальных связей , как на одном уровне):правом рисунке.
[[Файл: Pr1.png]]
'''else''' '''if''' t.left.level == t.level
<font color=green>// Меняем указатель горизонтального левого ребра</font>
'''return''' Node(t.left,t.left.level,t.left.left,Node(t,t.level,t.left.right,t.right))
'''else'''
'''return''' t
'''if''' t == <tex>\varnothing</tex>
'''return''' <tex>\varnothing</tex>
'''else''' '''if''' t.right == <tex>\varnothing</tex> '''or''' t.right.right == <tex>\varnothing</tex>
'''return''' t
<font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font>
'''else''' '''if''' t.level == t.right.right.level
<font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font>
'''return''' Node(t.right,t.right.level+1,Node(t,t.level,t.left,t.right.left),t.right.right)
'''else'''
'''return''' t
=== Удаление вершины ===
Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находиться находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем <tex>1</tex>, имеющих двух детей, предшественник или преемник будет на уровне <tex>1</tex>, что делает их удаление тривиальным. Ниже представлена рекурсивная реализация алгоритма.
Будем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</tex>, она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.
'''else''' '''if''' t.left == <tex>\varnothing</tex>
l = successor(t)
t.right = delete(value(l).valuel, t.right)
t.value = l.value
'''else'''
l := predecessor(t) t.left = delete(l.value, t.left))
t.value = l.value
<font color=green>// Сбалансируем дерево. Если необходимо, уменьшим поля «уровень»
