 | Эта статья требует дополнительных ссылок для проверки . ( июнь 2011 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Дерево АА в информатике является формой сбалансированного дерева используется для хранения и эффективного извлечения упорядочивания данных. Деревья AA названы в честь их изобретателя Арне Андерссона .
Деревья AA представляют собой разновидность красно-черного дерева , формы двоичного дерева поиска, которое поддерживает эффективное добавление и удаление записей. В отличие от красно-черных деревьев, красные узлы в дереве AA могут быть добавлены только как правые дочерние элементы. Другими словами, никакой красный узел не может быть левым дочерним элементом. Это приводит к моделированию дерева 2-3-4 вместо дерева 2-3-4 , что значительно упрощает операции обслуживания. Алгоритмы обслуживания красно-черного дерева должны учитывать семь различных форм, чтобы правильно сбалансировать дерево:
С другой стороны, дерево AA должно учитывать только две формы из-за строгого требования, что только правые ссылки могут быть красными:
Балансировка вращений [ править ]
В то время как красно-черные деревья требуют одного бита балансирующих метаданных на узел (цвет), деревья AA требуют O (log (log (N))) бит метаданных на узел в виде целочисленного «уровня». Для AA-деревьев имеют место следующие инварианты:
- Уровень каждого листового узла равен единице.
- Уровень каждого левого потомка ровно на единицу меньше, чем у его родителя.
- Уровень каждого правого дочернего элемента равен или на единицу меньше, чем у его родителя.
- Уровень каждого правого внука строго ниже, чем у его прародителя.
- Каждый узел уровня выше одного имеет двух дочерних узлов.
Ссылка, в которой уровень дочернего элемента равен уровню его родителя, называется горизонтальной ссылкой и аналогична красной ссылке в красно-черном дереве. Разрешены отдельные правые горизонтальные ссылки, но запрещены последовательные; все левые горизонтальные ссылки запрещены. Это более строгие ограничения, чем аналогичные ограничения для красно-черных деревьев, в результате чего повторная балансировка дерева AA процедурно намного проще, чем повторная балансировка красно-черного дерева.
Вставки и удаления могут временно привести к тому, что дерево AA станет несбалансированным (то есть нарушит инварианты дерева AA). Для восстановления баланса необходимы всего две различные операции: «перекос» и «разбиение». Наклон - это поворот вправо для замены поддерева, содержащего левую горизонтальную ссылку, на поддерево, содержащее вместо этого правую горизонтальную ссылку. Разделение - это левый поворот и повышение уровня для замены поддерева, содержащего две или более последовательных правых горизонтальных ссылки, одной, содержащей на две последовательных правых горизонтальных ссылки меньше. Реализация вставки и удаления с сохранением баланса упрощается за счет использования операций перекоса и разделения для изменения дерева только в случае необходимости, вместо того, чтобы заставлять их вызывающие стороны решать, перекосить или разделить.
Функция перекоса является ввод: Т, узел , представляющий дерево АА , который должен быть балансировку. output: Еще один узел, представляющий ребалансированное дерево AA. если nil (T), то вернуть Nil else if nil (left (T)) затем вернуть T else if level (left (T)) == level (T), затем поменять местами указатели горизонтальных левых ссылок. L = слева (T) слева (T): = справа (L) справа (L): = T return L else return T end if end функция
Перекос: 
Функция сплит является ввод: Т, узел , представляющий дерево АА , который должен быть балансировку. output: Еще один узел, представляющий ребалансированное дерево AA. если nil (T), то вернуть Nil else if nil (right (T)) или nil (right (right (T))), затем вернуть T else if level (T) == level (right (right (T))), то У нас есть две горизонтальные правые ссылки. Возьмите средний узел, поднимите его и верните. R = право (T) справа (T): = слева (R) left (R): = T уровень (R): = уровень (R) + 1 return R else return T end if end функция
Расколоть: 
Вставка [ править ]
Вставка начинается с обычной процедуры поиска и вставки в двоичное дерево. Затем, когда стек вызовов раскручивается (при условии рекурсивной реализации поиска), легко проверить правильность дерева и при необходимости выполнить любые вращения. Если возникает горизонтальная левая ссылка, выполняется перекос, а если возникают две горизонтальные правые связи, выполняется разделение, возможно, увеличивая уровень нового корневого узла текущего поддерева. Обратите внимание, что в приведенном выше коде приращение уровня (T). Это заставляет продолжать проверку достоверности дерева, поскольку модификации всплывают из листьев.
Функция вставки является ввод: Х, значение , которое должно быть вставлено, и Т, корень дерева , чтобы вставить его в. выход: сбалансированная версия T, включая X. Выполните обычную процедуру вставки двоичного дерева. Установите результат рекурсивного вызова для правильного дочернего элемента в случае создания нового узла или изменения корня поддерева. if nil (T), то создайте новый листовой узел с X. return node (X, 1, Nil, Nil) иначе, если X <value (T), то left (T): = вставить (X, left (T)) иначе, если X> значение (T), то right (T): = вставить (X, right (T)) end if Обратите внимание, что случай X == value (T) не указан. Как указано, вставка не будет иметь никакого эффекта. Разработчик может пожелать другого поведения. Выполните перекос, а затем разделите. Условные выражения, которые определяют, произойдет ли ротация или нет, находятся внутри процедур, как указано выше. T: = перекос (T) T: = разделить (T) вернуть функцию конца T
Удаление [ править ]
Как и в большинстве сбалансированных бинарных деревьев, удаление внутреннего узла может быть превращено в удаление листового узла путем замены внутреннего узла на его ближайшего предшественника или преемника, в зависимости от того, какие из них находятся в дереве, или от прихоти разработчика. Для получения предшественника нужно просто перейти по одной левой ссылке, а затем по всем оставшимся правым ссылкам. Точно так же преемника можно найти, пройдя один раз вправо и влево, пока не будет найден нулевой указатель. Из-за свойства AA всех узлов уровня выше одного, имеющих двух дочерних узлов, узел-преемник или предшественник будет на уровне 1, что делает их удаление тривиальным.
Чтобы перебалансировать дерево, есть несколько подходов. Вариант, описанный Андерссоном в его оригинальной статье, является самым простым, и он описан здесь, хотя в реальных реализациях может быть выбран более оптимизированный подход. После удаления первым шагом к поддержанию достоверности дерева является понижение уровня всех узлов, чьи дочерние элементы находятся на два уровня ниже их, или у которых отсутствуют дочерние элементы. Затем весь уровень необходимо перекосить и разделить. Этот подход был одобрен, потому что, когда он концептуально изложен, он включает три легко понимаемых отдельных шага:
- При необходимости уменьшите уровень.
- Наклоните уровень.
- Разделите уровень.
Однако на этот раз мы должны перекосить и разделить весь уровень, а не только узел, что усложняет наш код.
Функция удаления является ввод: Х, значение для удаления, и Т, корень дерева , из которого она должна быть удалена. выход: T, симметричный, без значения X. если nil (T), то вернуть T иначе, если X> значение (T), то right (T): = delete (X, right (T)) иначе, если X <значение (T), то left (T): = delete (X, left (T)) else Если мы лист, то просто, в противном случае сведем к листу. если лист (T), то вернуться вправо (T) иначе, если nil (left (T)), то L: = преемник (T) вправо (T): = удалить (значение (L), вправо (T)) значение (T): = значение (L) еще L: = предшественник (T) left (T): = delete (значение (L), left (T)) значение (T): = значение (L) конец, если конец, если Восстановите баланс дерева. При необходимости уменьшите уровень всех узлов на этом уровне , а затем наклоните и разделите все узлы на новом уровне. T: = уменьшение_уровня (T) T: = перекос (T) right (T): = наклон (вправо (T)) если не ноль (справа (T)) right (right (T)): = наклон (right (right (T))) конец, если T: = разделить (T) right (T): = разделить (right (T)) вернуть Tконечная функция
функция reduce_level является входной: T, дерево, из которого мы хотим удалить ссылки, пропускающие уровни. вывод: T с его уровнем уменьшился. should_be = min (уровень (слева (T)), уровень (справа (T))) + 1 если should_be <level (T), то level (T): = should_be если should_be <level (right (T)), то уровень (справа (T)): = should_be конец, если конец, если вернуть Tконечная функция
Хороший пример удаления с помощью этого алгоритма представлен в статье Андерссона .
Производительность [ править ]
Производительность дерева AA эквивалентна производительности красно-черного дерева. В то время как дерево AA совершает больше вращений, чем красно-черное дерево, более простые алгоритмы имеют тенденцию быть быстрее, и все это уравновешивается, чтобы привести к аналогичной производительности. Красно-черное дерево более стабильно по своим характеристикам, чем дерево AA, но дерево AA имеет тенденцию быть более плоским, что приводит к немного более быстрому поиску. [1]
См. Также [ править ]
Ссылки [ править ]
- ^ «Исследование поведения производительности структур данных дерева двоичного поиска (страницы 67-75)» (PDF) . Архивировано из оригинального (PDF) 27 марта 2014 года . Проверено 17 октября 2010 .
Внешние ссылки [ править ]
- А. Андерссон. Сбалансированные деревья поиска стали проще
- А. Андерссон. Замечание о поиске в двоичном дереве поиска
- BSTlib - Древовидная библиотека AA с открытым исходным кодом для C от trijezdci
- AA Visual 2007 1.5 - программа на Delphi с открытым исходным кодом для обучения древовидным структурам AA
- Подробное руководство Julienne Walker с большим количеством кода, включая практическую реализацию
- Объектно-ориентированная реализация с тестами
- Исследование поведения производительности структур данных дерева двоичного поиска (страницы 67-75) - Сравнение деревьев AA, красно-черных деревьев, переходов, списков пропусков и оснований системы счисления
- Реализация Objective-C
- Реализация Python
