302
правки
Изменения
Нет описания правки
'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое является разновидностью [[Красно-черное дерево|красно-черного дерева ]] с дополнительными ограничениями.
АA-дерево названо по первым буквам имени и фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию B[[Красно-черное дерево|красно-черного дерева ]] в 1993 году.
{{Определение
|definition='''Уровень вершины''' (англ. ''Level'') {{- --}} вертикальная высота соответствующей вершины. Уровень листа равен 1.
}}
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка).На картинке ниже представлен пример АА-дерева. [[Файл: Exaa.PNG]] На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация о ее уровне. На картинки ниже изображен пример того же дерева, построенного только на основе информации об уровне вершин, горизонтальные ребра обозначают связь вершин одного уровня. [[Файл: Exaa2.PNG]]
== Свойства ==
Свойства АА-дерева:
*Уровень каждого листа равен 1.
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
{{Определение
|definition='''Горизонтальное ребро''' (англ. ''Horizontal edges'') {{- --}} ребро, соединяющее вершины с одинаковым уровнем.
}}
В AA - дереве разрешены правые ребра, не идущие подряд, и запрещены все левые горизонтальные ребра. Эти более жесткие ограничения , аналогичные ограничениям на красно-черных деревьях, приводят к более простой реализации балансировки AA - дерева.
Для балансировки АА-дерева нужны следующие две операции:
'''function''' skew(T)
[[Файл: Skew.png]]
'''function''' split(T)
== Эффективность ==
Скорость работы AA - дерева эквивалентна скорости работы красно-черного дерева. В среднем более простые алгоритмы на AA - дерева выполняются быстрее, но в красно-черном дереве делается меньше поворотов, что уравновешивает асимптотику.
== См. также ==
== Источники информации ==
* [http://user.it.uu.se/~arnea/ps/simp.pdf {{---}} Balanced searched trees made simple]* [https://en.wikipedia.org/wiki/AA_tree {{---}} AA - tree]* [https://habrahabr.ru/post/110212/ {{---}} AA-Tree или простое бинарное дерево]
