Изменения
→Удаление вершины
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию [[Красно-черное дерево|красно-черного дерева]] в 1993 году.
== Свойства Описание дерева ===== Структура АА-дерева ===
{{Определение
}}
Для представления АА-дерева в памяти будем использовать следующую структуру:
'''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> различных вариантов расположения вершин:
[[Файл: Rb3.png]]
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин (получающиеся из соответствующего правила: , чтобы проверить соблюдается ли главное правило «одна правая одноуровневая связь (горизонтальное ребро)»: это устранение горизонтальная связь». То есть мы должны проверить нет ли левой горизонтальной связи , как на одном уровне первом рисунке ниже и устранение нет ли двух последовательных правых горизонтальных связей , как на одном уровне): [[Файл: Rb6.png]] [[Файл: Rb7правом рисунке.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'''
'''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> r = '''return''' Node(t.right , t.right = r.level + 1, Node(t, t.level, t.left r, t.right.left = ), t r.level = rright.level + 1 '''return''' rright)
'''else'''
'''return''' t
t.right = insert(x, t.right)
<font color=green>// Случай x == t.value не определен. Т.е. вставка не будет иметь никакого эффекта,
// возможны различные варианты обработки, в зависимости от решаемой задачи</font>
t = skew(t)
t = split(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>// Сбалансируем дерево. Если необходимо, уменьшим поля "уровень" «уровень» // у вершин на данном уровне, и затем skew и split все вершины на новом уровне</font>
t = decreaseLevel(t)
t = skew(t)
t.right = skew(t.right)
'''if not''' t.right == <tex>\neq\ \varnothing</tex>
t.right.right = skew(t.right.right)
t = split(t)
== Эффективность ==
Оценка на высоту деревьев соответствует оценке для красно-черного дерева, <tex>2\cdot \log 2(N)</tex>, так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за <tex>O(\log N)</tex>, потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за <tex>O(h)</tex>. Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, overhead дополнительные расходы по памяти достигает достигают байта.
== См. также ==
