Изменения
Нет описания правки
<tex>P[size(L) = i] = \frac{1}n, i = 1..n</tex>.
}}
Из определения следует, что каждый ключ в RBST размера n может оказаться корнем с вероятностью <texdpi="150">\frac{1}{n}</tex>.
Идея RBST состоит в том, что хранимое дерево постоянно является рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
==Операции==
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex dpi = "150">\frac{1}{n+1}</tex> вставим ключ в корень дерева, используя процедуру <tex>\mathrm{insert\_at\_root}</tex>. С вероятностью <tex dpi = "150">1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insert\_at\_root}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через <tex>Node </tex> обозначен тип вершины дерева, дерево представляется как указатель на корень)
'''Node''' insert(T, x)
'''return''' T
split(T, x, L, R) <font color="green"> // разделяет дерево T по x, результат - деревья L и R</font>
'''if''' size(T) == 0
L = RBST()
'''else if''' x < T.key
R = T
split (T.left, x, L, R.left)
'''else'''
L = T
split (T.right, x, L.right, R)
Далее рассмотрим как меняется свойство дерева быть рандомизированным при вставке в него ключей.
{{Лемма
|statement= Пусть после операции <tex>\mathrm{split}</tex> от дерева <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 | \mid y < x\}</tex> и <tex>K_{R} = \{y \in K | \mid y > x\}</tex>.
|proof=
Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то лемма верна (получим два пустых дерева).
(пусть событие <tex>A</tex> {{---}} <tex>z</tex> является коренем <tex>T_{L}</tex>)
<tex dpi = "150">P[A | \mid y < x] = \frac{P[A \; \wedge \; y < x]}{P[y < x]} = \frac{1 / n}{m / n} = \frac{1}{m}</tex>
Случай, когда <tex>x < y</tex> симметричен рассмотренному.
Тогда:
<tex>P[A] = P[A|\mid B] \cdot P[B] + P[A|\mid\neg B] \cdot P[\neg B] = P[C] \cdot 1/n + P[D|\mid\neg B] \cdot (n - 1)/n = </tex>
<tex dpi = "150">\frac{1}{n - 1} \cdot \frac{1}{n} + \frac{1}{n - 1} \cdot \frac{n - 1}{n} = \frac{1}{n - 1}</tex>.
}}
*[[Декартово дерево по неявному ключу]]
==СсылкиИсточники информации ==* [http://en.wikipedia.org/wiki/Random_binary_tree Wikipedia {{---}} Random binary tree]
* [http://en.wikipedia.org/wiki/Treap Wikipedia {{---}} Treap]
* Martinez, 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 г.
