188
правок
Изменения
м
Нет описания правки
Пусть <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] = \frac{1}n, i = 1..n</tex>.
}}
Из определения следует, что каждый ключ в RBST размера <tex>n </tex> может оказаться корнем с вероятностью <tex dpi="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\_rootinsertAtRoot}</tex>. С вероятностью <tex dpi = "150">1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insert\_at\_rootinsertAtRoot}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через <tex>Node</tex> обозначен тип вершины дерева, дерево представляется как указатель на корень)
'''Node''' insert(T, x)
'''int''' r = '''random'''(0..T.size))
'''if''' r == n
T = insert_at_rootinsertAtRoot(T, x)
'''if''' x < root.key
T = insert(T.left, x)
Заметим, что если дерево пусто, то <tex>\mathrm{insert}</tex> с вероятностью 1 делает <tex>x</tex> корнем.
'''Node''' insert_at_rootinsertAtRoot(T, x) <font color="green">// вставляем в дерево T ключ x</font>
L = RBST() <font color="green">// создать пустые L и R</font>
R = RBST()
