Дерево танго

Дерево танго — это тип двоичного дерева поиска, предложенный Эриком Д. Демейном , Дайоном Хармоном, Джоном Яконо и Михаем Патрашку в 2004 году. Он назван в честь Буэнос-Айреса , символом которого является танго .

Это онлайн- дерево двоичного поиска, которое обеспечивает $O(\log \log n)$ соотношение конкурентоспособности относительно автономного оптимального бинарного дерева поиска , при этом используется только $O(\log \log n)$ дополнительные биты памяти на узел. Это улучшило предыдущий наиболее известный коэффициент конкурентоспособности, который был $O(\log n)$.

Структура

Деревья танго работают путем разделения двоичного дерева поиска на набор предпочтительных путей , которые сами хранятся во вспомогательных деревьях (поэтому дерево танго представляется как дерево деревьев).

Справочное дерево

Чтобы построить дерево танго, мы моделируем полное двоичное дерево поиска, называемое ссылочным деревом , которое представляет собой просто традиционное двоичное дерево поиска, содержащее все элементы. Это дерево никогда не появляется в реальной реализации, но является концептуальной основой следующих частей дерева танго.

В частности, высота опорного дерева равна ⌈log ₂ ( n +1)⌉. Это соответствует длине самого длинного пути и, следовательно, размеру самого большого вспомогательного дерева. Поддерживая разумную сбалансированность вспомогательных деревьев , их высоту можно ограничить величиной O (log log n ). Это источник гарантий производительности алгоритма.

Предпочтительные пути

Предпочтительные пути дерева. Предпочтительным дочерним элементом каждого узла является его последний посещенный дочерний узел.

Во-первых, мы определяем для каждого узла его предпочтительный дочерний элемент , который неформально является самым последним посещенным дочерним элементом при традиционном поиске в дереве двоичного поиска. Более формально, рассмотрим поддерево T с корнем в p и потомками l (слева) и r (справа). Мы устанавливаем r как предпочтительный дочерний элемент p, если последний доступный узел в T находится в поддереве с корнем в r , и l как предпочтительный дочерний элемент в противном случае. Обратите внимание: если последний доступный узел T — это сам p , то l является предпочтительным дочерним элементом по определению.

Предпочтительный путь определяется начиная с корня и следуя по предпочтительным дочерним узлам до достижения конечного узла. Удаление узлов на этом пути разбивает оставшуюся часть дерева на несколько поддеревьев, и мы выполняем рекурсию для каждого поддерева (формируя предпочтительный путь из его корня, который разбивает поддерево на большее количество поддеревьев).

Вспомогательные деревья

Чтобы представить предпочтительный путь, мы сохраняем его узлы в сбалансированном двоичном дереве поиска , а именно в красно-черном дереве . Для каждого нелистового узла n в предпочтительном пути P у него есть непредпочтительный дочерний узел c , который является корнем нового вспомогательного дерева. Мы присоединяем корень этого другого вспомогательного дерева ( c ) к n в P , связывая таким образом вспомогательные деревья вместе. Мы также дополняем вспомогательное дерево, сохраняя в каждом узле минимальную и максимальную глубину (то есть глубину в опорном дереве) узлов в поддереве под этим узлом.

Алгоритм

Идет поиск

Для поиска элемента в дереве танго мы просто имитируем поиск в дереве ссылок. Мы начинаем с поиска предпочтительного пути, соединенного с корнем, который моделируется путем поиска во вспомогательном дереве, соответствующем этому предпочтительному пути. Если вспомогательное дерево не содержит искомого элемента, поиск завершается на родителе корня поддерева, содержащего искомый элемент (начало другого предпочтительного пути), поэтому мы просто продолжаем поиск этого предпочтительного пути во вспомогательном дереве. и так далее.

Обновление

Чтобы сохранить структуру дерева танго (вспомогательные деревья соответствуют предпочтительным путям), мы должны выполнять некоторую работу по обновлению всякий раз, когда предпочтительные дочерние элементы изменяются в результате поиска. При изменении предпочтительного дочернего элемента верхняя часть предпочтительного пути отделяется от нижней части (которая становится собственным предпочтительным путем) и снова присоединяется к другому предпочтительному пути (который становится новой нижней частью). Чтобы сделать это эффективно, мы определим операции вырезания и соединения для наших вспомогательных деревьев.

Присоединиться

