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

Концепция компьютерной науки

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

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

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

Статическая оптимальность

Определение

В статической задаче оптимальности, как определено Кнутом , ^[2] нам дан набор из n упорядоченных элементов и набор вероятностей. Мы будем обозначать элементы через и вероятности через и через . — вероятность того, что будет выполнен поиск элемента (или успешный поиск ). ^[3] Для , — вероятность того, что будет выполнен поиск элемента между и (или неудачный поиск ), ^[3] — вероятность того, что будет выполнен поиск элемента строго меньше , а — вероятность того, что будет выполнен поиск элемента строго больше . Эти вероятности охватывают все возможные поиски и, следовательно, в сумме дают единицу. ${\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 i<n}$ ${\displaystyle B_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i+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] В этой работе Кнут расширил и улучшил алгоритм динамического программирования Эдгара Гилберта и Эдварда Ф. Мура, представленный в 1958 году. ^[4] Алгоритм Гилберта и Мура требовал времени и пространства и был разработан для частного случая построения оптимальных бинарных деревьев поиска (известного как задача оптимального алфавитного дерева ^[5] ), который учитывает только вероятность неудачных поисков, то есть . Работа Кнута основывалась на следующем понимании: задача статической оптимальности демонстрирует оптимальную подструктуру ; то есть, если определенное дерево статически оптимально для заданного распределения вероятностей, то его левое и правое поддеревья также должны быть статически оптимальными для своих соответствующих подмножеств распределения (известное как свойство монотонности корней). ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2})}$ ${\textstyle \sum _{i=1}^{n}A_{i}=0}$

Чтобы увидеть это, рассмотрим то, что Кнут называет «взвешенной длиной пути» дерева. Взвешенная длина пути дерева из 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 ² ) времени.

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

Правила Кнута можно рассматривать следующим образом:

• Правило I (Root-max): поместите наиболее часто встречающееся имя в корень дерева, затем действуйте аналогичным образом для поддеревьев.
• Правило II (Деление пополам): выберите корень так, чтобы максимально уравнять общий вес левого и правого поддеревьев, затем действуйте аналогичным образом для поддеревьев.

Эвристика Кнута реализует почти оптимальные бинарные деревья поиска во времени и пространстве. Анализ того, насколько далеко от оптимума может быть эвристика Кнута, был далее предложен Куртом Мельхорном . ^[6] ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$

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

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

В 1975 году Курт Мельхорн опубликовал статью, доказывающую важные свойства правил Кнута. Основные результаты Мельхорна утверждают, что только одна из эвристик Кнута (правило II) всегда производит почти оптимальные бинарные деревья поиска. С другой стороны, правило root-max часто может приводить к очень «плохим» деревьям поиска на основе следующего простого аргумента. ^[6]

Позволять

${\textstyle {\begin{aligned}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~~\operatorname {with} ~~\sum _{i=1}^{n}\varepsilon _{i}=2^{-k}\end{aligned}}}$

и

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {for} ~~1\leqq i\leqq n~~\operatorname {and} ~~B_{j}=0\operatorname {for} ~~0\leqq j\leqq n.\end{aligned}}}$

Учитывая взвешенную длину пути дерева, построенного на основе предыдущего определения, имеем следующее: ${\displaystyle P}$

${\textstyle {\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$

Таким образом, полученное дерево по правилу root-max будет деревом, которое растет только с правой стороны (за исключением самого глубокого уровня дерева), а с левой стороны всегда будут конечные узлы. Это дерево имеет длину пути, ограниченную и, по сравнению со сбалансированным деревом поиска (с путем, ограниченным ), будет работать существенно хуже для того же распределения частот. ^[6] ${\textstyle \Omega ({\frac {n}{2}})}$ ${\textstyle O(2\log n)}$

Кроме того, Мельхорн улучшил работу Кнута и представил гораздо более простой алгоритм, который использует правило II и близко приближается к производительности статически оптимального дерева всего за ⁠ ⁠ ${\displaystyle O(n)}$ время. ^[6] Алгоритм следует той же идее правила деления пополам, выбирая корень дерева для наиболее точного баланса общего веса (по вероятности) левого и правого поддеревьев. И затем стратегия применяется рекурсивно к каждому поддереву.

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

${\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}}}$

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

