Изменения

Теперь рассмотрим то же дерево, но с информацией об уровне каждой вершине. Горизонтальные ребра обозначают связи между ребрами одного уровня. [[Файл: Ex10.PNG]] На практике в AA-дереве вместо значения цвета для балансировки дерева в вершине хранится информация только о ее уровне. На картинки ниже изображен пример того же дерева, построенного только на основе информации об уровне вершин, горизонтальные ребра обозначают связь вершин одного уровня.

В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин(получающиеся из соответствующего правила: «одна правая одноуровневая связь (горизонтальное ребро)»: это устранение левой связи на одном уровне и устранение двух правых связей на одном уровне):

[[Файл: Rb2Rb6.png]] [[Файл: Rb7.png]]

Оценка на высоту деревьев соответствует оценке для красно-черного дерева, <tex>2\cdot log 2(N)</tex>, так как AA-дерево сохраняет структуру красно-черного дерева. Следовательно все операции происходят за <tex>O(log N)</tex>, потому что в сбалансированном двоичном дереве поиска почти все операции реализуются за <tex>O(h)</tex>. Скорость работы AA-дерева эквивалентна скорости работы красно-черного дерева, но так как в реализации вместо цвета обычно хранят «уровень» вершины, overhead по памяти достигает байта.