Изменения

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

Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, что отрицательно скажется на быстродействииа следовательно операции будут выполняться за <tex>O(n)</tex>. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.Дадим рекурсивное определение '''случайного рандомизированного бинарного дерева поиска(RBST)'''.

1) # Если <tex>T</tex> пусто, то оно является случайным '''рандомизированным бинарным деревом поиска'''.2) # Если <tex>T</tex> непусто (содержит <tex>n</tex> вершин, <tex>n > 0</tex>), то <tex>T</tex> {{---}} случайное '''рандомизированное бинарное дерево поиска ''' тогда и только тогда, когда его левое и правое поддеревья (<tex>L</tex> и <tex>R</tex>) оба являются '''RBST''', а также выполняется соотношение<tex>P[size(L) = i] = \fracdfrac{1}n, i = 1..n</tex>.

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

Идея RBST состоит в том, что хранимое дерево постоянно является случайным рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.

(Похожие идеи используются в [[Декартово дерево| декартовом дереве]], поэтому во многих русскоязычных ресурсах термин '''рандомизированное бинарное дерево поиска''' используется как синонимическое название декартового дерева и [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]]).

Операцииобхода дерева, не связанные с изменением структуры деревапоиска ключа, поиска максимума/минимума, поиск следующего/предыдущего элемента выполняются как в [[Дерево поиска, наивная реализация|обычном дереве поиска]], т.к. не меняют структуру дерева.

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

