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