Алгоритмы Ху-Такера и Гарсиа-Вакса

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

Пример фрагмента кода

Следующий фрагмент кода определяет оптимальное двоичное дерево поиска, если задан набор ключей и значения вероятности того, что ключ является ключом поиска:

public static float calculateOptimalSearchTree(int numNodes, float[] вероятности, int[][] корни) { float[][] costMatrix = new float[numNodes + 2][numNodes + 1]; для (int i = 1; i <= numNodes; i++) { costMatrix[i][i - 1] = 0; costMatrix[i][i] = вероятности[i]; корни[i][i] = i; корни[i][i - 1] = 0; } для (диагональ int = 1; диагональ <= numNodes; диагональ++) { для (int i = 1; i <= numNodes - диагональ; i++) { int j = i + диагональ; costMatrix[i][j] = findMinCost(costMatrix, i, j) + sumProbabilities(probabilities, i, j); // Примечание: отсутствует назначение roots[i][j], это нужно исправить, если вы хотите // для реконструкции дерева. } } вернуть costMatrix[1][numNodes];}

Динамическая оптимальность

Нерешенная проблема в информатике :

Являются ли алгоритмы расширенного дерева такими же эффективными, как и любые другие алгоритмы двоичного дерева поиска?

(еще нерешенные проблемы в информатике)

Определение

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

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

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

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

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

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

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

Раскидистые деревья

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

Деревья танго

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

Другие результаты

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

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

Смотрите также

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

Примечания

1. Трембле, Жан-Поль; Честон, Грант А. (2001). Структуры данных и разработка программного обеспечения в объектно-ориентированной области . Eiffel Edition/Prentice Hall. ISBN 978-0-13-787946-5.
2. Кнут, Дональд Э. (1971), «Оптимальные бинарные деревья поиска», Acta Informatica , 1 (1): 14–25, doi :10.1007/BF00264289, S2CID  62777263
3. Nagaraj, SV (1997-11-30). "Оптимальные бинарные деревья поиска". Теоретическая информатика . 188 (1): 1–44. doi :10.1016/S0304-3975(96)00320-9. ISSN  0304-3975. S2CID  33484183.
4. Гилберт, EN; Мур, EF (июль 1959). «Двоичные кодировки переменной длины». Bell System Technical Journal . 38 (4): 933–967. doi :10.1002/j.1538-7305.1959.tb01583.x.
5. Ху, TC ; Такер, AC (декабрь 1971 г.). «Оптимальные деревья компьютерного поиска и алфавитные коды переменной длины». Журнал SIAM по прикладной математике . 21 (4): 514–532. doi :10.1137/0121057. ISSN  0036-1399.
6. Мельхорн, Курт (1975), «Почти оптимальные двоичные деревья поиска», Acta Informatica , 5 (4): 287–295, doi :10.1007/BF00264563, S2CID  17188103
7. Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа–Вакса для оптимальных бинарных деревьев)», Искусство программирования, т. 3: Сортировка и поиск (2-е изд.), Эддисон–Уэсли, стр. 451–453. См. также Историю и библиографию, стр. 453–454.
8. Демейн, Эрик Д.; Хармон, Дион; Иаконо, Джон; Патраску, Михай (2004), «Динамическая оптимальность — почти» (PDF) , Труды 45-го ежегодного симпозиума IEEE по основам компьютерной науки , стр. 484–490, CiteSeerX 10.1.1.99.4964 , doi :10.1109/FOCS.2004.23, ISBN  978-0-7695-2228-9
9. Sleator, Daniel; Tarjan, Robert (1985), «Саморегулирующиеся бинарные деревья поиска», Journal of the ACM , 32 (3): 652–686, doi : 10.1145/3828.3835 , S2CID  1165848
10. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд; Штейн, Клиффорд (2009). Введение в алгоритмы (PDF) (Третье изд.). Массачусетский технологический институт Пресс. п. 503. ИСБН 978-0-262-03384-8. Получено 31 октября 2017 г. .
11. Яконо, Джон (2013), «В погоне за гипотезой динамической оптимальности», arXiv : 1306.0207 [cs.DS]