'''Node''' insert(t : '''insertNode''' (, x, : '''T'''): '''int''' r = '''random'''(0.<tex>\dots</tex> t.size(t)) '''if''' (r = n)= t.size T t = '''insert_at_root'''insertAtRoot(t, x, T) '''if''' (x < root <tex>\rightarrow</tex> t.key) T t = '''insert(t.left, x, T <tex>\rightarrow</tex> left)'''

T t = insert(t.right, x, T <tex>\rightarrow</tex> right) t.size = 1 + t.size '''return''' Tt

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

// вставляет ключ x в дерево T '''Node''' insertAtRoot(t : '''insert_at_rootNode''' (, x, T) ...создать вершины L и R : '''split(x, T, L, R)''' ...создать новую вершину T T T ): <texfont color="green">\rightarrow// вставляем в дерево t ключ x</texfont> <l, r> = split(t, x) t.key = x T <tex>\rightarrow</tex> t.left = Ll T <tex>\rightarrow</tex> left t.right = Rr '''return''' Tt

'''<Node''', '''Node>''' split(t : '''Node''', x : '''T'''): <font color="green"> // разделяет дерево T t по x // , результат: деревья L {{---}} пара деревьев r и Rl</font> '''splitif''' (x, T, L, R)t.size == 0 '''return''if'<'' (T пусто) ...создать пустые L И R null'', 'else'null'' > '''else if''' (x < T T t.key <texl, r>\rightarrow</tex> key= split(t.left, x) R t.left = Tr t.size = 1 + t.left.size + t.right.size r = t '''splitreturn''' (x, T <tex>\rightarrow</tex> left, Ll, R <tex>\rightarrow</texr> left)

L <l, r> = split(t.right, x) t.right = l t.size = 1 + t.left.size + t.right.size l = Tt '''splitreturn''' (x, T <tex>\rightarrow</tex> rightl, L <tex>\rightarrow</texr> 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>.

Пусть <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>, а <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>.

Итак для того, чтобы доказать, что <tex>T_{<L}</tex> {{---}} случайное рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина <tex>z</tex> с вероятностью <tex dpi = "150">\fracdfrac{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 | \mid y < x] = \fracdfrac{P[A \; \wedge \; y < x]}{P[y < x]} = \fracdfrac{1 / n}{m / n} = \fracdfrac{1}{m}</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 cup x</tex>.

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

В первом случае правое и левое поддеревья <tex>x</tex> по лемме являются случайными рандомизированными BST, а также вероятность того, что <tex>x</tex> окажется в корне, равна <tex dpi = "150">\fracdfrac{1}{n + 1}</tex>. Т.е. новое дерево {{---}} случайное рандомизированное BST.

Во втором случае корень у дерева останется прежнем. Заметим, что для каждого <tex>y \in K</tex> вероятность быть корнем была <tex dpi = "150">\fracdfrac{1}{n}</tex>, а корнем он останется с вероятностью <tex dpi = "150">\fracdfrac{n}{n + 1}</tex>, тогда для каждого <tex>y \in K</tex> вероятность быть корнем равна <tex dpi = "150">\fracdfrac{1}{n} \cdot \fracdfrac{n}{n + 1} = \fracdfrac{1}{n + 1}</tex>. По предположению же индукции поддерево, в которое вставляется <tex>x</tex> становится случайным рандомизированным бинарным деревом поиска; а т.к. другое поддерево корня было случайнымрандомизированным, то новое дерево {{---}} случайное рандомизированное BST.

Пусть <tex>K = \{x_{1}; , ... ;,x_{n}\}</tex> {{---}} множество ключей, <tex>P = \{x_{i_{1}}, ... ,x_{i_{n}}\}</tex> {{---}} какая-то фиксированная перестановка элементов <tex>K</tex>. Из приведённой выше теоремы следует, что если в изначально пустое дерево <tex>T</tex> добавлять ключи P по порядку, то получим дерево <tex>T</tex>, являющееся RBST.

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

// удаляет ключ x из дерева T '''Node''' remove(t : '''removeNode'''(, x, : '''T'''): <font color="green">// удаляет ключ x из дерева T</font> '''if''' (T пусто)t.size == 0 t = ''null'' ...выйти, вернув '''return''' t <font color="green">// вернуть пустое деревоподдерево</font> '''if''' (x < T T <tex>\rightarrow</tex> t.key) T <tex>\rightarrow</tex> t.left = deleteremove(t.left, x, T <tex>\rightarrow</tex> left) '''else''' '''if''' (x > T T <tex>\rightarrow</tex> t.key) T <tex>\rightarrow</tex> t.right = deleteremove(t.right, x, T <tex>\rightarrow</tex> right)

...создать пустое дерево Q Q q = merge(T <tex>\rightarrow</tex> t.left, T <tex>\rightarrow</tex> t.right) T t = Qq '''return''' Tt

// сливает деревья L и R // результат'''Node''' merge(l : дерево T '''Node''' , r : '''mergeNode'''(L): <font color="green">// сливает деревья l и r, R)результат {{---}} дерево t</font> '''int''' m = L <tex>\rightarrow</tex> l.size '''int''' n = R <tex>\rightarrow</tex> r.size

'''if''' (total == 0) ...t = ''null'' '''return''' t <font color="green">// вернуть пустое Tподдерево</font> '''int''' r = '''random'''(1..<tex>\dots</tex> total) '''if''' (r < m) l.right = merge(l.right, r) <font color="green">// с вероятностью m / (m + n) L <tex>\rightarrow</texfont> right l.size = merge(L <tex>\rightarrow</tex> 1 + l.left.size + l.right, R).size '''return''' Ll '''if''' r.left = merge(l, r .left) < m) font color="green">// с вероятностью m n / (m + n) R <tex>\rightarrow</texfont> left r.size = merge(L, R <tex>\rightarrow</tex> 1 + r.left).size + r.right.size '''return''' Rr

Докажем, что данный алгоритм не оставляет случайное рандомизированное дерево случайнымрандомизированным.

|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 = \mathrm{merge(L, R)}</tex> {{---}} случайное вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex> = <tex>K_{L} \cap cup K_{R}</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">\fracdfrac{1}{m + n}</tex>: действительно, вероятность оказаться в корне в <tex>L</tex> до слияния равна <tex dpi = "150">\fracdfrac{1}{m}</tex>, вероятность того, что элемент останется корнем после слияния равна <tex dpi = "150">\fracdfrac{m}{m + n}</tex>; осталось применить правило умножения.

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

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

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

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

Достаточно очевидноОчевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины случайного рандомизированного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве<ref>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stei, "Introduction to Algorithms", Second Edition {{---}} Chapter 12.4</ref>, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <tex>O (\log n)</tex>.

==Смотри См. также==*[[Дерево поиска, наивная реализация2-3 дерево]]* [[B-дерево]]* [[Splay-дерево]]*[[Декартово АВЛ-дерево]]*[[Декартово Красно-черное дерево по неявному ключу]]

==СсылкиПримечания==*[http:<references //en.wikipedia.org/wiki/Treap Википедия {{---}} Дерамида и RBST]*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия {{---}} случайное бинарное дерево]>

== Литература Источники информации ==* Martínez[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

* [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 listhttps://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf Binary Search Trees]]s; randomized binary search trees are mentioned only briefly. Robert Sedgewick and Kevin Wayne - Algorithms and Data Structures course.