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

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

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

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

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

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

В статической задаче оптимальности, определенной Кнутом , ^[2] нам дан набор из $n$ упорядоченных элементов и набор $2n+1$ вероятности. Обозначим элементы $a_{1}$ через $a_{n}$ и вероятности $A_{1}$ через $A_{n}$ и $B_{0}$ через $B_{n}$ . $A_{i}$ вероятность того, что будет выполнен поиск элемента $a_{i}$ (или успешный поиск ). ^[3] Для $1\leq i<n$ , $B_{i}$ вероятность поиска элемента между $a_{i}$ и $a_{i+1}$ (или неудачный поиск ), ^[3] $B_{0}$ вероятность поиска элемента строго меньше, чем $a_{1}$ , и $B_{n}$ вероятность того, что поиск будет выполнен для элемента, строго превышающего $a_{n}$ . Эти $2n+1$ вероятности охватывают все возможные поиски и, следовательно, в сумме дают единицу.

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

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

В 1971 году Кнут опубликовал относительно простой алгоритм динамического программирования, способный построить статически оптимальное дерево всего за O ( n ²) время. ^[2] В этой работе Кнут расширил и улучшил алгоритм динамического программирования Эдгара Гилберта и Эдварда Ф. Мура, представленный в 1958 году. ^[4] Требуется алгоритм Гилберта и Мура $O(n^{3})$ время и $O(n^{2})$ пространстве и был разработан для частного случая построения оптимальных бинарных деревьев поиска (известного как задача оптимального алфавитного дерева). ^[5]), учитывающий только вероятность неудачных поисков, т.е. ${\textstyle \sum _{i=1}^{n}A_{i}=0}$ . Работа Кнута основывалась на следующем понимании: проблема статической оптимальности демонстрирует оптимальную подструктуру ; то есть, если определенное дерево статически оптимально для данного распределения вероятностей, то его левое и правое поддеревья также должны быть статически оптимальными для соответствующих им подмножеств распределения (так называемое свойство монотонности корней).

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

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

E=E_{L}+E_{R}+W

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

{\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 ²) время.

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

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

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

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

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

В то время как 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}}}$

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

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

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

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

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

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

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

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

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

Пример фрагмента кода [ править ]

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

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

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

Нерешенная задача в информатике :

Работают ли расширенные деревья так же хорошо, как любой другой алгоритм двоичного дерева поиска?

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

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

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

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

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

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

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

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

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

Распространение деревьев [ править ]

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

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

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

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

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

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

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

Примечания [ править ]

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

[1] Трамбле, Жан-Поль; Честон, Грант А. (2001). Структуры данных и разработка программного обеспечения в объектно-ориентированной области . Эйфелева версия/Прентис-холл. ISBN 978-0-13-787946-5 .

[Knuth1971-2] Jump up to: ^а ^б ^с Кнут, Дональд Э. (1971), «Оптимальные деревья двоичного поиска», Acta Informatica , 1 (1): 14–25, doi : 10.1007/BF00264289 , S2CID 62777263

[:0-3] Jump up to: ^а ^б Нагарадж, С.В. (30 ноября 1997 г.). «Оптимальные бинарные деревья поиска» . Теоретическая информатика . 188 (1): 1–44. дои : 10.1016/S0304-3975(96)00320-9 . ISSN 0304-3975 . S2CID 33484183 .

[4] Гилберт, EN; Мур, EF (июль 1959 г.). «Двоичные кодировки переменной длины» . Технический журнал Bell System . 38 (4): 933–967. дои : 10.1002/j.1538-7305.1959.tb01583.x .

[5] Ху, ТЦ ; Такер, AC (декабрь 1971 г.). «Оптимальные компьютерные деревья поиска и алфавитные коды переменной длины» . SIAM Journal по прикладной математике . 21 (4): 514–532. дои : 10.1137/0121057 . ISSN 0036-1399 .

[Mehlhorm1975-6] Jump up to: ^а ^б ^с ^д ^и ^ж Мельхорн, Курт (1975), «Почти оптимальные бинарные деревья поиска» , Acta Informatica , 5 (4): 287–295, doi : 10.1007/BF00264563 , S2CID 17188103

[7] Кнут, Дональд Э. (1998), «Алгоритм G (алгоритм Гарсиа – Вакса для оптимальных двоичных деревьев)», Искусство компьютерного программирования, Vol. 3: Сортировка и поиск (2-е изд.), Аддисон – Уэсли, стр. 451–453 . См. также «История и библиография», стр. 453–454.

[Demaine2004-8] Jump up to: ^а ^б ^с ^д Демейн, Эрик Д.; Хармон, Дион; Яконо, Джон; Патраску, Михай (2004), «Динамическая оптимальность — почти» (PDF) , Труды 45-го ежегодного симпозиума IEEE по основам компьютерных наук , стр. 484–490, CiteSeerX 10.1.1.99.4964 , doi : 10.1109/FOCS.2004.23 , ISBN 978-0-7695-2228-9

[SplayTrees-9] Jump up to: ^а ^б Слитор, Дэниел; Тарьян, Роберт (1985), «Самонастраивающиеся двоичные деревья поиска», Журнал ACM , 32 (3): 652–686, doi : 10.1145/3828.3835 , S2CID 1165848

[10] Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд; Стоун, Клиффорд (2009). Введение в алгоритмы (PDF) (Третье изд.). Массачусетский технологический институт Пресс. п. 503. ИСБН 978-0-262-03384-8 . Проверено 31 октября 2017 г.

[Iacono2013-11] Яконо, Джон (2013), «В поисках гипотезы динамической оптимальности», arXiv : 1306.0207 [ cs.DS ]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т и Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v т и Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures