Изменения

'''А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 === '''<tex>\mathrm{Skew(pt)}</tex>''' {{---}} устранение левого горизонтального ребра. Делаем правое вращение, соединяющего вершину чтобы заменить поддерево, содержащее левую горизонтальную связь, на поддерево, содержащее разрешенную правую горизонтальную связь.  '''Node''' skew(t : '''Node''') '''if''' t == <tex>\varnothing</tex> '''preturn'' с вершиной того же уровня' <tex>\varnothing</tex> '''else''' '''if''' t.left == <tex>\varnothing</tex> '''return''' t <font color=green>// Проверяем, что есть ли у нас левое горизонтальное ребро</font> '''else''' '''if''' t.left.level == t.level <font color=green>// Меняем указатель горизонтального левого ребра</font> ''p'return''' Node(t.left, t.left.level, t.left.left, Node(t, t.level, t.left.right, t.right)) '''else''' '''return''' t На рисунке ниже представлен пример работы алгоритма.

'''function''' skew '''is<tex>\mathrm{Split(t)}</tex>'''{{---}} устранение двух последовательных правых горизонтальных ребер. Делаем левое вращение и увеличиваем уровень, чтобы заменить поддерево, содержащее две или более последовательных правильных горизонтальных связи, на вершину, содержащую два поддерева с меньшим уровнем.   '''inputNode'''split(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''' left(T) t.right == NULL <tex>\varnothing</tex> '''thenor'''t.right.right == <tex>\varnothing</tex> '''return''' Tt <font color=green>// Проверяем, один ли уровень у родителя и внука, т.е. существует ли два последовательных правых горизонтальных ребра</font> '''else''' '''if''' t.level(left(T)) == t.right.right.level(T) <font color=green>// Существует два правых горизонтальных ребра. Берем центральную вершину, «поднимаем» ее и возвращаем указатель на нее</font> '''thenreturn''' Swap the pointers of horizontal Node(t.right, t.right.level + 1, Node(t, t.level, t.left links, t.right. L = left(T) left(T) := , t.right(L) .right(L) := T '''return''' L

'''return''' T '''end''' '''if''' '''end''' '''function'''t

#'''Split(p)''' {{---}} устранение двух последовательных правых ребер, которые соединяют вершины с одним уровнем[[Файл: 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 Пример вставки нового элемента (на рис. уровни разделены горизонтальными линиями): [[Файл: Split_rbEx_insert.png]] === Удаление вершины ===Как и в большинстве сбалансированных бинарных деревьев, удаление внутренней вершины можно заменить на удаление листа, если заменить внутреннюю вершину на ее ближайшего «предшественника» или «преемника», в зависимости от реализации. «Предшественник» находится в начале последнего левого ребра, после которого идут все правые ребра. По аналогии, «преемник» может быть найден после одного правого ребра и последовательности левых ребер, пока не будет найден указатель на 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''' split delete(x : '''isV''' , t : '''inputNode''': T, a node representing an AA tree that needs to be rebalanced.) '''output''': Another node representing the rebalanced AA tree. <font color=green>// x {{---}} удаляемый элемент, t {{---}} корень дерева, из которого он должен быть удален</font> '''if''' nil(T) '''then'''t == <tex>\varnothing</tex> '''return''' Nilt '''else''' '''if''' nil(x > t.value t.right= delete(T)) '''or''' nil(x, t.right(right(T))) '''then''' '''return''' T '''else''' '''if''' level(T) == level(right(right(T))) '''then'''x < t.value We have two horizontal right linkst. Take the middle nodeleft = delete(x, elevate it, and return itt. R = right(T) right(T) := left(R) left(R) := T level(R) := level(R) + 1 '''return''' R

'''if''' leaf(t) '''return''' T<tex>\varnothing</tex> '''endelse''' '''if'''t.left == <tex>\varnothing</tex> l = successor(t) t.right = delete(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) '''end functionif'''t.right <tex> \neq\ \varnothing</tex> t.right.right = skew(t.right.right) t = split(t) t.right = split(t.right) '''return''' t Пример удаления вершины (на рис. уровни разделены горизонтальными линиями): [[Файл: Exdelete.png]] == Эффективность ==Оценка на высоту деревьев соответствует оценке для красно-черного дерева, <tex>2\cdot \log 2(N)</tex>, так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за <tex>O(\log N)</tex>, потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за <tex>O(h)</tex>. Скорость работы 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 или простое бинарное дерево] [[Категория:Дискретная математика и алгоритмы]][[Категория:Структуры данных]][[Категория:Деревья поиска]]