Изменения

'''Рандомизированное бинарное дерево поиска ''' (англ. ''Randomized binary search tree, RBST'', RBST) {{---}} структура данных, реализующая бинарное дерево поиска.

Из определения следует, что каждый ключ в RBST размера n может оказаться корнем с вероятностью <tex>\frac{1}{n}</ntex>.

Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex dpi = "150">\frac{1}{n+1}</tex> вставим ключ в корень дерева, используя процедуру ''insert_at_root''<tex>\mathrm{insert\_at\_root}</tex>. С вероятностью <tex dpi = "150">1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки ''<tex>\mathrm{insert''}</tex>, процедуры ''insert_at_root''<tex>\mathrm{insert\_at\_root}</tex>, а также процедуры ''<tex>\mathrm{split(k)''}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через Node обозначен тип вершины дерева, дерево представляется как указатель на корень)

'''Node''' '''insert''' (T, x) '''int''' r = '''random'''(0..size(T)) '''if''' (r == n)

'''if''' (x < root.key)

Заметим, что если дерево пусто, то ''<tex>\mathrm{insert'' }</tex> с вероятностью 1 делает <tex>x</tex> корнем.

// вставляет ключ x в дерево T '''Node''' '''insert_at_root''' (T, x) <font color="green">// вставляем в дерево T ключ x</font> L = RBST() <font color="green">// создать пустые L и R L = RBST()</font>

T = RBST() <font color="green">// создать пустое T T = RBST()</font>

split(T, x, L, R) <font color="green"> // разделяет дерево T по x // , результат: - деревья L и R '''split''' (T, x, L, R)</font> '''if''' (size(T) == 0) // создать пустые L и R

'''else''' '''if''' (x < T.key)

|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 | y < x\}</tex> и <tex>K_{R} = \{y \in K | y > x\}</tex>.

Пусть <tex>n > 0</tex>, и лемма верна при всех меньших размерах дерева.. Пусть также <tex>y = T.key, L = T.left, R = T.right</tex>. Если <tex>x > y</tex>, то <tex>y</tex> {{---}} корень <tex>T_{L}</tex>, <tex>L</tex> {{---}} левое поддерево <tex>T_{L}</tex>, а ''<tex>\mathrm{split'' }</tex> рекурсивно вызовется от <tex>R</tex>, разделив его на <tex>R'</tex> {{---}} правое поддерево <tex>T_{L}</tex> {{---}}, и <tex>T_{R}</tex>, которые по предположению индукции будут рандомизированными бинарными деревьями поиска. Но <tex>L</tex> также является RBST, т.к. является поддеревом <tex>T</tex>.

|statement= Если <tex>T</tex> {{---}} рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура ''<tex>\mathrm{insert(x, T)'' }</tex> вернёт рандомизированное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>.

Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то теорема верна: после операции ''<tex>\mathrm{insert(x, T)'' }</tex> получим дерево с корнем <tex>x</tex> и двумя пустыми поддеревьями.

Алгоритм удаления использует операцию ''<tex>\mathrm{merge'' }</tex> {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.

// удаляет ключ x из дерева T '''Node''' '''remove'''(T, x) <font color="green">// удаляет ключ x из дерева T</font> '''if''' (size(T) == 0) // выйти, вернув пустое дерево

'''return''' T <font color="green">// вернуть пустое поддерево</font> '''if''' (x < T.key)

'''else''' '''if''' (x > T.key)

// сливает деревья L и R // результат: дерево T '''Node''' '''merge'''(L, R) <font color="green">// сливает деревья L и R, результат - дерево T</font>

'''if''' (total == 0) // вернуть пустое T

'''return''' T <font color="green">// вернуть пустое поддерево</font> '''int''' r = random(1..total) '''if''' (r < m) // с вероятностью m / (m + n) L.right = merge(L.right, R) <font color="green">// с вероятностью m / (m + n)</font>

'''if''' (r < m) // с вероятностью m / (m + n) R.left = merge(L, R.left) <font color="green">// с вероятностью m / (m + n)</font>

|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>\mathrm{merge(L, R)'' }</tex> вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex> = <tex>K_{L} \cap K_{R}</tex>.

|statement= Если <tex>T</tex> {{---}} рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, тогда процедура ''<tex>\mathrm{remove(x, T)'' }</tex> вернёт рандомизированное бинарное дерево поиска <tex>T'</tex>, содержащее множество ключей <tex>K \backslash \{x\}</tex>

событие <tex>B</tex> {{---}} <tex>x</tex> был корнем <tex>T</tex> (до операции ''<tex>\mathrm{remove''}</tex>);

событие <tex>C</tex> {{---}} <tex>y</tex> стал корнем <tex>T'</tex> после операции ''<tex>\mathrm{merge'' }</tex> (но до этого им не являлся);

событие <tex>D</tex> {{---}} <tex>y</tex> был корнем <tex>T</tex> (до операции ''<tex>\mathrm{remove''}</tex>);

<tex>P[A] = P[A|B] \times cdot P[B] + P[A|\neg B] \times cdot P[\neg B] = P[C] \times cdot 1/n + P[D|\neg B] \times cdot (n - 1)/n = </tex><tex dpi = "150">\frac{1}{n - 1} \times cdot \frac{1}{n} + \frac{1}{n - 1} \times cdot \frac{n - 1}{n} = \frac{1}{n - 1}</tex>.

*[http://en.wikipedia.org/wiki/Treap Википедия Wikipedia {{---}} Дерамида и RBSTTreap]*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия Wikipedia {{---}} случайное бинарное деревоRandom binary tree]