Оптимальное двоичное дерево поиска

В информатике , оптимальное бинарное дерево поиска (Оптимальное БСТ) , иногда называемый вес сбалансирован бинарное дерево , ^[1] является бинарное дерево поиска , который обеспечивает наименьшее возможное время поиска (или ожидаемое время поиска ) для данной последовательности доступов (или вероятности доступа). Оптимальные BST обычно делятся на два типа: статические и динамические.

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

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

Статическая оптимальность [ править ]

Определение [ править ]

В статической задаче оптимальности , как определено Кнут , ^[2] задано множество п заказал элементы и набор вероятностей. Мы будем обозначать элементы через и вероятности через и через . вероятность того, что элемент будет выполнен поиском . Ибо , - это вероятность того, что поиск будет выполнен для элемента между и , - это вероятность того, что поиск будет выполнен для элемента, строго меньшего, чем , и - это вероятность того, что поиск будет выполнен для элемента, строго превышающего . Эти${\ displaystyle 2n + 1}$${\ displaystyle a_ {1}}$${\ displaystyle a_ {n}}$${\ displaystyle A_ {1}}$${\ displaystyle A_ {n}}$${\ displaystyle B_ {0}}$${\ displaystyle B_ {n}}$${\ displaystyle A_ {i}}$${\ displaystyle a_ {i}}$${\ Displaystyle 1 \ Leq я <п}$${\ displaystyle B_ {i}}$${\ displaystyle a_ {i}}$${\ displaystyle a_ {я + 1}}$${\ displaystyle B_ {0}}$${\ displaystyle a_ {1}}$${\ displaystyle B_ {n}}$${\ displaystyle a_ {n}}$${\ displaystyle 2n + 1}$ вероятности охватывают все возможные поиски и поэтому в сумме составляют один.

Проблема статической оптимальности - это задача оптимизации поиска двоичного дерева поиска, которое минимизирует ожидаемое время поиска с учетом вероятностей. Поскольку количество возможных деревьев в наборе из n элементов равно , ^[2], что экспоненциально от n , поиск методом перебора обычно не является допустимым решением.${\ displaystyle 2n + 1}$${\displaystyle {2n \choose n}{\frac {1}{n+1}}}$

Алгоритм динамического программирования Кнута [ править ]

В 1971 году Кнут опубликовал относительно простой алгоритм динамического программирования , способный построить статически оптимальное дерево всего за O ( n ² ) времени. ^[2] Основное понимание Кнута состояло в том, что проблема статической оптимальности демонстрирует оптимальную подструктуру ; то есть, если определенное дерево является статически оптимальным для данного распределения вероятностей, то его левое и правое поддеревья также должны быть статически оптимальными для соответствующих подмножеств распределения.

Чтобы убедиться в этом, рассмотрим то, что Кнут называет «взвешенной длиной пути» дерева. Взвешенная длина пути дерева из n элементов представляет собой сумму длин всех возможных путей поиска, взвешенных по их соответствующим вероятностям. Дерево с минимальной взвешенной длиной пути по определению является статически оптимальным.${\displaystyle 2n+1}$

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

${\displaystyle E=E_{L}+E_{R}+W}$

Это повторение приводит к естественному решению динамического программирования. Пусть будет взвешенной длиной пути статически оптимального дерева поиска для всех значений между a _i и a _j , пусть будет общим весом этого дерева и пусть будет индексом его корня. Алгоритм можно построить по следующим формулам:${\displaystyle E_{ij}}$${\displaystyle W_{ij}}$${\displaystyle R_{ij}}$

