АА-дерево

Дерево AA в информатике — это форма сбалансированного дерева, используемая для эффективного хранения и извлечения упорядоченных данных. Деревья АА названы в честь их создателя, шведского ученого-компьютерщика Арне Андерссона .

Деревья AA — это разновидность красно-черного дерева , формы двоичного дерева поиска , которая поддерживает эффективное добавление и удаление записей. В отличие от красно-черных деревьев, красные узлы в дереве AA можно добавлять только как правый дочерний элемент. Другими словами, ни один красный узел не может быть левым дочерним элементом. Это приводит к моделированию дерева 2–3 вместо дерева 2–3–4 , что значительно упрощает операции по обслуживанию. Алгоритмы обслуживания красно-черного дерева должны учитывать семь различных форм, чтобы правильно сбалансировать дерево:

С другой стороны, AA-дереву необходимо учитывать только две формы из-за строгого требования, чтобы только правые ссылки могли быть красными:

Балансировка вращений

В то время как красно-черным деревьям требуется один бит балансирующих метаданных на узел (цвет), деревьям AA требуется O(log(log(N))) бит метаданных на узел в форме целочисленного «уровня». Для деревьев AA справедливы следующие инварианты:

1. Уровень каждого листового узла равен единице.
2. Уровень каждого левого дочернего элемента ровно на один меньше уровня его родителя.
3. Уровень каждого правого потомка равен уровню его родителя или на один меньше.
4. Уровень каждого правого внука строго ниже уровня его дедушки и бабушки.
5. Каждый узел уровня выше единицы имеет двух дочерних узлов.

Ссылка, в которой уровень дочернего элемента равен уровню его родителя, называется горизонтальной ссылкой и аналогична красной ссылке в красно-черном дереве. Отдельные правые горизонтальные ссылки разрешены, но последовательные запрещены; все левые горизонтальные ссылки запрещены. Это более строгие ограничения, чем аналогичные ограничения для красно-черных деревьев, в результате чего повторная балансировка AA-дерева процедурно намного проще, чем повторная балансировка красно-черного дерева.

Вставки и удаления могут временно привести к тому, что дерево AA станет несбалансированным (то есть нарушится инварианты дерева AA). Для восстановления баланса необходимы всего две отдельные операции: «перекос» и «разделение». Наклон — это поворот вправо для замены поддерева, содержащего левую горизонтальную ссылку, на поддерево, содержащее вместо этого правую горизонтальную ссылку. Разделение — это поворот влево и повышение уровня для замены поддерева, содержащего две или более последовательные правые горизонтальные ссылки, на поддерево, содержащее на две последовательные правые горизонтальные ссылки меньше. Реализация вставки и удаления с сохранением баланса упрощается за счет использования операций наклона и разделения для изменения дерева только в случае необходимости, вместо того, чтобы заставлять их вызывающую сторону решать, наклонять или разбивать.

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 nil(T) then
        return Nil
    else if nil(left(T)) 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

Перекос:

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

Расколоть:

Вставка

Вставка начинается с обычной процедуры поиска и вставки в двоичном дереве. Затем, когда стек вызовов раскручивается (при условии рекурсивной реализации поиска), можно легко проверить достоверность дерева и при необходимости выполнить любые вращения. Если возникает горизонтальная левая ссылка, будет выполнен перекос, а если возникнут две горизонтальные правые ссылки, будет выполнено разделение, возможно, с увеличением уровня нового корневого узла текущего поддерева. Обратите внимание: в приведенном выше коде происходит приращение уровня (T). Это приводит к необходимости продолжать проверку достоверности дерева по мере того, как изменения всплывают из листьев.

function insert is
    input: X, the value to be inserted, and T, the root of the tree to insert it into.
    output: A balanced version T including X.

    Do the normal binary tree insertion procedure. Set the result of the
    recursive call to the correct child in case a new node was created or the
    root of the subtree changes.
    if nil(T) then
        Create a new leaf node with X.
        return node(X, 1, Nil, Nil)
    else if X < value(T) then
        left(T) := insert(X, left(T))
    else if X > value(T) then
        right(T) := insert(X, right(T))
    end if
    Note that the case of X == value(T) is unspecified. As given, an insert
    will have no effect. The implementor may desire different behavior.

    Perform skew and then split. The conditionals that determine whether or
    not a rotation will occur or not are inside of the procedures, as given
    above.
    T := skew(T)
    T := split(T)

    return T
