188
правок
Изменения
Нет описания правки
==Основная идея и связанные определения==
Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, а следовательно запрос будет операции будут выполняться за <tex>O(n)</tex>. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.
Дадим рекурсивное определение '''рандомизированного бинарного дерева поиска (RBST)'''.
{{Определение
Пусть <tex>T</tex> {{---}} бинарное дерево поиска. Тогда
# Если <tex>T</tex> пусто, то оно является рандомизированным бинарным деревом поиска.
# Если <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 dpi="150">\fracdfrac{1}{n}</tex>.
Идея RBST состоит в том, что хранимое дерево постоянно является рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex dpi = "150">\fracdfrac{1}{n+1}</tex> вставим ключ в корень дерева(разделим дерево по данному ключу и подвесим получившиеся деревни к новому корню), используя процедуру <tex>\mathrm{insertAtRoot}</tex>. С вероятностью <tex dpi = "150">1 - \fracdfrac{1}{n+1} = \fracdfrac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insertAtRoot}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через <tex>Node</tex> обозначен тип вершины дерева, дерево представляется как указатель на корень).
'''Node''' insert(Tt : '''Node''', x: '''T'''): '''int''' r = '''random'''(0..T<tex>\dots</tex> t.size))
'''if''' r == n
'''else'''
Заметим, что если дерево пусто, то <tex>\mathrm{insert}</tex> с вероятностью 1 делает <tex>x</tex> корнем.
'''Node''' insertAtRoot(Tt : '''Node''', x: '''T''') : <font color="green">// вставляем в дерево T t ключ x</font> L = RBST() '''Node''' l, r <font color="green">// создать пустые L l и Rr</font> R = RBST() split(Tt, x, Ll, Rr) T = RBST() <font color="green">// создать пустое T</font> Tt.key = x Tt.left = Ll Tt.left right = Rr '''return''' Tt
'''func''' split(Tt : '''Node''', x: '''T''', Ll : '''Node''', Rr : '''Node''') : <font color="green"> // разделяет дерево T t по x, результат {{- --}} деревья L r и Rl</font> '''if''' Tt.size == 0 L l = RBST()''null'' R r = RBST()''null'' '''else if''' x < Tt.key R r = Tt split(Tt.left, x, Ll, Rr.left)
'''else'''
Далее рассмотрим как меняется свойство дерева быть рандомизированным при вставке в него ключей.
Пусть <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>.
Итак для того, чтобы доказать, что <tex>T_{L}</tex> {{---}} рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина <tex>z</tex> с вероятностью <tex dpi = "150">\fracdfrac{1}{m}</tex> окажется в корне, где <tex>m</tex> {{---}} размер <tex>T_{L}</tex>. Действительно:
(пусть событие <tex>A</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>
Случай, когда <tex>x < y</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>.
|proof=
Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то теорема верна: после операции <tex>\mathrm{insert(x, T)}</tex> получим дерево с корнем <tex>x</tex> и двумя пустыми поддеревьями.
Пусть <tex>n > 0</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>\mathrm{merge}</tex> {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.
'''Node''' remove(Tt : '''Node''', x: '''T''') : <font color="green">// удаляет ключ x из дерева T</font> '''if''' Tt.size == 0 T t = RBST()''null'' '''return''' T t <font color="green">// вернуть пустое поддерево</font> '''if''' x < Tt.key Tt.left = remove(Tt.left, x) '''else if''' x > Tt.key Tt.right = remove(Tt.right, x)
'''else'''
'''Node''' merge(Ll : '''Node''', Rr : '''Node''') : <font color="green">// сливает деревья L l и Rr, результат {{--- }} дерево Tt</font> '''int''' m = Ll.size '''int''' n = Rr.size
'''int''' total = m + n
'''if''' total == 0
'''if''' r < m
'''if''' r < m
Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным.
Пусть <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.key = a</tex> или <tex>L.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>; осталось применить правило умножения.
}}
Пусть <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">\fracdfrac{1}{n - 1}</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">\fracdfrac{1}{n - 1} \cdot \fracdfrac{1}{n} + \fracdfrac{1}{n - 1} \cdot \fracdfrac{n - 1}{n} = \fracdfrac{1}{n - 1}</tex>.
}}
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
[[Категория: Структуры данных]]
