O(log log n)-конкурентное бинарное дерево поиска
Ключевые слова и синонимы
Tango
Постановка задачи
Данная модель алгоритма бинарного дерева поиска (binary search tree, BST), используемая в большинстве работ, была детально изложена Уилбером [22]. Статичное множество из n ключей хранится в вершинах бинарного дерева. Ключи взяты из вполне упорядоченной совокупности и хранятся в симметричном порядке. Каждая вершина содержит указатели на левого потомка, правого потомка и предка. Также каждая вершина может содержать o(log n) бит дополнительной информации, но не может содержать дополнительных указателей.
Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), [math]\displaystyle{ S = s_1, s_2, s_3, s_4, ..., s_m \; }[/math]. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута [math]\displaystyle{ s_i \; }[/math]. По пути алгоритм может модифицировать поля в любой вершине и поворачивать любые ребра. Стоимость выполнения последовательности операций доступа определяется как количество затронутых вершин плюс число поворотов.
Пусть A – любой алгоритм бинарного поиска. Обозначим за A(S) стоимость обработки последовательности S, а за [math]\displaystyle{ OPT(S, T_0) \; }[/math] – минимальную стоимость обработки последовательности S. Алгоритм A является T-конкурентным, если для всех возможных последовательностей S, [math]\displaystyle{ A(S) \le T * OPT(S, T_0) + O(m + n) \; }[/math].
Количество поворотов, необходимых для преобразования любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что [math]\displaystyle{ OPT(S, T_0) \; }[/math] отличается от [math]\displaystyle{ OPT(S, T_0') \; }[/math] не более чем на 2n - 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель.
Основные результаты
Границей чередования является нижняя граница [math]\displaystyle{ OPT(S, T_0) \; }[/math], зависящая только от S. Рассмотрим любое бинарное дерево поиска P, состоящее из всех элементов [math]\displaystyle{ T_0 \; }[/math]. Для каждой вершины y в P определим левую сторону y, включающую все вершины левого поддерева y и саму y, а также правую сторону y, включающую все вершины правого поддерева y. Для каждой вершины y пометим каждую операцию доступа к [math]\displaystyle{ s_i \; }[/math] в S меткой, обозначающей, находится ли она на левой или правой стороне y, игнорируя все операции доступа, производимые над другими поддеревьями, отличными от y. Обозначим количество изменений метки для y как IB(S, y). Граница чередования IB(S) составляет [math]\displaystyle{ \sum_y IB(S, y) \; }[/math].
Теорема 1 (Нижняя граница чередования [6, 22]). IB(S)/2 - n – нижняя граница [math]\displaystyle{ OPT(S, T_0) \; }[/math].
Демейн и коллеги заметили, что эту нижнюю границу невозможно использовать для улучшения конкурентного соотношения относительно [math]\displaystyle{ \Theta (log \; log \; n) }[/math].
Теорема 2. (Алгоритм Tango является [math]\displaystyle{ O(log \; log \; n) }[/math]-конкурентным BST-алгоритмом [6]).
Время выполнения алгоритма Tango BST на последовательности S из m операций доступа составляет [math]\displaystyle{ O((OPT(S, T_0)) + n) * (1 + log \; log \; n)) }[/math].
Применение
Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует лучшей теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность из m операций доступа занимает [math]\displaystyle{ \Theta (m \; log \; n) }[/math] времени.
Но хотя улучшить асимптотический результат для случайной последовательности m операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как косое дерево. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным.
За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время выполнения которого оптимально с поправкой на константный коэффициент. Слейтор и Тарьян [14] получили ту же границу без предварительного знания D. Также стоит упомянуть оптимальность, не зависящую от ключей [10], и дерево бинарного поиска со свободными поворотами [1].
В 2004 году Демейн и коллеги взялись за разработку альтернативных алгоритмов построения бинарного дерева поиска с небольшими, но неконстантными коэффициентами конкурентности [6]. Они предложили Tango – первую структуру данных, для которой доказано наличие нетривиального коэффициента конкурентности в виде O(log log n). Это большой шаг в направлении разработки O(1)-конкурентного алгоритма; данное направление исследований потенциально способно заменить значительное количество специализированных алгоритмов поддержки бинарных деревьев поиска.
Открытые вопросы
Недавно было предложено еще несколько вариантов O(log log n)-конкурентных бинарных деревьев поиска [9, 21]. Стоит отметить такой пример, как многократно скошенные деревья [21]. В них понятие границы чередования обобщается, допуская операции вставки и удаления. Для многократно скошенных деревьев было сформулировано несколько теорем, аналогичных теоремам для косых деревьев [20, 21] – таких как лемма об операциях доступа и теорема о рабочем множестве. Ван [21] предположил, что многократно скошенное дерево является O(1)-конкурентным; это предположение также пока не доказано.
Задача нахождения o(log log n)-конкурентного сбалансированного бинарного дерева поиска тоже остается открытой. Было предпринято несколько попыток улучшить нижнюю границу [6, 7, 22], но ни одна из них не дала в результате более низкий коэффициент конкурентности. Даже в несбалансированной модели задача нахождения O(1)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени выполнения.
См. также
Литература
Tango [6] – первое O(loglogn)-конкурентное бинарное дерево поиска; его алгоритм основывается на предложенной Уилбером [22] нижней границе. Использующие многие идеи Tango и деревьев со связыванием и отрезанием (деревьев Слейтора-Тарьяна) [14, 19], многократно скошенные деревья [21] обобщают структуру конкурентных алгоритмов, дополняя их операциями вставки и удаления. Заслуживают особого внимания такие работы, как Самонастраивающиеся бинарные деревья поиска (Слейтор и Тарьян) [14], Нижние границы доступа к бинарным деревьям поиска в присутствии поворотов (Уилбер) [22], В поисках динамической оптимальности (Демейн и коллеги) [6] и Динамическое O(log log n)-конкурентное бинарное дерево поиска (Ван и коллеги) [21].
1. Blum, A., Chawla, S., Kalai, A.: Static optimality and dynamic search-optimality in lists and trees. Algorithmica 36, 249-260 (2003)
2. Cole, R.: On the dynamic finger conjecture for splay trees II: The proof. SIAM J. Comput. 30(1), 44-85 (2000)
3. Cole, R., Mishra, B., Schmidt, J., Siegel, A.: On the dynamic finger conjecture for splay trees I: Splay sorting log n-block sequences. SIAM J. Comput. 30(1), 1 -43 (2000)
4. Crane, C.A.: Linear lists and priority queues as balanced binary trees. Technical Report STAN-CS-72-259, Computer Science Dept., Stanford University (1972)
5. Culik II, K., Wood, D.: A note on some tree similarity measures. Inf. Process. Lett. 15(1), 39^2 (1982)
6. Demaine, E.D., Harmon, D., Iacono, J., Patrascu, M.: Dynamic optimality —almost. SIAM J. Comput. 37(1), 240-251 (2007)
7. Derryberry, J., Sleator, D.D., Wang, C.C.: A lower bound framework for binary search trees with rotations. Technical Report CMU-CS-05-187, Carnegie Mellon University (2005)
8. Elmasry, A.: On the sequential access theorem and deque conjecture for splay trees. Theor. Comput. Sci. 314(3), 459-466 (2004)
9. Georgakopoulos, G.F.: How to splay for log log n-competitiveness. In: Proc. 4th Int'l Workshop on Experimental and Efficient Algorithms (WEA), pp. 570-579 (2005)
10. Iacono, J.: Key-independent optimality. Algorithmica 42(1), 3-10(2005)
11. Knuth, D.E.: Optimum binary search trees. Acta Informatica 1, 14-25(1971)
12. Luccio, F., Pagli, L.: On the upper bound on the rotation distance of binary trees. Inf. Process. Lett. 31 (2), 57-60 (1989)
13. Makinen, E.: On the rotation distance of binary trees. Inf. Process. Lett. 26(5), 271-272 (1988)
14. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J.ACM 32(3), 652-686 (1985)
15. Sleator, D.D., Tarjan, R.E.,Thurston, W.P.: Rotation distance, triangulations, and hyperbolic geometry. In: Proceedings 18th ACM Symposium on Theory of Computing (STOC), Berkeley, 1986, pp. 122-135
16. Sundar, R.: Twists, turns, cascades, deque conjecture, and scanning theorem. In: Proceedings 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 555-559 (1989)
17. Sundar, R.: On the deque conjecture for the splay algorithm. Combinatorica 12(1), 95-124 (1992)
18. Tarjan, R.: Sequential access in play trees takes linear time. Combinatorica 5(4), 367-378 (1985)
19. Tarjan, R.E.: Data structures and network algorithms, CBMS-NSF Reg. Conf.Ser.Appl.Math., vol. 44. SIAM, Philadelphia, PA (1983) Wang, C.C.: Multi-splay trees. Ph.D. Thesis, Carnegie Mellon University (2006)
20. Wang, C.C., Derryberry, J., Sleator, D.D.: O(log logn)-competitive dynamic binary search trees. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, 2006, pp.374-383
21. Wilber, R.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18(1), 56-67 (1989)