74
правки
Изменения
Нет описания правки
==Основная идея и связанные определения==
Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, что отрицательно скажется на быстродействииа следовательно запрос будет выполняться за <tex>O(n)</tex>. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.Дадим рекурсивное определение '''случайного рандомизированного бинарного дерева поиска(RBST)'''.
{{Определение
|definition=
Пусть <tex>T</tex> {{---}} бинарное дерево поиска. Тогда
<tex>P[size(L) = i] = \frac{1}n, i = 1..n</tex>.
}}
Из определения следует, что каждый ключ в случайном RBST размера n может оказаться корнем с вероятностью 1/n.
Идея RBST состоит в том, что хранимое дерево постоянно является случайным рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
(Похожие идеи используются в [[Декартово дерево| декартовом дереве]], поэтому во многих русскоязычных ресурсах термин '''рандомизированное бинарное дерево поиска''' используется как синонимическое название декартового дерева и [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]])
==Операции==
Операцииобхода дерева, не связанные с изменением структуры деревапоиска ключа, поиска максимума/минимума, поиск следующего/предыдущего элемента выполняются как в [[Дерево поиска, наивная реализация|обычном дереве поиска]], т.к. не меняют структуру дерева.
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST , состоящее из <tex>n</tex> вершин. С вероятностью <tex dpi = "150">\frac{1}{n+1}</tex> вставим ключ в корень дерева, использую используя процедуру ''insert_at_root''. С вероятностью <tex dpi = "150">1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддереао, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки ''insert'', процедуры ''insert_at_root'', а также процедуры ''split(k)'', разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через Node обозначен тип вершины дерева, дерево представляется как указатель на корень)
'''Node''' '''insert''' (T, x, T) '''int''' r = '''random'''(0..size(tT))
'''if''' (r = n)
T = '''insert_at_root'''(T, x, T) '''if''' (x < root <tex>\rightarrow</tex> .key) T = '''insert(x, T <tex>\rightarrow</tex> .left, x)'''
'''else'''
T = insert(x, T <tex>\rightarrow</tex> .right, x)
'''return''' T
Заметим, что если дерево пусто, то ''insert '' с вероятностью 1 делает <tex>x</tex> корнем.
// вставляет ключ x в дерево T
'''Node''' '''insert_at_root''' (T, x, T) ...// создать вершины пустые L и R '''L = RBST() R = RBST() split(T, x, T, L, R)''' ...// создать новую вершину пустое T T = RBST() T <tex>\rightarrow</tex> .key = x T <tex>\rightarrow</tex> .left = L T <tex>\rightarrow</tex> .left = R
'''return''' T
// разделяет дерево T по x
// результат: деревья L и R
'''split''' (T, x, T, L, R) '''if''' (size(T пусто) = 0) ...// создать пустые L И и R L = RBST() R= RBST() '''else''' '''if''' (x < T T <tex>\rightarrow</tex> .key)
R = T
'''else'''
L = T
Далее рассмотрим как меняется свойство дерева быть случайным рандомизированным при вставке в него ключей.
{{Лемма
|statement= Пусть после операции ''split '' от дерева <tex>T</tex> по ключу <tex>x</tex> были получены деревья <tex>T_{<L}</tex> и <tex>T_{>R}</tex>. Тогда если <tex>T</tex> было случайным рандомизированным бинарным деревом поиска, содержащим множество ключей <tex>K</tex>, то деревья <tex>T_{<L}</tex> и <tex>T_{>R}</tex> {{---}} независимые случайные рандомизированные бинарные деревья поиска, содержащие соответственно множества ключей <tex>K_{<L} = \{y \in K | y < x\}</tex> и <tex>K_{>R} = \{y \in K | y > x\}</tex>.
|proof=
Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то лемма верна (получим два пустых дерева).
Пусть <tex>n > 0</tex>, и лемма верна при всех меньших размерах дерева.. Пусть также <tex>y = T \rightarrow .key, L = T \rightarrow .left, R = T \rightarrow .right</tex>. Если <tex>x > y</tex>, то <tex>y</tex> {{---}} корень <tex>T_{<L}</tex>, <tex>L</tex> {{---}} левое поддерево <tex>T_{<L}</tex>, а ''split '' рекурсивно вызовется от <tex>R</tex>, разделив его на <tex>R'</tex> {{---}} правое поддерево <tex>T_{<L}</tex> {{---}}, и <tex>T_{>R}</tex>, которые по предположению индукции будут случайными рандомизированными бинарными деревьями поиска. Но <tex>L</tex> также случайноявляется RBST, т.к. является поддеревом <tex>T</tex>.
Итак для того, чтобы доказать, что <tex>T_{<L}</tex> {{---}} случайное рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина <tex>z</tex> с вероятностью <tex dpi = "150">\frac{1}{m}</tex> окажется в корне, где <tex>m</tex> {{---}} размер <tex>T_{<L}</tex>. Действительно:
(пусть событие <tex>A \Longleftrightarrow z</tex> {{---}} корень <tex>z</tex> является коренем <tex>T_{<L}</tex>)
<tex dpi = "150">P[A | y < x] = \frac{P[A \wedge y < x]}{P[y < x]} = \frac{1 / n}{m / n} = \frac{1}{m}</tex>
{{Теорема
|statement= Если <tex>T</tex> {{---}} случайное рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура ''insert(x, T) '' вернёт случайное рандомизированное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>.
|proof=
Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то теорема верна: после операции ''insert(x, T) '' получим дерево с корнем <tex>x</tex> и двумя пустыми поддеревьями.
Пусть <tex>n > 0</tex>, и теорема верна при всех меньших размерах дерева. Возможны два случая: <tex>x</tex> вставляется в корень или рекурсивно в одно из поддеревьев.
В первом случае правое и левое поддеревья <tex>x</tex> по лемме являются случайными рандомизированными BST, а также вероятность того, что <tex>x</tex> окажется в корне, равна <tex dpi = "150">\frac{1}{n + 1}</tex>. Т.е. новое дерево {{---}} случайное рандомизированное BST.
Во втором случае корень у дерева останется прежнем. Заметим, что для каждого <tex>y \in K</tex> вероятность быть корнем была <tex dpi = "150">\frac{1}{n}</tex>, а корнем он останется с вероятностью <tex dpi = "150">\frac{n}{n + 1}</tex>, тогда для каждого <tex>y \in K</tex> вероятность быть корнем равна <tex dpi = "150">\frac{1}{n} \cdot \frac{n}{n + 1} = \frac{1}{n + 1}</tex>. По предположению же индукции поддерево, в которое вставляется <tex>x</tex> становится случайным рандомизированным бинарным деревом поиска; а т.к. другое поддерево корня было случайнымрандомизированным, то новое дерево {{---}} случайное рандомизированное BST.
}}
===Удаление===
Алгоритм удаления использует операцию ''merge '' {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.
// удаляет ключ x из дерева T
'''Node''' '''remove'''(T, x, T) '''if''' (size(T пусто) = 0) ...// выйти, вернув пустое дерево T = RBST() '''return''' T '''if''' (x < T T <tex>\rightarrow</tex> .key) T <tex>\rightarrow</tex> .left = deleteremove(x, T <tex>\rightarrow</tex> .left, x) '''else''' '''if''' (x > T T <tex>\rightarrow</tex> .key) T <tex>\rightarrow</tex> .right = deleteremove(x, T <tex>\rightarrow</tex> .right, x)
'''else'''
T = Q
'''return''' T
// результат: дерево T
'''Node''' '''merge'''(L, R)
'''int''' m = L <tex>\rightarrow</tex> .size '''int''' n = R <tex>\rightarrow</tex> .size
'''int''' total = m + n
'''if''' (total = 0)
'''int''' r = random(1..total)
'''if''' (r < m)
// с вероятностью m / (m + n)
L <tex>\rightarrow</tex> .right = merge(L <tex>\rightarrow</tex> .right, R)
'''return''' L
'''if''' (r < m)
// с вероятностью m / (m + n)
R <tex>\rightarrow</tex> .left = merge(L, R <tex>\rightarrow</tex> .left)
'''return''' R
Докажем, что данный алгоритм не оставляет случайное рандомизированное дерево случайнымрандомизированным.
{{Лемма
|statement= Пусть <tex>L</tex> и <tex>R</tex> {{---}} независимые случайные рандомизированные бинарные деревья поиска, содержащие соответственно множества ключей <tex>K_{L}</tex> и <tex>K_{R}</tex>, причём <tex>K_{L} < K_{R}</tex> (то есть каждый элемент <tex>K_{L}</tex> меньше каждого элемента <tex>K_{R}</tex>). Тогда <tex>T = операция ''merge(L, R)</tex> {{---}} случайное '' вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex> = <tex>K_{L} \cap K_{R}</tex>.
|proof=
Пусть <tex>m</tex> и <tex>n</tex> {{---}} размеры <tex>L</tex> и <tex>R</tex> соответственно. Применим индукцию по <tex>m</tex> и <tex>n</tex>. Если <tex>m = 0</tex> или <tex>n = 0</tex>, то лемма верна.
Пусть <tex>m > 0</tex> и <tex>n > 0</tex>, пусть также <tex>L \rightarrow .key = a</tex> или <tex>L \rightarrow .key = b</tex>. Без потери общности делаем корнем <tex>a</tex>. После рекурсивного слияния правого поддерева <tex>L</tex> и <tex>R</tex> получим случайное рандомизированное бинарное дерево поиска (которое является правым поддеревом нового дерева). Левое же поддерево нового дерева тоже случайноерандомизированное. Также верно, что для любого <tex>x \in K_{L}</tex> вероятность быть корнем равна <tex dpi = "150">\frac{1}{m + n}</tex>: действительно, вероятность оказаться в корне в <tex>L</tex> до слияния равна <tex dpi = "150">\frac{1}{m}</tex>, вероятность того, что элемент останется корнем после слияния равна <tex dpi = "150">\frac{m}{m + n}</tex>; осталось применить правило умножения.
}}
{{Теорема
|statement= Если <tex>T</tex> {{---}} случайное рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, тогда процедура delete''remove(x, T) '' вернёт случайное рандомизированное бинарное дерево поиска <tex>T'</tex>, содержащее множество ключей <tex>K \backslash \{x\}</tex>
|proof=
Если удаляемый элемент отсутствует в дереве, то теорема верна.
Пусть <tex>x \in T</tex> (дерево не пусто), <tex>n</tex> {{---}} размер <tex>T</tex>. Докажем теорему по индукции по <tex>n</tex>. Для <tex>n = 1</tex> теорема очевидным образом верна. Пусть <tex>n > 1</tex>, и предположим, что теорема верна для всех деревьев размера меньше <tex>n</tex>.
Возможно два случая: если <tex>x</tex> {{---}} корень <tex>T</tex>, то по лемме, после удаления получим случайное рандомизированное бинарное дерево поиска; если же <tex>x</tex> {{---}} не корень <tex>T</tex>, то <tex>x</tex> рекурсивно удаляется из поддерева исходного дерева, и по предположению индукции после удаления получаем случайное рандомизированное BST. Осталось лишь показать, что для любого <tex>y \in T, y \neq x</tex> вероятность оказаться корнем после удаления равна <tex dpi = "150">\frac{1}{n - 1}</tex>.
Введём обозначения:
событие <tex>A \Longleftrightarrow y</tex> {{---}} корень <tex>y</tex> является коренем <tex>T'</tex>;
событие <tex>B \Longleftrightarrow </tex> {{---}} <tex>x</tex> был корнем <tex>T</tex>(до операции ''remove'');
событие <tex>C \Longleftrightarrow </tex> {{---}} <tex>y</tex> стал корнем <tex>T'</tex> после операции ''merge.'' (но до этого им не являлся);
событие <tex>D \Longleftrightarrow </tex> {{---}} <tex>y</tex> был корнем <tex>T</tex>(до операции ''remove'');
Тогда:
==Анализ времени работы==
Достаточно очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины случайного рандомизированного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <tex>O (\log n)</tex>.
==Смотри См. также==
*[[Дерево поиска, наивная реализация]]
*[[Декартово дерево]]
== Литература ==
* MartínezMartinez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM 45
* Seidel, Raimund; Aragon, Cecilia R. [http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf «Randomized Search Trees»], 1996 г.
* [http://www.cs.uiuc.edu/class/sp09/cs473/notes/08-treaps.pdf Randomized binary search trees]. Lecture notes from a course by Jeff Erickson at UIUC. Despite the title, this is primarily about treaps and [[skip list]]s; randomized binary search trees are mentioned only briefly.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