Наша операция соединения объединит два вспомогательных дерева, если они обладают свойством, согласно которому верхний узел одного (в ссылочном дереве) является дочерним элементом нижнего узла другого (по сути, соответствующие предпочтительные пути могут быть объединены). Это будет работать на основе операции конкатенации красно-черных деревьев, которая объединяет два дерева, если они обладают свойством, согласно которому все элементы одного меньше всех элементов другого, и операции разделения , которая делает обратное. Обратите внимание, что в дереве ссылок существуют два узла в верхнем пути, так что узел находится в нижнем пути тогда и только тогда, когда его ключ-значение находится между ними. Теперь, чтобы соединить нижний путь с верхним путем, мы просто разделяем верхний путь между этими двумя узлами, затем объединяем два полученных вспомогательных дерева по обе стороны от вспомогательного дерева нижнего пути, и у нас есть окончательное объединенное вспомогательное дерево.

Резать

Наша операция разрезания разбивает предпочтительный путь на две части в данном узле: верхнюю часть и нижнюю часть. Более формально, вспомогательное дерево разделяется на два вспомогательных дерева, так что одно содержит все узлы на определенной глубине или выше в ссылочном дереве, а другое содержит все узлы ниже этой глубины. Как и в случае с join , обратите внимание, что верхняя часть имеет два узла, которые заключают в скобки нижнюю часть. Таким образом, мы можем просто разделить каждый из этих двух узлов, чтобы разделить путь на три части, а затем объединить две внешние части, чтобы в итоге мы получили две части: верхнюю и нижнюю, как хотелось бы.

Анализ

Чтобы определить коэффициент конкурентоспособности для деревьев танго, мы должны найти нижнюю границу производительности оптимального автономного дерева, которое мы используем в качестве эталона. Как только мы найдем верхнюю границу производительности дерева танго, мы сможем разделить их, чтобы определить коэффициент конкурентоспособности.

Перемежать связанное

Основная статья: Нижняя граница чередования

Чтобы найти нижнюю границу работы, выполняемой оптимальным автономным двоичным деревом поиска, мы снова используем понятие предпочтительных дочерних элементов. При рассмотрении последовательности доступа (последовательности поиска) мы отслеживаем, сколько раз предпочтительные дочерние узлы узла ссылочного дерева переключались. Общее количество переключателей (суммированное по всем узлам) дает асимптотическую нижнюю границу работы, выполняемой любым алгоритмом двоичного дерева поиска в заданной последовательности доступа. Это называется нижней границей чередования .

Дерево танго

Чтобы связать это с деревьями танго, мы найдем верхнюю границу работы, выполняемой деревом танго для данной последовательности доступа. Наша верхняя граница будет $(k+1)O(\log \log n)$, где k — количество чередований.

Общая стоимость делится на две части: поиск элемента и обновление структуры дерева танго для поддержания правильных инвариантов (переключение предпочтительных дочерних элементов и перестановка предпочтительных путей).

Идет поиск

Чтобы увидеть, что поиск (а не обновление) соответствует этой границе, просто обратите внимание, что каждый раз, когда поиск вспомогательного дерева оказывается неудачным и нам приходится переходить к следующему вспомогательному дереву, это приводит к переключению предпочтительного дочернего элемента (поскольку предпочтительный родительский путь теперь переключает направления, чтобы присоединиться к предпочтительному пути ребенка). Поскольку все вспомогательные поиски по дереву, кроме последнего, не увенчались успехом (естественно, мы останавливаемся, когда поиск успешен), мы ищем $k+1$ вспомогательные деревья. Каждый поиск занимает $O(\log \log n)$, поскольку размер вспомогательного дерева ограничен $\log n$, высота опорного дерева.

Обновление

Стоимость обновления также укладывается в эти рамки, поскольку нам нужно выполнить только одно разрезание и одно соединение для каждого посещенного вспомогательного дерева. Одна операция вырезания или соединения требует только постоянного количества поисков, разбиений и конкатенаций , каждый из которых занимает логарифмическое время в размере вспомогательного дерева, поэтому наша стоимость обновления равна $(k+1)O(\log \log n)$.

Конкурентоспособное соотношение

Деревья танго $O(\log \log n)$-конкурентно, потому что работа, выполняемая оптимальным автономным двоичным деревом поиска, как минимум линейна по k (общему числу предпочтительных дочерних переключателей), а работа, выполняемая деревом танго, не более $(k+1)O(\log \log n)$.

См. также

• Распространение дерева
• Оптимальное двоичное дерево поиска
• Красно-черное дерево
• Дерево (структура данных)