302
правки
Изменения
Нет описания правки
'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [[Дерево поиска, наивная реализация|двоичное дерево поиска]], которое является разновидностью красно-черного дерева с дополнительными ограничениями.
АA-дерево названо по первым буквам имени и фамилия фамилии изобретателя, Арне Андерссона, который впервые предложил данную модификацию B-дерева в 1993 году.
{{Определение
== Балансировка ==
Для балансировки АА-дерева нужно две операции:
#'''Skew(p)''' {{- --}} устранение левого ребра, соединяющего вершину ''p'' с вершиной того же уровня, что у ''p''. [[Файл: Skew.png]] '''function''' skew '''is''' '''input''': T, a node representing an AA tree that needs to be rebalanced. '''output''': Another node representing the rebalanced AA tree. '''if''' T == NULL '''then''' '''return''' NULL '''else''' '''if''' left(T) == NULL '''then''' '''return''' T '''else''' '''if''' level(left(T)) == level(T) '''then''' Swap the pointers of horizontal left links. L = left(T) left(T) := right(L) right(L) := T '''return''' L '''else''' '''return''' T '''end''' '''if''' '''end''' '''function''' #'''Split(p)''' {{---}} устранение двух последовательных правых ребер, которые соединяют вершины с одним уровнем. [[Файл: Split_rb.png]] '''function''' split '''is''' '''input''': T, a node representing an AA tree that needs to be rebalanced. '''output''': Another node representing the rebalanced AA tree. '''if''' nil(T) '''then''' '''return''' Nil '''else''' '''if''' nil(right(T)) '''or''' nil(right(right(T))) '''then''' '''return''' T '''else''' '''if''' level(T) == level(right(right(T))) '''then''' We have two horizontal right links. Take the middle node, elevate it, and return it. R = right(T) right(T) := left(R) left(R) := T level(R) := level(R) + 1 '''return''' R '''else''' '''return''' T '''end''' '''if''' '''end function'''
