Войти
Дерево AAв информатике - это форма сбалансированного дерева, используемая для эффективного хранения и извлечения упорядоченных данных. Деревья AA названы в честь их изобретателя.
AA-деревья являются разновидностью красно-черного дерева, формы двоичного дерева поиска, которое поддерживает эффективное добавление и удаление записей. В отличие от красно-черных деревьев, красные узлы в дереве AA можно добавить только как правый дочерний элемент. Другими словами, никакой красный узел не может быть левым дочерним элементом. Это приводит к моделированию дерева 2-3 вместо дерева 2-3-4, что значительно упрощает операции обслуживания. Алгоритмы обслуживания красно-черного дерева должны учитывать семь различных форм, чтобы правильно сбалансировать дерево:
АА-дерево, с другой стороны, должно учитывать только две формы из-за строгого требования, чтобы только правые ссылки могли быть красными:
В то время как красно-черные деревья требуют одного бита балансировки метаданных на узел (цвет), деревья AA требуют O (log (log (N))) бит метаданных на узел в форме целочисленного «уровня». Для деревьев AA выполняются следующие инварианты:
Ссылка, где уровень дочернего элемента равен уровню его родительского элемента, называется горизонтальной ссылкой и аналогична красной ссылке в красно-черном дереве. Разрешены отдельные правые горизонтальные ссылки, но запрещены последовательные; все левые горизонтальные ссылки запрещены. Это более строгие ограничения, чем аналогичные ограничения для красно-черных деревьев, в результате чего повторная балансировка дерева AA процедурно намного проще, чем повторная балансировка красно-черного дерева.
Вставки и удаления могут временно привести к тому, что дерево AA станет несбалансированным (то есть нарушит инварианты дерева AA). Для восстановления баланса нужны всего две различные операции: «перекос» и «разбиение». Наклон - это поворот вправо для замены поддерева, содержащего левую горизонтальную ссылку, на поддерево, содержащее правую горизонтальную ссылку. Разделение - это левый поворот и повышение уровня для замены поддерева, содержащего две или более последовательных правых горизонтальных ссылки, одной, содержащей на две последовательных правых горизонтальных ссылки меньше. Реализация вставки и удаления с сохранением баланса упрощается за счет использования операций перекоса и разделения для изменения дерева только в случае необходимости, вместо того, чтобы заставлять их вызывающие стороны решать, перекосить или разделить.
functionskew isinput:T, узел, представляющий дерево AA, которое необходимо перебалансировать. вывод:Другой узел, представляющий перебалансированное дерево AA. ifnil (T) затемвернутьNil else ifnil (left (T)) тогдаreturnT else iflevel (left (T)) == level (T) thenПоменять местами указатели горизонтальных левых ссылок. L = влево (T) влево (T): = вправо (L) вправо (L): = T returnL elsereturnT конец ifend function
Skew:
functionsplit isinput:T, узел, представляющий дерево AA, которое необходимо перебалансировать. вывод:Другой узел, представляющий перебалансированное дерево AA. ifnil (T) затемвернутьNil else ifnil (right (T)) илиnil ( right (right (T))) затемreturnT else iflevel (T) == level (right (right (T))) thenУ нас есть две горизонтальные правые ссылки. Возьмите средний узел, поднимите его и верните обратно. R = вправо (T) вправо (T): = влево (R) влево (R): = T уровень (R): = уровень (R) + 1 returnR elsereturnT end ifend function
Split:
Вставка начинается с обычной процедуры поиска и вставки в двоичное дерево. Затем, когда стек вызовов раскручивается (при условии рекурсивной реализации поиска), легко проверить правильность дерева и выполнить любые вращения по мере необходимости. Если возникает горизонтальная левая ссылка, будет выполнено перекос, а если возникнут две горизонтальные правые связи, будет выполнено разделение, возможно, увеличив уровень нового корневого узла текущего поддерева. Обратите внимание, что в приведенном выше коде приращение уровня (T). Это заставляет продолжать проверку достоверности дерева, поскольку модификации всплывают из листьев.
functioninsert isinput:X, значение, которое нужно вставить, и T, корень дерева, в которое его нужно вставить. вывод:Сбалансированная версия T, включая X. Выполните обычную процедуру вставки двоичного дерева. Задайте результат рекурсивного вызова правильному дочернему элементу в случае создания нового узла или изменения корня поддерева. ifnil (T) thenСоздать новый листовой узел с X. returnnode (X, 1, Nil, Nil) else ifX < value(T) затемleft (T): = insert (X, left (T)) else ifX>value (T) thenright (T): = insert (X , right (T)) end ifОбратите внимание, что случай X == value (T) не указан. Как указано, вставка не будет иметь никакого эффекта. Разработчик может пожелать другого поведения. Выполните перекос, а затем разделите. Условные выражения, которые определяют, произойдет ли ротация, находятся внутри процедур, как указано выше. T: = skew (T) T: = split (T) return Tend function
Как и в большинстве сбалансированных двоичных деревьев, удаление внутреннего узла может быть превращен в удаление листового узла путем замены внутреннего узла либо его ближайшим предшественником, либо преемником, в зависимости от того, какие из них находятся в дереве, или от прихоти разработчика. Чтобы получить предшественника, достаточно перейти по одной левой ссылке, а затем по всем оставшимся правым ссылкам. Точно так же преемника можно найти, пройдя один раз вправо и влево, пока не будет найден нулевой указатель. Из-за свойства AA всех узлов уровня выше одного, имеющих двух дочерних узлов, узел-преемник или предшественник будет на уровне 1, что делает их удаление тривиальным.
Чтобы восстановить баланс дерева, есть несколько подходов. Вариант, описанный Андерссоном в его исходной статье, является самым простым, и он описан здесь, хотя в реальных реализациях может быть выбран более оптимизированный подход. После удаления первым шагом к поддержанию достоверности дерева является снижение уровня всех узлов, чьи дочерние элементы находятся на два уровня ниже их, или у которых отсутствуют дочерние элементы. Затем весь уровень нужно перекосить и разделить. Этот подход получил поддержку, потому что в концептуальном плане он состоит из трех легко понимаемых отдельных шагов:
Однако на этот раз мы должны перекосить и разделить весь уровень, а не только узел, что усложняет наш код.
functiondelete isinput:X, значение для удаления и T, корень дерева, из которого оно должно быть удалено. вывод:T, сбалансированный, без значения X. еслиnil (T) , товернуть T иначе, еслиX>значение (T ) , затемвправо (T): = delete (X, right (T)) иначе, еслиX < value(T) , товлево (T): = delete (X, left (T)) elseЕсли мы лист, то просто, иначе сведем к листу. еслилист (T) , тоreturn right (T) else ifnil (left (T)) тогдаL: = преемник ( T) справа (T): = удалить (значение (L), справа (T)) значение (T): = значение (L) иначеL: = предшественник (T) слева (T): = delete (value (L), left (T)) value (T): = value (L) end ifend ifПеребалансируйте дерево. При необходимости уменьшите уровень всех узлов на этом уровне, а затем наклоните и разделите все узлы на новом уровне. T: = уменьшение_уровня (T) T: = наклон (T) вправо (T): = наклон (вправо (T)) , если неноль (вправо (T)) вправо (вправо (T)): = skew (right (right (T))) end ifT: = split (T) right (T): = split (right (T)) return T end function
functionreduce_level isinput:T, дерево, для которого мы хотим удалить ссылки, пропускающие уровни. вывод:T с пониженным уровнем. should_be = min (level (left (T)), level (right (T))) + 1 еслиshould_be, тоlevel (T): = should_be ifshould_be < level(right(T)) thenlevel (right (T)): = should_be end ifend ifreturn T end function
Хороший пример удаления с помощью этого алгоритма представлен в статье Андерссона.
Производительность дерева AA эквивалентна производительности красно-черного дерева. В то время как дерево AA делает больше вращений, чем красно-черное дерево, более простые алгоритмы, как правило, работают быстрее, и все это уравновешивается, чтобы привести к аналогичной производительности. Красно-черное дерево более стабильно по своим характеристикам, чем дерево AA, но дерево AA имеет тенденцию быть более плоским, что приводит к немного более быстрому поиску.
