 | Эта статья в значительной степени или полностью основана на одном источнике . ( март 2021 г. ) |
Танго дерево представляет собой тип бинарного дерева поиска , предложенная Эриком Д. Demaine , Дион Harmon, Джон Iacono и Михай Pătraşcu в 2004 году [1] Она названа в честь Буэнос - Айрес , из которых танго является символическим.
Это онлайн- дерево двоичного поиска, которое обеспечивает конкурентное соотношение по сравнению с автономным оптимальным двоичным деревом поиска , при этом используя только дополнительные биты памяти на узел. Это улучшило предыдущее наиболее известное соотношение конкуренции, которое было .
Структура [ править ]
Деревья танго работают путем разбиения двоичного дерева поиска на набор предпочтительных путей , которые сами хранятся во вспомогательных деревьях (таким образом, дерево танго представлено как дерево деревьев).
Справочное дерево [ править ]
Чтобы построить дерево танго, мы моделируем полное двоичное дерево поиска, называемое ссылочным деревом , которое является просто традиционным двоичным деревом поиска, содержащим все элементы. Это дерево никогда не появляется в реальной реализации, но является концептуальной основой следующих частей дерева танго.
В частности, высота справочного дерева равна ⌈log 2 ( n +1) ⌉. Это равно длине самого длинного пути и, следовательно, размеру самого большого вспомогательного дерева. Поддерживая разумный баланс вспомогательных деревьев , высота вспомогательных деревьев может быть ограничена до O (log log n ). Это источник гарантий производительности алгоритма.
Предпочтительные пути [ править ]
Во-первых, мы определяем для каждого узла его предпочтительный дочерний элемент, который неформально является последним посещенным дочерним элементом при традиционном поиске в двоичном дереве поиска. Более формально, рассмотрим поддерево T , с корнем в р , с детьми л (слева) и г (справа). Мы устанавливаем r как предпочтительный дочерний элемент p, если последний доступный узел в T находится в поддереве с корнем r , и l как предпочтительный дочерний элемент в противном случае. Обратите внимание, что если самым последним доступным узлом T является сам p , то l является предпочтительным дочерним элементом по определению.
Предпочтительный путь определяется, начиная с корня и следуя предпочтительным дочерним элементам, пока не достигнет конечного узла. Удаление узлов на этом пути разбивает оставшуюся часть дерева на несколько поддеревьев, и мы рекурсивно обрабатываем каждое поддерево (формируя предпочтительный путь от его корня, который разбивает поддерево на большее количество поддеревьев).
Вспомогательные деревья [ править ]
Чтобы представить предпочтительный путь, мы сохраняем его узлы в сбалансированном двоичном дереве поиска , а именно в красно-черном дереве . Для каждого нелистового узла n в предпочтительном пути P у него есть нежелательный дочерний элемент c , который является корнем нового вспомогательного дерева. Мы присоединяем корень ( c ) этого другого вспомогательного дерева к n в P , таким образом связывая вспомогательные деревья вместе. Мы также дополняем вспомогательное дерево, сохраняя в каждом узле минимальную и максимальную глубину (то есть глубину в ссылочном дереве) узлов в поддереве под этим узлом.
Алгоритм [ править ]
Поиск [ править ]
Чтобы найти элемент в дереве танго, мы просто имитируем поиск в дереве ссылок. Мы начинаем с поиска предпочтительного пути, связанного с корнем, который моделируется путем поиска во вспомогательном дереве, соответствующем этому предпочтительному пути. Если вспомогательное дерево не содержит желаемого элемента, поиск завершается на родительском элементе корня поддерева, содержащего желаемый элемент (начало другого предпочтительного пути), поэтому мы просто продолжаем поиск этого предпочтительного пути во вспомогательном дереве. , и так далее.
Обновление [ править ]
Чтобы сохранить структуру дерева танго (вспомогательные деревья соответствуют предпочтительным путям), мы должны выполнять некоторую работу по обновлению всякий раз, когда предпочтительные дочерние элементы меняются в результате поиска. Когда предпочтительный дочерний элемент изменяется, верхняя часть предпочтительного пути отделяется от нижней части (которая становится его собственным предпочтительным путем) и повторно присоединяется к другому предпочтительному пути (который становится новой нижней частью). Чтобы сделать это эффективно, мы определим операции вырезания и соединения на наших вспомогательных деревьях.
Присоединяйтесь [ редактировать ]
Наша операция соединения объединит два вспомогательных дерева, если у них есть свойство, согласно которому верхний узел одного (в ссылочном дереве) является дочерним по отношению к нижнему узлу другого (по сути, соответствующие предпочтительные пути могут быть объединены). Это будет работать на основе операции конкатенации красно-черных деревьев, которая объединяет два дерева, если у них есть свойство, что все элементы одного меньше, чем все элементы другого, и split , что делает обратное. Обратите внимание на то, что в ссылочном дереве существуют два узла в верхнем пути, так что узел находится в нижнем пути тогда и только тогда, когда его ключ-значение находится между ними. Теперь, чтобы соединить нижний путь с верхним, мы просто разделимверхний путь между этими двумя узлами, затем объедините два результирующих вспомогательных дерева по обе стороны от вспомогательного дерева нижнего пути, и мы получим наше последнее, соединенное вспомогательное дерево.
Вырезать [ править ]
Наша операция вырезания разделит предпочтительный путь на две части в данном узле, верхнюю часть и нижнюю часть. Более формально он разделит вспомогательное дерево на два вспомогательных дерева, так что одно содержит все узлы на определенной глубине или выше в ссылочном дереве, а другое содержит все узлы ниже этой глубины. Как и в случае соединения , обратите внимание, что у верхней части есть два узла, которые ограничивают нижнюю часть. Таким образом, мы можем просто разделить каждый из этих двух узлов, чтобы разделить путь на три части, а затем соединить две внешние, чтобы в итоге получить две части, верхнюю и нижнюю, по желанию.
Анализ [ править ]
Чтобы ограничить конкурентоспособность деревьев танго, мы должны найти нижнюю границу производительности оптимального автономного дерева, которое мы используем в качестве эталона. Как только мы найдем верхнюю границу производительности дерева танго, мы можем разделить их, чтобы ограничить конкурентоспособность.
Граница чередования [ править ]
Чтобы найти нижнюю границу работы, выполняемой оптимальным автономным деревом двоичного поиска, мы снова используем понятие предпочтительных дочерних элементов. При рассмотрении последовательности доступа (последовательности поисков) мы отслеживаем, сколько раз предпочтительный дочерний узел ссылочного дерева переключается. Общее количество переключений (суммированное по всем узлам) дает асимптотическую нижнюю границу работы, выполняемой любым алгоритмом двоичного дерева поиска для данной последовательности доступа. Это называется нижней границей чередования . [1]
Дерево танго [ править ]
Чтобы связать это с деревьями танго, мы найдем верхнюю границу работы, выполняемой деревом танго для данной последовательности доступа. Наша верхняя граница будет , где k - количество чередований.
Общая стоимость делится на две части: поиск элемента и обновление структуры дерева танго для поддержания правильных инвариантов (переключение предпочтительных дочерних элементов и изменение предпочтительных путей).
Поиск [ править ]
Чтобы увидеть, что поиск (не обновление) вписывается в эту границу, просто обратите внимание, что каждый раз, когда поиск по вспомогательному дереву оказывается неудачным, и мы должны переходить к следующему вспомогательному дереву, что приводит к предпочтительному дочернему переключателю (поскольку родительский предпочтительный путь теперь переключает направления, чтобы присоединиться к предпочтительному дочернему пути). Поскольку все поиски по вспомогательному дереву безуспешны, кроме последнего (естественно, мы останавливаемся после успешного поиска), мы ищем вспомогательные деревья. Каждый поиск требует , поскольку размер вспомогательного дерева ограничен высотой ссылочного дерева.
Обновление [ править ]
Стоимость обновления также укладывается в эту границу, потому что нам нужно выполнить только одно вырезание и одно соединение для каждого посещенного вспомогательного дерева. Одна операция вырезания или соединения требует только постоянного количества поисков, разбиений и конкатенаций , каждое из которых занимает логарифмическое время в размере вспомогательного дерева, поэтому наша стоимость обновления равна .
Конкурентное соотношение [ править ]
Деревья танго -конкурентоспособны, потому что работа, выполняемая оптимальным автономным деревом двоичного поиска, по крайней мере линейна по k (общее количество предпочтительных дочерних переключателей), а работа, выполняемая деревом танго, - не более .
См. Также [ править ]
- Splay tree
- Оптимальное двоичное дерево поиска
- Красно-черное дерево
- Дерево (структура данных)
Ссылки [ править ]
- ^ a b Demaine, ED; Harmon, D .; Iacono, J .; Патрашку, М. (2007). «Динамическая оптимальность - почти» (PDF) . SIAM Journal on Computing . 37 (1): 240. DOI : 10.1137 / S0097539705447347 .
