Pull to refresh

AA-Tree или простое бинарное дерево

Website development *
Тема бинарных деревьев уже обсуждалась на хабре (здесь и здесь).

Про AA-дерево было сказано, что «из-за дополнительного ограничения операции реализуются проще чем у красно-черного дерева (за счет уменьшения количества разбираемых случаев)».

Мне, однако, кажется, что AA-дерево заслуживает отдельной статьи.

Почему?

Потому, что фактически это самое быстрое (или одно из самых быстрых) бинарное дерево с простой реализацией.

Я оставлю за рамками данной статьи рассмотрение алгоритмов вставки и удаления в AVL и красно-черное дерево, но их реализация, как правило, не тривиальна. Почему?

Как известно, основная проблема бинарного дерева — его балансировка, то есть противодействие вырождению в обычный связный список. Обычно при балансировке дерева возникает много вариантов взаимного расположения вершин, каждый из которых нужно учесть в алгоритме отдельно.

AA-дерево было придумано Arne Andersson, который решил, что для упрощения балансировки дерева нужно ввести понятие уровень (level) вершины. Если представить себе дерево растущим сверху вниз от корня (то есть «стоящим на листьях»), то уровень любой листовой вершины будет равен 1. В своей работе Arne Andersson приводит простое правило, которому должно удовлетворять AA-дерево:

К одной вершине можно присоединить другую вершину того же уровня но только одну и только справа.

(В своей статье автор AA-дерева использует немного другую терминологию, связанную с 2-3 деревьями, но суть не меняется).

Таким образом, введенное понятие уровня вершины не всегда совпадает с реальной высотой вершины (расстояния от земли), но дерево сохраняет балансировку при следовании правилу «одна правая связь на одном уровне».

Для балансировки АА-дерева нужно всего 2 (две) операции.

Нетрудно их понять из правила «одна правая одноуровневая связь»: это устранение левой связи на одном уровне и устранение двух правых связей на одном уровне.

Это операции названы в оригинальной работе skew и split, соответственно. На приведенных рисунках горизонтальная стрелка обозначает связь между вершинами одного уровня, а наклонная (вертикальная) — между вершинами разного уровня.

skew, устранение левой связи на одном уровне
image

split, устранение двух правых связей на одном уровне
image

Давайте посмотрим как выглядит вставка и удаление в АА-дерево. Для упрощения реализации введем понятие вершины bottom ("земля"). Ее уровень всегда 0 и ее левая и правая связь указывают на нее же. Все листовые вершины ссылаются на bottom вместо того, чтобы хранить 0 в ссылке.

В рамках недель Delphi на Хабре, исходный код будет в виде псевдокода, похожего на Delphi (для влюбленных в кофе C++: операция P^.x в Delphi эквивалентна P->x, var означает что переменная передается по ссылке, а не по значению, т.е. при изменении меняется внешняя переменная).

Определим вершину AA-дерева.

  PNode = ^TNode;
  TNode = packed record
    left, right: PNode;
    level: integer; // уровень; 1 у листьев
    key: pointer; // ключ, данные связанные с вершиной
  end;
 


Вставка элемента newkey проще всего выглядит в рекурсивной реализации.

procedure NodeInsert(var P: PNode; newkey: pointer);
begin
  if P = bottom then begin // достигли "дна" - создаем новую вершину
    new(P);
    P^.left := bottom;
    P^.right := bottom;
    P^.level := 1;
    P^.key := newkey;
  end else begin
    if newkey < P^.key then
      NodeInsert(P^.left, newkey)
    else if  newkey > P^.key then 
      NodeInsert(P^.right, newkey)
    else begin
      P^.key := newkey;
      exit;
    end;
    Skew(P);
    Split(P);
  end;
end;
 


Для вставки в дерево ключа newkey вызываем NodeInsert(root, newkey). Спускаемся от корня вниз по дереву, сравнивая ключи; вставляем; идем вверх и выполняем балансировку: skew и split для каждой вершины.

Удаление немного хитрее.

procedure NodeDelete(var P:PNode; newkey: pointer);
begin
 
  if P <> bottom then begin
 
  // 1. спускаемся вниз и запоминаем last и deleted
    last := P;
    if Compare(newkey, P) < 0 then  // newkey < key
      NodeDelete(P^.left, newkey)
    else begin
      deleted := P;
      NodeDelete(P^.right, newkey);
    end;
 
  // 2. удаляем элемент, если найден
    if (= last) and (deleted <> bottom) and (newkey == deleted^.key) then begin
      deleted^.key := P^.key;
      deleted := bottom;
      P := P^.right;
      delete last;
    end else if (P^.left.level < P^.level - 1) or (P^.right.level < P^.level - 1) then begin
   // 3. выполняем балансировку при движении вверх
      Dec(P^.level);
      if P^.right.level > P^.level then P^.right.level := P^.level;
      Skew(P);
      Skew(P^.right);
      Skew(P^.right^.right);
      Split(P);
      Split(P^.right);
    end;
  end;
 
end;
 

Используются две вспомогательные переменные — deleted и last. При спуске вниз по дереву (как и при вставке) сравниваются ключи вершин с удаляемым ключом. Если ключ вершины меньше удаляемого, то переходим к левой ссылке, иначе — к правой (т.е. к правой переходим даже при совпадении ключей). В last заносится каждая проходимая вершина, а в deleted — только та, где «свернули направо».

Когда достигнуто «дно» дерева, deleted указывает на вершину, в которой находится удаляемый ключ (если она есть в дереве), а last — на вершину, которую следует удалить (это может быть одна и та же вершина). Ключ переносится из last в deleted и вершина last удаляется.

Далее выполняется балансировка — нужно выполнить 3 skew и 2 split.

Реализация skew и split банальна.

// поменять местами _содержимое_ записей с вершинами (не указатели)
procedure Swap(P1, P2: PNode);
var
  tmp: TNode;
begin
  tmp := P1^;
  P1^ := P2^;
  P2^ := tmp;
end;
 
procedure Skew(T: PNode);
var
  L: PNode;
begin
  L := T^.left;
  if T^.level = L^.level then begin
    Swap(T, L); // теперь T ==> L, L ==> T
    L^.left := T^.right; // т.е. T.left = L.right
    T^.right := L; // т.е. L.right = T
  end;
end;
 
procedure Split(T: PNode);
var
  R: PNode;
begin
  R := T^.right;
  if T^.level = R^.right^.level then begin
    Swap(T, R); // теперь T ==> R, R ==> T
    R^.right := T^.left;
    T^.left := R;
    Inc(T^.level);
  end;
end;
 


Фактически, приведенный псевдокод достаточен для создания реализации АА-дерева (добавить лишь «мелочи» вроде модификации корня дерева (root) и пр.).

Некоторые полезные ссылки.

Реализация AA-дерева на C.

Замечательный апплет, в котором можно поиграться с различными видами деревьев (в том числе и с АА-деревьями).

Delphi проект с визуализацией АА-дерева и исходным кодом.

Статья в википедии.
Tags:
Hubs:
Total votes 42: ↑39 and ↓3 +36
Views 17K
Comments 10
Comments Comments 10