O(log log n)-конкурентное бинарное дерево поиска: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показано 14 промежуточных версий 1 участника)
Строка 5: Строка 5:
   
   
== Постановка задачи ==
== Постановка задачи ==
Данная модель алгоритма [[Binary search tree|бинарного дерева поиска]] (binary search tree, BST) используется в большинстве посвященных ему работ; она была детально изложена Уилбером [22]. Статичное множество из n ключей хранится в вершинах бинарного дерева. Ключи взяты из вполне упорядоченной совокупности и хранятся в симметричном порядке. Каждая вершина содержит указатели на левого потомка, правого потомка и предка. Также каждая вершина может содержать o(log n) бит дополнительной информации, но не может содержать дополнительных указателей.
Данная модель алгоритма [[Binary search tree|бинарного дерева поиска]] (binary search tree, BST), используемая в большинстве работ, была детально изложена Уилбером [22]. Статичное множество из n ключей хранится в вершинах бинарного дерева. Ключи взяты из вполне упорядоченной совокупности и хранятся в симметричном порядке. Каждая вершина содержит указатели на левого потомка, правого потомка и предка. Также каждая вершина может содержать o(log n) бит дополнительной информации, но не может содержать дополнительных указателей.




Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), <math>S = s_1, s_2, s_3, s_4, ... s_m \;</math>. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута вершина <math>s_i \;</math>. По пути алгоритм может модифицировать поля в любой вершине и поворачивать любые ребра. Стоимость выполнения последовательности операций доступа определяется как количество затронутых вершин плюс число поворотов.
Алгоритм BST должен обрабатывать последовательность из m операций доступа (без вставок и удалений), <math>S = s_1, s_2, s_3, s_4, ..., s_m \;</math>. i-я операция доступа начинается от корня и следует по указателям до тех пор, пока не будет достигнута <math>s_i \;</math>. По пути алгоритм может модифицировать поля в любой вершине и поворачивать любые ребра. Стоимость выполнения последовательности операций доступа определяется как количество затронутых вершин плюс число поворотов.




Строка 14: Строка 14:




В силу этого количество поворотов, необходимых для изменения любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что <math>OPT(S, T_0) \;</math> отличается от <math>OPT(S, T_0') \;</math> не более чем на 2n - 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель.
Количество поворотов, необходимых для преобразования любого бинарного дерева с n ключами в другое дерево с теми же n ключами, не превышает 2n - 6 [4, 5, 12, 13, 15]. Отсюда следует, что <math>OPT(S, T_0) \;</math> отличается от <math>OPT(S, T_0') \;</math> не более чем на 2n - 6. Таким образом, если m > n, то исходное дерево может повлиять только на константный множитель.


== Основные результаты ==
== Основные результаты ==
Границей чередования является нижняя граница <math>OPT(S, T_0) \;</math>, зависящая только от S. Рассмотрим любое бинарное дерево поиска P, состоящее из всех элементов <math>T_0 \;</math>. Для каждой вершины y в P определим левую сторону y, включающую все вершины левого поддерева y и саму y, а также правую сторону y, включающую все вершины правого поддерева y. Для каждой вершины y пометим каждую операцию доступа к <math>s_i \;</math> в S меткой, обозначающей, находится ли она на левой или правой стороне y, игнорируя все операции, производимые над другими поддеревьями, отличными от y. Обозначим количество изменений метки для y как IB(S; y). Граница чередования IB(S) составляет <math>\sum_y IB(S, y) \;</math>.
Границей чередования является нижняя граница <math>OPT(S, T_0) \;</math>, зависящая только от S. Рассмотрим любое бинарное дерево поиска P, состоящее из всех элементов <math>T_0 \;</math>. Для каждой вершины y в P определим левую сторону y, включающую все вершины левого поддерева y и саму y, а также правую сторону y, включающую все вершины правого поддерева y. Для каждой вершины y пометим каждую операцию доступа к <math>s_i \;</math> в S меткой, обозначающей, находится ли она на левой или правой стороне y, игнорируя все операции доступа, производимые над другими поддеревьями, отличными от y. Обозначим количество изменений метки для y как IB(S, y). Граница чередования IB(S) составляет <math>\sum_y IB(S, y) \;</math>.




Строка 25: Строка 25:


'''Теорема 2. (Алгоритм Tango является <math>O(log \; log \; n)</math>-конкурентным BST-алгоритмом [6]).'''
'''Теорема 2. (Алгоритм Tango является <math>O(log \; log \; n)</math>-конкурентным BST-алгоритмом [6]).'''
Время исполнения алгоритма Tango BST на последовательности S из m операций доступа составляет <math>O((OPT(S, T_0)) + n) * (1 + log \; log \; n))</math>.
Время выполнения алгоритма Tango BST на последовательности S из m операций доступа составляет <math>O((OPT(S, T_0)) + n) * (1 + log \; log \; n))</math>.


== Применение ==
== Применение ==
Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность операций доступа занимает <math>\Theta (m \; log \; n)</math> времени.
Бинарное дерево поиска – одна из самых древних структур данных в истории компьютерных наук. Оно часто используется для поддержки упорядоченных множеств данных. За последние 40 лет было разработано множество специальных версий бинарных деревьев поиска для конкретных вариантов применения. Почти все они позволяют осуществлять доступ, вставку и удаление за время O(log n) в наихудшем случае в среднем для случайной последовательности операций доступа. Это значение соответствует лучшей теоретически возможной границе для наихудшего случая. Для большинства подобных структур данных случайная последовательность из m операций доступа занимает <math>\Theta (m \; log \; n)</math> времени.




