74
правки
Изменения
Нет описания правки
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST состоящее из <tex>n</tex> вершин. С вероятностью <tex>\frac{1}{n+1}</tex> вставим ключ в корень дерева, использую процедуру insert_at_root. С вероятностью <tex>1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддереао, если он больше корня, или в левое поддерево, если меньше. Ниже представлен приведён псевдокод процедуры вставки insert, процедуры insert_at_root, а также процедуры split(k), разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через Node обозначен тип вершины дерева, дерево представляется как указатель на корень)
'''Node''' '''insert''' (x, T)
Заметим, что если дерево пусто, то insert с вероятностью 1 делает <tex>x</tex> корнем.
// вставляет ключ x в дерево T
'''Node''' '''insert_at_root''' (x, T)
...создать вершины L и R
'''return''' T
// разделяет дерево T по x
// результат: деревья L и R
'''split''' (x, T, L, R)
'''if''' (T пусто)
{{Лемма
|statement= Пусть после операции split от дерева <tex>T</tex> по ключу <tex>x</tex> были получены деревья <tex>L</tex> и <tex>R</tex>. Тогда если <tex>T</tex> было случайным бинарным деревом поиска, содержащим множество ключей <tex>K</tex>, то деревья <tex>L</tex> и <tex>R</tex> {{---}} независимые случайные бинарные деревья поиска, содержащие соответственно множества ключей <tex>K_{<} = \{y \in K | y < x\}</tex> и <tex>K_{>} = \{y \in K | y > x\}</tex>.
|proof=
{{Теорема
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура insert(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>.
|proof=
===Удаление===
Алгоритм удаления использует операцию merge {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.
// удаляет ключ x из дерева T
'''Node''' '''remove'''(x, T)
'''if''' (T пусто)
...выйти, вернув пустое дерево
'''if''' (x < T T <tex>\rightarrow</tex> key)
T <tex>\rightarrow</tex> left = delete(x, T <tex>\rightarrow</tex> left)
'''else''' '''if''' (x > T T <tex>\rightarrow</tex> key)
T <tex>\rightarrow</tex> right = delete(x, T <tex>\rightarrow</tex> right)
'''else'''
...создать пустое дерево Q
Q = merge(T <tex>\rightarrow</tex> left, T <tex>\rightarrow</tex> right)
T = Q
'''return''' T
// сливает деревья L и R
// результат: дерево 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)
...вернуть пустое T
'''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=
}}
{{Теорема
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, тогда процедура delete(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \ x</tex>
|proof=
}}
==Анализ времени работы==
Достаточно очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины случайного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <tex>O (\log n)</tex>.
==Смотри также==
*[http://en.wikipedia.org/wiki/Treap Википедия {{---}} Дерамида и RBST]
*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия {{---}} случайное бинарное дерево]
== Литература ==
* Martínez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM 45 (2): 288–323
* 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.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
