Изменения

'''А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''' T '''end''' '''if''' '''end''' '''function'''t

#'''Split(T)''' {{---}} устранение двух последовательных правых горизонтальных ребер[[Файл: Skew.png]]

[[Файл: Split_rb=== Split === '''<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>. Ниже представлена рекурсивная реализация алгоритма.

'''functionNode''' insert (x : '''is''' '''inputV''', t : X, the value to be inserted, and T, the root of the tree to insert it into. '''outputNode''': 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.<font color=green>// x {{---}} вставляемое значение, t {{---}} корень дерева, в который вставляется вершина</font> '''if''' nil(T) '''then''' Create a new leaf node with X.t == <tex>\varnothing</tex> '''return''' nodeNode(Xx, 1, Nil<tex>\varnothing</tex>, Nil<tex>\varnothing</tex>) '''else if''' X x < t.value(T) '''then''' t.left(T) := insert(Xx, t.left(T)) '''else if''' X x > t.value(T) '''then''' t.right(T) := insert(Xx, t.right(T)) '''end if''' Note that the case of X <font color=green>// Случай x == t.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.в зависимости от решаемой задачи</font> T :t = skew(Tt) T :t = split(Tt) '''return''' T '''end function'''t

Рекурсивная реализация. Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего "предшественника" (англ. ''predecessor'') «предшественника» или "преемника" (англ. ''successor'')«преемника», в зависимости от реализации. "Предшественник" находиться «Предшественник» находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, "преемник" «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на NULL. В силу свойства всех узлов уровня более чем <tex>1</tex>, имеющих двух детей, предшественник или преемник будет на уровне <tex>1</tex>, что делает их удаление тривиальным.Ниже представлена рекурсивная реализация алгоритма. Будем использовать дополнительную функцию <tex>\mathrm{decreaseLevel}</tex>, она будет обновлять уровень вершины, которую передают в функцию, в зависимости от значения уровня дочерних вершин.  '''Node''' decreaseLevel(t : '''Node''') shouldBe = min(t.left.level, t.right.level) + 1 '''if''' shouldBe < t.level t.level = shouldBe '''if''' shouldBe < t.right.level t.right.level = shouldBe '''return''' t

Чтобы сохранять баланс дерева необходимо делать <tex>\mathrm{skew}</tex>, <tex>\mathrm{split }</tex> и корректировку уровня <tex>\mathrm{decreaseLevel}</tex> для каждой вершины.

'''functionNode''' delete (x : '''isV''' , t : '''inputNode''': X, the value to delete, and T, the root of the tree from which it should be deleted.) '''output''': T<font color=green>// x {{---}} удаляемый элемент, balancedt {{---}} корень дерева, without the value X. из которого он должен быть удален</font> '''if''' nil(T) '''then'''t == <tex>\varnothing</tex> '''return''' Tt '''else if''' X x > t.value(T) '''then''' t.right(T) := delete(Xx, t.right(T)) '''else if''' X x < t.value(T) '''then''' t.left(T) := delete(Xx, t.left(T))

If we're a leaf, easy, otherwise reduce to leaf case. '''if''' leaf(Tt) '''then''' '''return''' Nil<tex>\varnothing</tex> '''else''' '''if''' nil(t.left(T)) '''then'''== <tex>\varnothing</tex> L :l = successor(Tt) t.right(T) := delete(value(L)l.valuel, t.right(T)) t.value(T) := l.value(L)

L :l = predecessor(Tt) t.left(T) := delete(l.value(L), t.left(T)) t.value(T) := l.value(L) '''end if''' '''end if''' Rebalance the tree<font color=green>// Сбалансируем дерево. Decrease the level of all nodes in this level ifЕсли необходимо, уменьшим поля «уровень» necessary// у вершин на данном уровне, and then и затем skew and и split all nodes in the new level.все вершины на новом уровне</font> T :t = decrease_leveldecreaseLevel(Tt) T :t = skew(Tt) t.right(T) := skew(t.right(T)) '''if not''' nil(t.right(T))<tex> \neq\ \varnothing</tex> t.right(.right(T)) := skew(t.right(.right(T))) '''end if''' T :t = split(Tt) t.right(T) := split(right(T)) '''return''' T '''end function'''  '''function''' decrease_level '''is''' '''input''': T, a tree for which we want to remove links that skip levels. '''output''': T with its level decreasedt. should_be = min(level(left(T)), level(right(T))) + 1 '''if''' should_be < level(T) '''then''' level(T) := should_be '''if''' should_be < level(right(T)) '''then''' level(right(T)) := should_be '''end if''' '''end if''' '''return''' T '''end function'''t

Оценка на высоту деревьев соответствует оценке для красно-черного дерева, <tex>2\cdot \log 2(N)</tex>, так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за <tex>O(\log N)</tex>, потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за <tex>O(h)</tex>. Скорость работы AA - дерева эквивалентна скорости работы красно-черного дерева. В среднем более простые алгоритмы на AA - дерева выполняются быстрее, но так как в краснореализации вместо цвета обычно хранят «уровень» вершины, дополнительные расходы по памяти достигают байта. == См. также ==* [[B-дерево]]* [[Splay-дерево]]* [[АВЛ-дерево]]* [[Декартово дерево]]* [[Красно-черное дерево]] == Источники информации ==* [http://user.it.uu.se/~arnea/ps/simp.pdf Uppsala University {{---}} Balanced searched trees made simple] * [https://en.wikipedia.org/wiki/AA_tree Википедия {{---}} AA -черном дереве делается меньше поворотов, что уравновешивает асимптотикуtree]* [https://habrahabr.ru/post/110212/ Хабрахабр {{---}} AA-Tree или простое бинарное дерево] [[Категория:Дискретная математика и алгоритмы]][[Категория:Структуры данных]][[Категория:Деревья поиска]]