Но хотя улучшить асимптотический результат для случайной последовательности операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как [[косое дерево]]. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным.
Но хотя улучшить асимптотический результат для случайной последовательности m операций доступа невозможно, в реальности во многих случаях операции доступа не являются случайными. Например, если множество операций доступа случайно выбирается из небольшого подмножества из k элементов, можно ответить на все вопросы за время O(m log k). Стоит отметить такой пример бинарного дерева поиска, как [[косое дерево]]. Оно отлично работает в множестве практических случаев [2, 3, 8, 14, 16, 17, 18]. Слейтор и Тарьян [14] предположили, что косое дерево является O(1)-конкурентным оптимальному несбалансированному бинарному дереву поиска. Спустя 20 лет это предположение остается недоказанным.




За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время исполнения которого оптимально с поправкой на константный коэффициент. Слейтор и Тарьян [14] получили ту же границу без предварительного знания D. Также стоит упомянуть оптимальность, не зависящую от ключей [10], и дерево бинарного поиска со свободными поворотами [1].
За время исследований была доказана оптимальность для нескольких типов ограниченных задач. Большинство ограничений и схем использования были основаны на задачах реального мира. Предположим, что каждая операция доступа производится независимым случайным образом на основе фиксированного распределения D. Кнут [11] предложил алгоритм построения бинарного дерева поиска на основе D, ожидаемое время выполнения которого оптимально с поправкой на константный коэффициент. Слейтор и Тарьян [14] получили ту же границу без предварительного знания D. Также стоит упомянуть оптимальность, не зависящую от ключей [10], и дерево бинарного поиска со свободными поворотами [1].




Строка 41: Строка 41:
== Открытые вопросы ==
== Открытые вопросы ==
Недавно было предложено еще несколько вариантов O(log log n)-конкурентных бинарных деревьев поиска [9, 21]. Стоит отметить такой пример, как многократно скошенные деревья [21]. В них понятие границы чередования обобщается, допуская операции вставки и удаления. Для многократно скошенных деревьев было сформулировано несколько теорем, аналогичных теоремам для косых деревьев [20, 21] – таких как лемма об операциях доступа и теорема о рабочем множестве. Ван [21] предположил, что многократно скошенное дерево является O(1)-конкурентным; это предположение также пока не доказано.
Недавно было предложено еще несколько вариантов O(log log n)-конкурентных бинарных деревьев поиска [9, 21]. Стоит отметить такой пример, как многократно скошенные деревья [21]. В них понятие границы чередования обобщается, допуская операции вставки и удаления. Для многократно скошенных деревьев было сформулировано несколько теорем, аналогичных теоремам для косых деревьев [20, 21] – таких как лемма об операциях доступа и теорема о рабочем множестве. Ван [21] предположил, что многократно скошенное дерево является O(1)-конкурентным; это предположение также пока не доказано.
Задача нахождения o(loglog n)-конкурентного сбалансированного бинарного дерева поиска тоже остается открытой. Было предпринято несколько попыток улучшить нижнюю границу [6, 7, 22], но ни одна из них не дала в результате более низкий коэффициент конкурентности. Даже в несбалансированной модели задача нахождения O(1)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени исполнения.


Задача нахождения o(log log n)-конкурентного сбалансированного бинарного дерева поиска тоже остается открытой. Было предпринято несколько попыток улучшить нижнюю границу [6, 7, 22], но ни одна из них не дала в результате более низкий коэффициент конкурентности. Даже в несбалансированной модели задача нахождения O(1)-конкурентного бинарного дерева поиска очень непроста. Лучший известный несбалансированный константный алгоритм использует методы динамического программирования и требует экспоненциального времени выполнения.


== См. также ==
== См. также ==
Строка 50: Строка 50:


== Литература ==
== Литература ==
Tango [ ] – первое O(loglogn)-конкурентное бинарное дерево поиска; его алгоритм основывается на предложенной Уилбером [ ] нижней границе. Использующие многие идеи Tango и деревьев со связыванием и отрезанием (деревьев Слейтора-Тарьяна) [14, 19], многократно скошенные деревья [21] обобщают структуру конкурентных алгоритмов, дополняя их операциями вставки и удаления. Заслуживают особого внимания такие работы, как Самонастраивающиеся бинарные деревья поиска (Слейтор и Тарьян), Нижние границы доступа к бинарным деревьям поиска в присутствии поворотов (Уилбер), В поисках динамической оптимальности (Демейн и коллеги) и Динамическое O(loglog n)-конкурентное бинарное дерево поиска (Ван и коллеги).
Tango [6] – первое O(loglogn)-конкурентное бинарное дерево поиска; его алгоритм основывается на предложенной Уилбером [22] нижней границе. Использующие многие идеи Tango и деревьев со связыванием и отрезанием (деревьев Слейтора-Тарьяна) [14, 19], многократно скошенные деревья [21] обобщают структуру конкурентных алгоритмов, дополняя их операциями вставки и удаления. Заслуживают особого внимания такие работы, как Самонастраивающиеся бинарные деревья поиска (Слейтор и Тарьян) [14], Нижние границы доступа к бинарным деревьям поиска в присутствии поворотов (Уилбер) [22], В поисках динамической оптимальности (Демейн и коллеги) [6] и Динамическое O(log log n)-конкурентное бинарное дерево поиска (Ван и коллеги) [21].




Строка 94: Строка 94:


21. Wilber, R.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18(1), 56-67 (1989)
21. Wilber, R.: Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. 18(1), 56-67 (1989)
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 11:38, 22 ноября 2024

Ключевые слова и синонимы

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)