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

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

    Про 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 проект с визуализацией АА-дерева и исходным кодом.

    Статья в википедии.
    Поделиться публикацией

    Комментарии 10

    • НЛО прилетело и опубликовало эту надпись здесь
        0
        Я в своё время придумал вариант AVL дерева на два простых случая. Критерий балансировки почти классический: |h1 — h2| <= 1 плюс если разница высот равна 1, то перекос допускается только в стороны, т.е. для левого потомка фактическое правило: 0 <= h1 — h2 <= 1, а для правого потомка: -1 <= h1 — h2 <= 0. Там, правда, вылезает log2(n) сложность из-за того, что после вращений может поменяться ориентация узлов. Но для олимпиад было самое то — всего два случая (на левое и правое вращение) и т.к. алгоритм знал только я, тестов на этот квадрат не было :)
          0
          Можно дать определение уровня вершины? На втором рисунке у правого дерева листья A, B, X, судя по сказанному выше, они должны быть все первого уровня, но нарисованы, как будто у них они не одинаковы.
            0
            Уровень вершины — это некая вспомогательная величина, которая есть у каждой вершины и листовая вершина получает вначале в качестве 1. Далее уровень меняется при балансировке таким образом, что всегда в АА-дереве две вершины одного уровня связаны только правой связью.

            Это и есть определение «уровня вершины», это понятие нельзя выразить в виде высоты или еще как-то.

            Это как бы переменная условия-инварианта.

            На рисунке после выполнения операции split:

            R.level = X.level + 1 = T.level + 1 = A.level + 2 = B.level + 2

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

            0
            Конечно, +1 за статью. Но вот смущает… .level это то, что уменьшается постоянно?

              0
              Эврика. Я увидел Inc. Но только после чтения Википедии. Паскаль, конечно, многим хорош. Присваивания вот в тексте легко искать: вместо =[^=], как в Си ищем :=. Но вот, надо бы этой возможностью документации пользоваться и всё же вместо Inc и Dec писать P^.level :=.

              Но это так, бурчание. А по теме. Раз level — это отдельный счётчик, то нужно учитывать, что его нельзя сделать битовым полем в одном из указателей, как это допускают красно-чёрные деревья или деревья AVL. В итоге, получаем накладные расходы на объём хранимой информации в памяти её чтение и запись.

              А тут довольно много обращений в память происходит. Плюс ещё есть операция копирования содержимого узлов. А если ключ большой?

              AVL-деревья с этой точки зрения, как мне кажется, гораздо симпатичнее. Там и доступы в память оптимальнее и поворот вообще нужен только один.
                0
                Накладные расходы на запись/чтение level с лихвой компенсируются простотой кода — то есть малыми размерами — то есть скоростью. Я для интереса нашел реализацию AVL на Delphi и сравнивал, AVL отставал на 10-20%. Понимаю, что утверждение, что АА-дерево всегда быстрее AVL требует более строгих тестов, тем не менее в моих тестах оно было быстрее.

                level это дополнительные 4 байта на вершину. Но, вообще говоря, не думаю, что в реальности можно столкнуться с деревьями, глубина которых превышает 256, ведь тогда кол-во элементов будет примерно 2^256 (что довольно много :-) ). Так что можно ограничиться одним байтом.

                Что касается копирования узлов — его можно избежать, введя указатель на parent и меняя исходные ссылки на вершины (а не сами вершины).

                Я буду рад сравнить скорость Вашей самой быстрой реализации AVL-дерева с AA-деревом.

                  0
                  Ок. Я как раз хочу нечто такое написать на Хабре. Только это будет не скоро. Недели через 3. Но я в todo'шку себе занесу это соревнование.

                  А ещё мне не кажется, что AA-код сильно проще. AVL-деревья реализуют обычно, описывая 4 разных поворота, но на самом деле их всего 2, с параметром. Что код упрощает существенно.
              +1
              читаем мы теги, читаем.
                0
                О, Delphi! Соскучился я по крышечкам ^

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое