Оглавление [Скрыть]
- 1 Optimal binary search tree
- 1.1 Оптимальные бинарные деревья поиска
- 1.2 Статическая оптимальность
- 1.3 Алгоритм Кнута
- 1.4 Правила Кнута
- 1.5 Алгоритм Мелхорна
- 1.6 Алгоритмы Ху-Такера и Гарсиа-Вахса
- 1.7 Определение динамической оптимальности
- 1.8 Проблема динамической оптимальности
- 1.9 Сплай-деревья
- 1.10 Танго-деревья
- 1.11 Другие результаты
- 1.12 Полный текст статьи:
- 2 Оптимальное двоичное дерево поиска
Optimal binary search tree
-
Оптимальные бинарные деревья поиска
- Оптимальные бинарные деревья поиска (Optimal BST) минимизируют время поиска для заданной последовательности доступов.
- Существуют статические и динамические оптимальные BST.
-
Статическая оптимальность
- В статической оптимальности дерево не может быть изменено после построения.
- Существуют алгоритмы для построения или аппроксимации статически оптимального дерева.
-
Алгоритм Кнута
- Кнут предложил алгоритм динамического программирования для построения статически оптимального дерева за O(n^2) времени.
- Алгоритм основан на идее, что дерево с минимальной взвешенной длиной пути является оптимальным.
-
Правила Кнута
- Правило I (Root-max) помещает наиболее часто встречающееся имя в корень дерева.
- Правило II (Bisection) выбирает корень так, чтобы уравнять веса левого и правого поддеревьев.
-
Алгоритм Мелхорна
- Мелхорн доказал, что только правило II всегда производит почти оптимальное дерево.
- Он предложил алгоритм, использующий правило II, который работает за O(n) времени и O(n) пространства.
-
Алгоритмы Ху-Такера и Гарсиа-Вахса
- В случае, когда все значения Ai равны нулю, оптимальное дерево можно найти за O(n log n) времени.
- Алгоритм Ху-Такера использует жадный алгоритм для построения дерева с оптимальной высотой для каждого листа.
- Алгоритм Гарсиа-Вахса использует жадный алгоритм для построения дерева с оптимальными высотами и затем строит другое дерево с теми же высотами.
-
Определение динамической оптимальности
- Динамическая оптимальность определяется как выполнение операций в бинарном дереве поиска с минимальным количеством операций.
- Операции включают перемещение указателя к дочернему узлу, родителю или выполнение вращения.
- Время выполнения алгоритма эквивалентно общему количеству операций.
-
Проблема динамической оптимальности
- Проблема динамической оптимальности была введена в 1985 году Дэниелом Слеатором и Робертом Таржаном.
- Формальное определение дано Эриком Д. Демайном и другими.
- Алгоритм считается динамически оптимальным, если он выполняет любую последовательность доступа за время O(OPT(X)).
-
Сплай-деревья
- Сплай-деревья — это форма бинарного дерева поиска, предложенная в 1985 году.
- Операции выполняются за O(log(n)) амортизированное время.
- Сплай-деревья предположительно динамически оптимальны.
-
Танго-деревья
- Танго-деревья — это структура данных, предложенная в 2004 году.
- Операции выполняются за O(log log n OPT(X)) время.
- Танго-деревья не являются динамически оптимальными, но имеют очень маленький коэффициент конкурентоспособности.
-
Другие результаты
- В 2013 году Джон Иаконо опубликовал алгоритм, использующий геометрию бинарных деревьев поиска.
- Алгоритм Иаконо может быть динамически оптимальным, но не известен как реализуемый в постоянное время.
- Интерлейв-нижняя граница — это асимптотическая нижняя граница динамической оптимальности.