${\displaystyle {\begin{aligned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\operatorname {for} 1\leq i\leq n+1\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\\E_{i,j}&=\min _{i\leq r\leq j}(E_{i,r-1}+E_{r+1,j}+W_{i,j})\operatorname {for} 1\leq i\leq j\leq n\end{aligned}}}$

Наивная реализация этого алгоритма фактически занимает O ( n ³ ) времени, но статья Кнута включает некоторые дополнительные наблюдения, которые можно использовать для создания модифицированного алгоритма, занимающего всего O ( n ² ) времени.

Алгоритм аппроксимации Мельхорна [ править ]

Хотя время O ( n ² ), затрачиваемое алгоритмом Кнута, значительно лучше экспоненциального времени, необходимого для поиска методом грубой силы, оно все же слишком медленно, чтобы быть практичным, когда количество элементов в дереве очень велико.

В 1975 году Курт Мельхорн опубликовал статью, доказывающую, что гораздо более простой алгоритм может быть использован для точной аппроксимации статически оптимального дерева всего за время. ^[3] В этом алгоритме корень дерева выбирается так, чтобы максимально сбалансировать общий вес (по вероятности) левого и правого поддеревьев. Затем эта стратегия рекурсивно применяется к каждому поддереву.${\displaystyle O(n)}$

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

${\displaystyle 2+(1-\log({\sqrt {5}}-1))^{-1}H=2+{\frac {H}{1-\log({\sqrt {5}}-1)}}}$

где H - энтропия распределения вероятностей. Поскольку никакое оптимальное двоичное дерево поиска не может работать лучше, чем длина взвешенного пути

${\displaystyle (1/\log 3)H={\frac {H}{\log 3}}}$

это приближение очень близко. ^[3]

Алгоритмы Ху – Такера и Гарсиа – Вакса [ править ]

В особом случае, когда все значения равны нулю, оптимальное дерево может быть найдено вовремя . Впервые это было доказано Т.С. Ху и Аланом Такером в статье, опубликованной ими в 1971 году. Более позднее упрощение Гарсиа и Вахса, алгоритм Гарсиа – Вакса , выполняет те же сравнения в том же порядке. Алгоритм работает с использованием жадного алгоритма для построения дерева с оптимальной высотой для каждого листа, но не в порядке, а затем построения другого двоичного дерева поиска с такой же высотой. ^[4]${\displaystyle A_{i}}$${\displaystyle O(n\log n)}$

Динамическая оптимальность [ править ]

Определение [ править ]

Существует несколько различных определений динамической оптимальности, все из которых фактически эквивалентны с точностью до постоянного коэффициента с точки зрения времени работы. ^[5] Проблема была впервые представлена ​​неявно Слеятором и Тарьяном в их статье о растянутых деревьях , ^[6] но Демейн и др. дать очень хорошее формальное заявление об этом. ^[5]

В задаче динамической оптимальности нам дана последовательность обращений x ₁ , ..., x _m по ключам 1, ..., n. Для каждого доступа нам дается указатель на корень нашего BST и мы можем использовать указатель для выполнения любой из следующих операций:

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

(Это наличие четвертой операции, которая перестраивает дерево во время доступа, что делает эту проблему динамической оптимальности.)

Для каждого доступа наш алгоритм BST может выполнять любую последовательность вышеуказанных операций до тех пор, пока указатель в конечном итоге окажется на узле, содержащем целевое значение x _i . Время, необходимое данному динамическому алгоритму BST для выполнения последовательности обращений, эквивалентно общему количеству таких операций, выполненных в течение этой последовательности. Для любой последовательности обращений к любому набору элементов существует некоторое минимальное общее количество операций, необходимых для выполнения этих обращений. Хотелось бы приблизиться к этому минимуму.

Хотя невозможно реализовать этот « алгоритм Бога » без предварительного знания того, какой будет последовательность доступа, мы можем определить OPT (X) как количество операций, которые он будет выполнять для последовательности доступа X, и мы можем сказать, что алгоритм является динамически оптимальным, если для любого X он выполняет X за время O (OPT (X)) (то есть имеет постоянный коэффициент конкуренции ). ^[5]

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

Раскрывающиеся деревья [ править ]

Расширенное дерево - это форма бинарного дерева поиска, изобретенного в 1985 году Дэниелом Слейтором и Робертом Тарьяном, на котором стандартные операции дерева поиска выполняются с амортизированным временем. ^[7] Предполагается, что он динамически оптимален в нужном смысле. То есть предполагается, что расширяемое дерево выполняет любую достаточно длинную последовательность доступа X за время O (OPT (X)). ^[6]${\displaystyle O(\log(n))}$

Деревья танго [ править ]

Дерева танго представляет собой структуру данных , предложенный в 2004 году Эрик Демейн и другие , которые было доказано , чтобы выполнить любую достаточно длинную последовательность-доступа к X во времени . Хотя это не является оптимальным с динамической точки зрения, коэффициент конкурентоспособности все еще очень мал при разумных значениях n. ^[5]${\displaystyle O(\log \log n\operatorname {OPT} (X))}$${\displaystyle \log \log n}$

Другие результаты [ править ]

В 2013 году Джон Иаконо опубликовал статью, в которой используется геометрия двоичных деревьев поиска для предоставления алгоритма, который является динамически оптимальным, если любой алгоритм двоичного дерева поиска является динамически оптимальным. ^[8] Узлы интерпретируются как точки в двух измерениях, и оптимальная последовательность доступа - это наименьшее произвольно удовлетворяемое надмножество этих точек. В отличие от растянутых деревьев и деревьев танго, структура данных Iacono не известна как реализуемая за постоянное время на шаг последовательности доступа, поэтому даже если она динамически оптимальна, она все равно может быть медленнее, чем другие структуры данных дерева поиска, на непостоянный коэффициент.

Перемежать нижняя граница приведен асимптотический нижняя граница динамического оптимальности.

См. Также [ править ]

• Деревья
• Splay tree
• Танго дерево
• Геометрия бинарных деревьев поиска
• Чередовать нижнюю границу

Заметки [ править ]