end function

Удаление

Как и в большинстве сбалансированных бинарных деревьев, удаление внутреннего узла можно превратить в удаление листового узла, заменяя внутренний узел либо его ближайшим предшественником, либо преемником, в зависимости от того, какие из них находятся в дереве, или от прихоти разработчика. Чтобы получить предшественника, нужно просто перейти по одной левой ссылке, а затем по всем остальным правым ссылкам. Аналогично, преемника можно найти, пройдя один раз вправо и влево, пока не будет найден нулевой указатель. Из-за свойства AA всех узлов уровня выше одного, имеющих двух дочерних узлов, узел-преемник или предшественник будет находиться на уровне 1, что делает их удаление тривиальным.

Чтобы сбалансировать дерево, есть несколько подходов. Тот, который описан Андерссоном в его оригинальной статье, является самым простым, и он описан здесь, хотя в реальных реализациях может быть выбран более оптимизированный подход. После удаления первым шагом к сохранению достоверности дерева является понижение уровня всех узлов, чьи дочерние элементы находятся на два уровня ниже их или у которых отсутствуют дочерние узлы. Затем весь уровень необходимо перекосить и разделить. Этот подход получил предпочтение, поскольку, если его концептуально изложить, он состоит из трех легко понимаемых отдельных этапов:

1. Если необходимо, уменьшите уровень.
2. Перекос уровня.
3. Разделите уровень.

Однако на этот раз нам придется исказить и разделить весь уровень, а не только узел, что усложняет наш код.

function delete is
    input: X, the value to delete, and T, the root of the tree from which it should be deleted.
    output: T, balanced, without the value X.
   
    if nil(T) then
        return T
    else if X > value(T) then
        right(T) := delete(X, right(T))
    else if X < value(T) then
        left(T) := delete(X, left(T))
    else
        If we're a leaf, easy, otherwise reduce to leaf case. 
        if leaf(T) then
            return right(T)
        else if nil(left(T)) then
            L := successor(T)
            right(T) := delete(value(L), right(T))
            value(T) := value(L)
        else
            L := predecessor(T)
            left(T) := delete(value(L), left(T))
            value(T) := value(L)
        end if
    end if

    Rebalance the tree. Decrease the level of all nodes in this level if
    necessary, and then skew and split all nodes in the new level.
    T := decrease_level(T)
    T := skew(T)
    right(T) := skew(right(T))
    if not nil(right(T))
        right(right(T)) := skew(right(right(T)))
    end if
    T := split(T)
    right(T) := split(right(T))
    return T
end function

function decrease_level is
    input: T, a tree for which we want to remove links that skip levels.
    output: T with its level decreased.

    should_be = min(level(left(T)), level(right(T))) + 1
    if should_be < level(T) then
        level(T) := should_be
        if should_be < level(right(T)) then
            level(right(T)) := should_be
        end if
    end if
    return T
end function

Хороший пример удаления по этому алгоритму присутствует в статье Андерссона .

Производительность

Производительность дерева AA эквивалентна производительности красно-черного дерева. Хотя AA-дерево совершает больше вращений, чем красно-черное дерево, более простые алгоритмы, как правило, работают быстрее, и все это уравновешивается, приводя к аналогичной производительности. Красно-черное дерево более стабильно в своей производительности, чем дерево AA, но дерево AA имеет тенденцию быть более плоским, что приводит к немного более быстрому времени поиска.

См. также

• Красно-черное дерево
• B-дерево
• АВЛ-дерево
• Дерево козла отпущения

Внешние ссылки

• А. Андерссон. Сбалансированные деревья поиска — это просто
• А. Андерссон. Примечание о поиске в бинарном дереве поиска.
• BSTlib. Архивировано 7 августа 2011 г. в Wayback Machine - библиотеке деревьев AA с открытым исходным кодом для C от trijezdci.
• AA Visual 2007 1.5 — программа Delphi с открытым исходным кодом для обучения древовидным структурам AA.
• Подробное руководство Жюльен Уокер с большим количеством кода, включая практическую реализацию.
• Объектно-ориентированная реализация с тестами
• Исследование поведения производительности структур данных дерева двоичного поиска (страницы 67–75) - сравнение деревьев AA, красно-черных деревьев, трепов, списков пропуска и поразрядных деревьев.
• Реализация Objective-C
• Реализация Python