302
правки
Изменения
Нет описания правки
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию [[Красно-черное дерево|красно-черного дерева]] в 1993 году.
== Свойства Описание дерева ==
{{Определение
|definition='''Уровень вершины''' (англ. ''Level'') {{---}} вертикальная высота соответствующей вершины.
}}
=== Структура АА-дерева ===
Для представления АА-дерева в памяти будем использовать следующую структуру:
'''struct''' Node:
'''V''' value <font color="green">// значение вершины</font>
'''Node''' level <font color="green">// указатель на предка</font>
'''Node''' left <font color="green">// указатель на левого потомка</font>
'''Node''' right <font color="green">// указатель на правого потомка</font>
<font color=green>// Конструктор вершины (создаем экземпляр структуры с полученными значениями)</font>
'''Node''' (value : '''V''', level : '''V''', left : '''Node''', right: '''Node''')
=== Свойства АА-дерева ===
Свойства АА-дерева:
*Уровень каждого листа равен <tex>1</tex>.
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
*Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.
*Уровень каждого правого внука строго меньше, чем у его прародителя.
*Каждая вершина с уровнем больше <tex>1</tex> имеет двоих детей.
=== Связь с красно-чёрным деревом ===
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример красно-чёрного дерева.
[[Файл: Exaa2.PNG]]
Для поддержки баланса красно-черного дерева необходимо обрабатывать <tex>7</tex> различных вариантов расположения вершин:
[[Файл: Pr1.png]]
== Балансировка ==
'''else''' '''if''' t.left == <tex>\varnothing</tex>
'''return''' t
<font color=green>// Проверяем, есть ли у нас левое горизонтальное ребро</font>
'''else''' '''if''' t.left.level == t.level
<font color=green>// Меняем указатель горизонтального левого ребра</font>
'''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>
