Геометрия бинарных деревьев поиска

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

Последовательность доступа и соотношение конкуренции

В типичной формулировке проблема онлайнового двоичного дерева поиска включает в себя деревья поиска, определенные по фиксированному набору ключей. $\{1,2,...,n\}$ . Последовательность доступа – это последовательность $x_{1},x_{2},$ ... где каждый доступ $x_{i}$ принадлежит набору ключей.

Любой конкретный алгоритм поддержки двоичных деревьев поиска (например, алгоритм расширенного дерева или структура рабочего набора Яконо ) имеет стоимость для каждой последовательности доступа, которая моделирует количество времени, которое потребуется для использования структуры для поиска каждого из ключей в последовательность доступа по очереди. Стоимость поиска моделируется исходя из предположения, что алгоритм дерева поиска имеет единственный указатель на двоичное дерево поиска, который в начале каждого поиска указывает на корень дерева. Затем алгоритм может выполнить любую последовательность следующих операций:

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

Поиск требуется в какой-то момент внутри этой последовательности операций переместить указатель на узел, содержащий ключ, а стоимость поиска равна количеству операций, которые выполняются в последовательности. Общая стоимость затрат _A ( X ) для алгоритма A в последовательности доступа X представляет собой сумму затрат на поиск каждого последующего ключа в последовательности.

Как это принято в конкурентном анализе , коэффициент конкуренции алгоритма A определяется как максимальное для всех последовательностей доступа отношение стоимости A к лучшей стоимости, которую может достичь любой алгоритм:

\rho _{A}=\sup _{X}{\frac {\mathrm {cost} _{A}(X)}{\mathrm {cost} _{\mathrm {opt} }(X)}}.

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

Перевод в набор геометрических точек

С геометрической точки зрения онлайн-проблемы бинарного дерева поиска:последовательность доступа $x_{1},...,x_{m}$ (последовательность поисков, выполняемых в бинарном дереве поиска (BST) с набором ключей ${1,2,...,n}$ ) отображается в набор точек ${(x_{i},i)}$ , где ось X представляет пространство ключей, а ось Y представляет время; набор затронутых к которому добавляется узлов. Под затронутыми узлами мы подразумеваем следующее. Рассмотрим алгоритм доступа BST с одним указателем на узел дерева. В начале доступа к данному ключу $x_{i}$ , этот указатель инициализируется корнем дерева. Всякий раз, когда указатель перемещается или инициализируется на узле, мы говорим, что узел был затронут. ^[2]Мы представляем алгоритм BST для заданной входной последовательности, рисуя точку для каждого элемента, к которому прикасаются.

Например, предположим, что задано следующее BST на 4 узлах: Набор ключей: {1, 2, 3, 4}.

Отображение только последовательности доступа 3, 1, 4, 2.

Геометрическое представление алгоритма двоичного дерева поиска.

Пусть 3, 1, 4, 2 — последовательность доступа.

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

Касания представлены геометрически: если доступа касаются элемента x в операциях i-го точка ( x , i , то отображается ).

Древовидно удовлетворенные наборы точек

Множество точек называется древесноудовлетворительным , если выполняется следующее свойство: для любогопары точек, не лежащих на одной горизонтальной или вертикальной линии, существует третья точкакоторый лежит в прямоугольнике, охватываемом первыми двумя точками (внутри или на границе).

Теорема

Набор точек, содержащий точки $(x_{i},i)$ древесно удовлетворяется тогда и только тогда, когда оно соответствует допустимому BST для входной последовательности $x_{1},x_{2},...,x_{m}$ .

Доказательство

Сначала докажите, что набор точек для любого допустимого алгоритма BST древесно удовлетворяется.Учитывайте моменты $(x,i)$ и $(y,j)$ , где $к x$ прикасаются в момент $i,$ а $к y$ прикасаются в момент $j$ . Предположим по симметрии, что $x<y$ и $i<j$ . Нужно показать, что в прямоугольнике существует третья точка.с углами как $(x,i)$ и $(y,j)$ . Также пусть $\mathrm {LCA} _{t}(a,b)$ обозначаем наименьшего общего предка узлов $a$ и $b$ прямо перед временем $t$ . Есть несколько случаев:

Если $\mathrm {LCA} _{i}(x,y)\neq x$ , затем используйте точку $(\mathrm {LCA} _{i}(x,y),i)$ , с $\mathrm {LCA} _{i}(x,y)$ должно быть, коснулись, если $x$ был.
Если $\mathrm {LCA} _{j}(x,y)\neq y$ , тогда точка $(\mathrm {LCA} _{j}(x,y),j)$ можно использовать.
Если ни один из двух вышеперечисленных случаев не выполняется, то $x$ должен быть предком $y$ непосредственно перед моментом $i,$ а $y$ быть предком $x$ непосредственно перед моментом $j$ . Тогда в какой-то момент $k$ $(i\leq k<j)$ , $y$ должно быть повернуто выше $x$ , поэтому точка $(y,k)$ можно использовать.

