AA tree
-
Описание AA деревьев
- AA деревья — это сбалансированные деревья для эффективного хранения и поиска упорядоченных данных.
- Названы в честь их создателя, шведского ученого Арне Андерссона.
- Являются вариацией красно-черных деревьев, но с ограничениями на добавление красных узлов.
-
Особенности AA деревьев
- Красные узлы могут быть только правыми дочерними элементами.
- Это упрощает операции поддержания баланса, так как требуется только два типа операций.
- Требуют O(log(log(N))) бит метаданных на узел в виде уровня.
-
Инварианты и ограничения
- Уровень каждого листового узла равен 1.
- Уровень левого дочернего элемента на 1 меньше уровня родителя.
- Уровень правого дочернего элемента равен или на 1 меньше уровня родителя.
- Уровень правого внука строго меньше уровня прадеда.
- Каждый узел уровня больше 1 имеет двух детей.
- Горизонтальные связи разрешены только для правых дочерних элементов.
-
Операции поддержания баланса
- Skew — правая ротация для замены левого горизонтального звена на правое.
- Split — левая ротация и увеличение уровня для замены двух или более последовательных правых горизонтальных звеньев.
-
Вставка и удаление
- Вставка начинается с обычной процедуры поиска и вставки.
- При возникновении горизонтального левого звена выполняется skew.
- При возникновении двух горизонтальных правых звеньев выполняется split.
- Удаление внутреннего узла сводится к удалению листового узла.
- После удаления уровень узлов с детьми на два уровня ниже или без детей понижается.
- Затем уровень skewed и split.
-
Производительность
- Производительность AA деревьев эквивалентна красно-черным деревьям.
- AA деревья делают больше вращений, но алгоритмы проще и быстрее.
- Red-black деревья более стабильны, но AA деревья более плоские, что ускоряет поиск.