Дерево AA в информатике — это форма сбалансированного дерева, используемая для эффективного хранения и извлечения упорядоченных данных. Деревья АА названы в честь их создателя, шведского ученого-компьютерщика Арне Андерссона. [1]
Деревья AA — это разновидность красно-черного дерева , формы двоичного дерева поиска , которая поддерживает эффективное добавление и удаление записей. В отличие от красно-черных деревьев, красные узлы в дереве AA можно добавлять только как правый дочерний элемент. Другими словами, ни один красный узел не может быть левым дочерним элементом. Это приводит к моделированию дерева 2–3 вместо дерева 2–3–4 , что значительно упрощает операции по обслуживанию. Алгоритмы обслуживания красно-черного дерева должны учитывать семь различных форм, чтобы правильно сбалансировать дерево:
С другой стороны, AA-дереву необходимо учитывать только две формы из-за строгого требования, чтобы только правые ссылки могли быть красными:
В то время как красно-черным деревьям требуется один бит балансирующих метаданных на узел (цвет), деревьям AA требуется O(log(log(N))) бит метаданных на узел в форме целочисленного «уровня». Для деревьев AA справедливы следующие инварианты:
Ссылка, в которой уровень дочернего элемента равен уровню его родителя, называется горизонтальной ссылкой и аналогична красной ссылке в красно-черном дереве. Отдельные правые горизонтальные ссылки разрешены, но последовательные запрещены; все левые горизонтальные ссылки запрещены. Это более строгие ограничения, чем аналогичные ограничения для красно-черных деревьев, в результате чего повторная балансировка AA-дерева процедурно намного проще, чем повторная балансировка красно-черного дерева.
Вставки и удаления могут временно привести к тому, что дерево AA станет несбалансированным (то есть нарушится инварианты дерева AA). Для восстановления баланса необходимы всего две отдельные операции: «перекос» и «разделение». Наклон — это поворот вправо для замены поддерева, содержащего левую горизонтальную ссылку, на поддерево, содержащее вместо этого правую горизонтальную ссылку. Разделение — это поворот влево и повышение уровня для замены поддерева, содержащего две или более последовательные правые горизонтальные ссылки, на поддерево, содержащее на две последовательные правые горизонтальные ссылки меньше. Реализация вставки и удаления с сохранением баланса упрощается за счет использования операций наклона и разделения для изменения дерева только в случае необходимости, вместо того, чтобы заставлять их вызывающую сторону решать, наклонять или разбивать.
На входе функции skew : T — узел, представляющий дерево AA, которое необходимо перебалансировать. выходные данные: еще один узел, представляющий перебалансированное дерево AA. если nil(T) то вернуть Nil else if nil(left(T)) то вернуть T else if level(left(T)) == level(T) тогда поменять местами указатели горизонтальных левых ссылок. L = слева(Т) влево(Т) := вправо(L) вправо(L) := Т вернуть L еще вернуть T end if end функция
Перекос:
Вводится функция разделения : T, узел, представляющий дерево AA, которое необходимо перебалансировать. выходные данные: еще один узел, представляющий перебалансированное дерево AA. если nil(T) то вернуть Nil else if nil(right(T)) или nil(right(right(T))) тогда вернуть T else if level(T) == level(right(right(T))) тогда У нас есть две горизонтальные правые ссылки. Возьмите средний узел, поднимите его и верните. R = вправо (Т) вправо(Т) := влево(R) влево(R) := Т уровень(R) := уровень(R) + 1 вернуть R иначе вернуть T end if end функция
Расколоть:
Вставка начинается с обычной процедуры поиска и вставки в двоичном дереве. Затем, когда стек вызовов раскручивается (при условии рекурсивной реализации поиска), можно легко проверить достоверность дерева и при необходимости выполнить любые повороты. Если возникает горизонтальная левая ссылка, будет выполнен перекос, а если возникнут две горизонтальные правые ссылки, будет выполнено разделение, возможно, с увеличением уровня нового корневого узла текущего поддерева. Обратите внимание: в приведенном выше коде происходит приращение уровня (T). Это приводит к необходимости продолжать проверку достоверности дерева по мере того, как изменения выходят из листьев.
Вводится функция Insert : X — значение, которое нужно вставить, и T — корень дерева, в которое оно будет вставлено. вывод: сбалансированная версия T, включая X. Выполните обычную процедуру вставки двоичного дерева. Установите результат рекурсивного вызова правильному дочернему элементу на случай, если был создан новый узел или изменился корень поддерева. если nil(T) , то Создать новый листовой узел с X. return node(X, 1, Nil, Nil) иначе, если X < значение(T) , то влево(Т) := вставить(X, влево(Т)) иначе, если X > значение (T) , то вправо(Т) := вставить(X, вправо(Т)) end if Обратите внимание, что случай X == value(T) не указан. Как известно, вставка не будет иметь никакого эффекта. Разработчик может желать другого поведения. Выполните перекос, а затем разделите. Условные выражения, определяющие, произойдет ротация или нет, находятся внутри процедур, как указано выше. Т := перекос(Т) Т := разделить(Т) вернуть конечную функцию T
Как и в большинстве сбалансированных бинарных деревьев, удаление внутреннего узла можно превратить в удаление листового узла, заменяя внутренний узел либо его ближайшим предшественником, либо преемником, в зависимости от того, какие из них находятся в дереве, или по прихоти разработчика. Для получения предшественника достаточно просто перейти по одной левой ссылке, а затем по всем остальным правым ссылкам. Аналогично, преемника можно найти, пройдя один раз вправо и влево, пока не будет найден нулевой указатель. Из-за свойства AA всех узлов уровня выше одного, имеющих двух дочерних узлов, узел-преемник или предшественник будет находиться на уровне 1, что делает их удаление тривиальным.
Чтобы сбалансировать дерево, есть несколько подходов. Тот, который описан Андерссоном в его оригинальной статье, является самым простым, и он описан здесь, хотя в реальных реализациях может быть выбран более оптимизированный подход. После удаления первым шагом к сохранению достоверности дерева является понижение уровня всех узлов, чьи дочерние элементы находятся на два уровня ниже их или у которых отсутствуют дочерние узлы. Затем весь уровень необходимо перекосить и разделить. Этот подход получил предпочтение, поскольку, если его концептуально изложить, он состоит из трех легко понимаемых отдельных этапов:
Однако на этот раз нам придется исказить и разделить весь уровень, а не только узел, что усложняет наш код.
Вводится функция удаления : X — значение для удаления и T — корень дерева, из которого оно должно быть удалено. выход: Т, сбалансированный, без значения Х. если ноль(Т) , то вернуть Т иначе, если X > значение (T) , то вправо(Т) := удалить(X, вправо(Т)) иначе, если X < значение (T) , то влево(Т) := удалить(X, влево(Т)) else Если мы лист, легко, иначе сведем к листу. если лист(Т) , то вернуться вправо (Т) иначе, если ноль(левый(T)) тогда L := преемник(T) вправо(Т) := удалить(значение(L), вправо(Т)) значение(Т) := значение(L) еще L := предшественник(Т) влево(T) := удалить(значение(L), влево(T)) значение(Т) := значение(L) конец, если конец, если Сбалансируйте дерево. При необходимости уменьшите уровень всех узлов на этом уровне , а затем наклоните и разделите все узлы на новом уровне. Т := уровень_уменьшения(Т) Т := перекос(Т) вправо(Т) := перекос(вправо(Т)) если не ноль (право (T)) вправо(вправо(Т)) := перекос(вправо(вправо(Т))) конец, если Т := разделить(Т) вправо(Т) := разделение(вправо(Т)) вернуть Тконечная функция
Вводится функция уменьшения_уровня : T, дерево, для которого мы хотим удалить ссылки, пропускающие уровни. вывод: T при этом его уровень снизился. must_be = min(уровень(левый(T)), уровень(правый(T))) + 1 если должно_быть <уровень(Т) , то уровень(T) := должно_быть если должно_быть < уровень(право(Т)) тогда уровень(право(T)) := должно_быть конец, если конец, если вернуть Тконечная функция
Хороший пример удаления с помощью этого алгоритма представлен в статье Андерссона.
Производительность дерева AA эквивалентна производительности красно-черного дерева. Хотя AA-дерево совершает больше вращений, чем красно-черное дерево, более простые алгоритмы, как правило, работают быстрее, и все это уравновешивается, приводя к аналогичной производительности. Красно-черное дерево более стабильно в своей производительности, чем дерево AA, но дерево AA имеет тенденцию быть более плоским, что приводит к немного более быстрому времени поиска. [2]