AA-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''АA-дерево''' (англ. ''AA-Tree'') {{---}} структура данных, представляющая собой сбалансированное [...»)
(нет различий)

Версия 22:10, 19 декабря 2016

АA-дерево (англ. AA-Tree) — структура данных, представляющая собой сбалансированное двоичное дерево поиска, которое является разновидностью красно-черного дерева с дополнительными ограничениями.

АA-дерево названо по первым буквам имени и фамилия изобретателя, Арне Андерссона, который впервые предложил данную модификацию B-дерева в 1993 году.


Определение:
Уровень вершины (англ. Level) - вертикальная высота соответствующей вершины. Уровень листа равен 1.


В отличие от красно-черных деревьев, к одной вершине можно присоединить вершину только того же уровня, только одну и только справа (другими словами, красные вершины могут быть добавлены только в качестве правого ребенка).

Свойства

  • Уровень каждого листа равен 1.
  • Уровень каждого левого ребенка ровно на один меньше, чем у его родителя.
  • Уровень каждого правого ребенка равен или один меньше, чем у его родителя.
  • Уровень каждого правого внука строго меньше, чем у его прародителя.
  • Каждая вершина с уровнем больше 1 имеет двоих детей.

Для поддержки баланса красно-черного дерева необходимо обрабатывать 7 различных вариантов расположения вершин:

Rb3.png

В АА-дереве из-за строгих ограничений необходимо обрабатывать только два вида возможных расположений вершин:

Rb2.png

Балансировка

Для балансировки АА-дерева нужно две операции:

  1. Skew(p) - устранение левого ребра, соединяющего вершину p с вершиной того же уровня, что у p.
  2. Split(p) -