Изменения

'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое является разновидностью [[Красно-черное дерево|красно-черного дерева ]] с дополнительными ограничениями.

АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию B[[Красно-черное дерево|красно-черного дерева ]] в 1993 году. == Описание дерева ===== Структура АА-дерева ===

|definition='''Уровень вершины''' (англ. ''Level'') {{- --}} вертикальная высота соответствующей вершины. Уровень листа равен 1.

В отличие от красно=== Свойства АА-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка).дерева ===

== Свойства ==АА-дерева:*Уровень каждого листа равен <tex>1</tex>.

*Уровень каждого правого ребенка равен или на один меньше, чем у его родителя.

*Каждая вершина с уровнем больше <tex>1 </tex> имеет двоих детей. === Связь с красно-чёрным деревом === В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка). На картинке ниже представлен пример красно-чёрного дерева. [[Файл: Exaa.PNG]] Теперь рассмотрим то же дерево, но с информацией об уровне каждой вершине. Горизонтальные ребра обозначают связи между ребрами одного уровня. [[Файл: Ex10.PNG]] На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация только о ее уровне. [[Файл: Exaa2.PNG]]

Для поддержки баланса красно-черного дерева необходимо обрабатывать <tex>7 </tex> различных вариантов расположения вершин:

В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:, чтобы проверить соблюдается ли главное правило «одна правая горизонтальная связь». То есть мы должны проверить нет ли левой горизонтальной связи, как на первом рисунке ниже и нет ли двух последовательных правых горизонтальных связей, как на правом рисунке.

[[Файл: Rb2Pr1.png]]

|definition='''Горизонтальное ребро''' (англ. ''Horizontal edges'') {{- --}} ребро, соединяющее вершины с одинаковым уровнем.

В AA - дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра. Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA - дерева.

[[Файл: === Skew.png]]===

'''functionNode''' skew '''is''' '''input'''(t : T, a node representing an AA tree that needs to be rebalanced. '''outputNode''': Another node representing the rebalanced AA tree. ) '''if''' T t == NULL '''then'''<tex>\varnothing</tex> '''return''' NULL<tex>\varnothing</tex> '''else''' '''if''' t.left(T) == NULL '''then'''<tex>\varnothing</tex> '''return''' Tt <font color=green>// Проверяем, есть ли у нас левое горизонтальное ребро</font> '''else''' '''if''' t.left.level(left(T)) == t.level(T) <font color=green>// Меняем указатель горизонтального левого ребра</font> '''thenreturn''' Swap the pointers of horizontal Node(t.left, t.left.level, t.left links. L = left, Node(T) t, t.level, t.left(T) := .right, t.right(L) right(L) := T '''return''' L

'''return''' Tt '''end''' '''if''' '''end''' '''function'''На рисунке ниже представлен пример работы алгоритма.

#'''=== Split(T)''' {{---}} устранение двух последовательных правых горизонтальных ребер.===

[[Файл: Split_rb'''<tex>\mathrm{Split(t)}</tex>''' {{---}} устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.png]]

'''functionNode''' split '''is''' '''input'''(t : T, a node representing an AA tree that needs to be rebalanced. '''outputNode''': Another node representing the rebalanced AA tree. ) '''if''' nil(T) '''then'''t == <tex>\varnothing</tex> '''return''' Nil<tex>\varnothing</tex> '''else''' '''if''' nil(t.right(T)) == <tex>\varnothing</tex> '''or''' nil(t.right(.right(T))) '''then'''== <tex>\varnothing</tex> '''return''' Tt <font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font> '''else''' '''if''' t.level(T) == level(t.right(.right(T))) .level <font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font> '''thenreturn''' We have two horizontal Node(t.right, t.right links. Take the middle nodelevel + 1, elevate itNode(t, and return itt.level, t.left, t. R = right(T.left) , t.right.right(T) := left(R) left(R) := T level(R) := level(R) + 1 '''return''' R

'''return''' Tt '''end''' '''if''' '''end function'''На рисунке ниже представлен пример работы алгоритма. [[Файл: Split_rb.png]]

Рекурсивная Вставка нового элемента происходит как в обычном дереве поиска, только на пути вверх необходимо делать ребалансировку, используя <tex>\mathrm{skew}</tex> и <tex>\mathrm{split}</tex>. Ниже представлена рекурсивная реализацияалгоритма. Спускаемся от корня вниз по дереву  '''Node''' insert(x : '''V''', сравнивая ключи; вставляем новую вершину; выходим из рекурсии и выполняем балансировкуt : '''Node''') <font color=green>// x {{---}} вставляемое значение, t {{---}} корень дерева, в который вставляется вершина</font> '''if''' t == <tex>\varnothing</tex> '''return''' Node(x, 1, <tex>\varnothing</tex>, <tex>\varnothing</tex>) '''else if''' x < t.value t.left = insert(x, t.left) '''else if''' x > t.value t.right = insert(x, t.right) <font color=green>// Случай x == t.value не определен. Т.е. вставка не будет иметь никакого эффекта, // возможны различные варианты обработки, в зависимости от решаемой задачи</font> t = skew и (t) t = split для каждой вершины(t) '''return''' t Пример вставки нового элемента (на рис.уровни разделены горизонтальными линиями):

'''function''' insert '''is''' '''input'''[[Файл: X, the value to be inserted, and T, the root of the tree to insert it intoEx_insert. '''output''': A balanced version T including X. Do the normal binary tree insertion procedure. Set the result of the recursive call to the correct child in case a new node was created or the root of the subtree changes. '''if''' nil(T) '''then''' Create a new leaf node with X. '''return''' node(X, 1, Nil, Nil) '''else if''' X < value(T) '''then''' left(T) := insert(X, left(T)) '''else if''' X > value(T) '''then''' right(T) := insert(X, right(T)) '''end if''' Note that the case of X == value(T) is unspecified. As given, an insert will have no effect. The implementor may desire different behavior. Perform skew and then split. The conditionals that determine whether or not a rotation will occur or not are inside of the procedures, as given above. T := skew(T) T := split(T) '''return''' T '''end function'''png]]