302
правки
Изменения
Новая страница: «'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [...»
'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое является разновидностью красно-черного дерева с дополнительными ограничениями.
АA-дерево названо по первым буквам имени и фамилия изобретателя, Арне Андерссона, который впервые предложил данную модификацию B-дерева в 1993 году.
{{Определение
|definition='''Уровень вершины''' (англ. ''Level'') - вертикальная высота соответствующей вершины. Уровень листа равен 1.
}}
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка).
== Свойства ==
*Уровень каждого листа равен 1.
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
*Уровень каждого правого ребенка равен или один меньше, чем у его родителя.
*Уровень каждого правого внука строго меньше, чем у его прародителя.
*Каждая вершина с уровнем больше 1 имеет двоих детей.
Для поддержки баланса красно-черного дерева необходимо обрабатывать 7 различных вариантов расположения вершин:
[[Файл: Rb3.png]]
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:
[[Файл: Rb2.png]]
== Балансировка ==
Для балансировки АА-дерева нужно две операции:
#'''Skew(p)''' - устранение левого ребра, соединяющего вершину ''p'' с вершиной того же уровня, что у ''p''.
#'''Split(p)''' -
АA-дерево названо по первым буквам имени и фамилия изобретателя, Арне Андерссона, который впервые предложил данную модификацию B-дерева в 1993 году.
{{Определение
|definition='''Уровень вершины''' (англ. ''Level'') - вертикальная высота соответствующей вершины. Уровень листа равен 1.
}}
В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка).
== Свойства ==
*Уровень каждого листа равен 1.
*Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
*Уровень каждого правого ребенка равен или один меньше, чем у его родителя.
*Уровень каждого правого внука строго меньше, чем у его прародителя.
*Каждая вершина с уровнем больше 1 имеет двоих детей.
Для поддержки баланса красно-черного дерева необходимо обрабатывать 7 различных вариантов расположения вершин:
[[Файл: Rb3.png]]
В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:
[[Файл: Rb2.png]]
== Балансировка ==
Для балансировки АА-дерева нужно две операции:
#'''Skew(p)''' - устранение левого ребра, соединяющего вершину ''p'' с вершиной того же уровня, что у ''p''.
#'''Split(p)''' -