Затем покажите другое направление: учитывая древесно-удовлетворительный набор точек, можно построить действительный BST, соответствующий этому набору точек. Организуйте наш BST в треп, который к моменту следующего касания будет организован в куче. Обратите внимание, что время следующего касания имеет связи и поэтому не определяется однозначно, но это не проблема, если есть способ разорвать связи. Когда время $i$ достигло, узлы, которых коснулись, образуют связанное поддерево вверху благодаря свойству упорядочивания кучи. Теперь назначьте новое время следующего касания для этого поддерева и преобразуйте его в новый локальный треп.Если пара узлов $x$ и $y$ находится на границе между затронутой и нетронутой частьюловушки, то если $y$ нужно коснуться раньше, чем $x$ , то $(x,now)\to (y,next-touch(y))$ является неудовлетворенным прямоугольником, потому что самая левая такая точка будет правым дочерним элементом $x$ , а не $y$ .

Следствие

Поиск лучшего исполнения BST для входной последовательности $x_{1},x_{2},...,x_{m}$ эквивалентно поиску надмножества точек минимальной мощности (которое содержит входные данные в геометрическом представлении), которое удовлетворяется древесным способом. Более общая проблема поиска минимальной мощности, древесно удовлетворяющей надмножеству общего набора входных точек (не ограниченного одной входной точкой на $координату y$ ), как известно, является NP-полной . ^[1]

Жадный алгоритм

Следующий жадный алгоритм создает древесно выполнимые множества:

Проведите по набору точек горизонтальную линию, увеличив $y .$ координату
В момент времени $i$ поместите минимальное количество точек в $y=i$ чтобы поставить точку на $y\geq i$ древесно удовлетворен. Этот минимальный набор точек определен однозначно: для любого неудовлетворительного прямоугольника, образованного $(x_{i},i)$ в одном углу, добавьте другой угол в $y=i$ .

Было высказано предположение, что алгоритм является оптимальным в пределах аддитивного члена. ^[3]

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

Геометрия двоичных деревьев поиска была использована для создания алгоритма, который является динамически оптимальным, если какой-либо алгоритм двоичного дерева поиска является динамически оптимальным. ^[4]

См. также

Ссылки

^ Перейти обратно: ^а ^б Демейн, Эрик Д .; Хармон, Дион; Яконо, Джон ; Кейн, Дэниел ; Патрашку, Михай (2009), «Геометрия бинарных деревьев поиска» , В материалах 20-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2009) , Нью-Йорк: 496–505, doi : 10.1137/1.9781611973068.55 , ISBN 978-0-89871-680-1
^ Демейн, Эрик Д .; Хармон, Дион; Яконо, Джон ; Патрашку, Михай (2007), «Динамическая оптимальность — почти» , SIAM Journal on Computing , 37 (1): 240–251, CiteSeerX 10.1.1.99.4964 , doi : 10.1137/S0097539705447347 , MR 2306291 , S2C ID 1480961
^ Фокс, Кайл (15–17 августа 2011 г.). Верхние границы максимально жадных бинарных деревьев поиска (PDF) . Алгоритмы и структуры данных: 12-й международный симпозиум, WADS 2011. Конспекты лекций по информатике. Том. 6844. Нью-Йорк: Спрингер. стр. 411–422. arXiv : 1102.4884 . дои : 10.1007/978-3-642-22300-6_35 .
^ Яконо, Джон (2013). «В поисках гипотезы динамической оптимальности». Компактные структуры данных, потоки и алгоритмы . Конспекты лекций по информатике. Том. 8066. стр. 236–250. arXiv : 1306.0207 . Бибкод : 2013arXiv1306.0207I . дои : 10.1007/978-3-642-40273-9_16 . ISBN 978-3-642-40272-2 . S2CID 14729858 .

[DHIKP09-1] Перейти обратно: ^а ^б Демейн, Эрик Д .; Хармон, Дион; Яконо, Джон ; Кейн, Дэниел ; Патрашку, Михай (2009), «Геометрия бинарных деревьев поиска» , В материалах 20-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2009) , Нью-Йорк: 496–505, doi : 10.1137/1.9781611973068.55 , ISBN 978-0-89871-680-1

[2] Демейн, Эрик Д .; Хармон, Дион; Яконо, Джон ; Патрашку, Михай (2007), «Динамическая оптимальность — почти» , SIAM Journal on Computing , 37 (1): 240–251, CiteSeerX 10.1.1.99.4964 , doi : 10.1137/S0097539705447347 , MR 2306291 , S2C ID 1480961

[3] Фокс, Кайл (15–17 августа 2011 г.). Верхние границы максимально жадных бинарных деревьев поиска (PDF) . Алгоритмы и структуры данных: 12-й международный симпозиум, WADS 2011. Конспекты лекций по информатике. Том. 6844. Нью-Йорк: Спрингер. стр. 411–422. arXiv : 1102.4884 . дои : 10.1007/978-3-642-22300-6_35 .

[Iacono2013-4] Яконо, Джон (2013). «В поисках гипотезы динамической оптимальности». Компактные структуры данных, потоки и алгоритмы . Конспекты лекций по информатике. Том. 8066. стр. 236–250. arXiv : 1306.0207 . Бибкод : 2013arXiv1306.0207I . дои : 10.1007/978-3-642-40273-9_16 . ISBN 978-3-642-40272-2 . S2CID 14729858 .

[1]

[2]

[3]

[4]