Изменения
Нет описания правки
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex>\dfrac{1}{n+1}</tex> вставим ключ в корень дерева (разделим дерево по данному ключу и подвесим получившиеся деревни деревья к новому корню), используя процедуру <tex>\mathrm{insertAtRoot}</tex>. С вероятностью <tex>1 - \dfrac{1}{n+1} = \dfrac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше.
Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insertAtRoot}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация (через <tex>Node</tex> обозначен тип вершины дерева, дерево представляется как указатель на корень).
'''Node''' insertAtRoot(t : '''Node''', x : '''T'''): <font color="green">// вставляем в дерево t ключ x</font>
t.key = x
t.left = l
'''return''' <''null'', ''null''>
'''else if''' x < t.key
t.left = r
t.size = 1 + t.left.size + t.right.size
'''return''' <l, r>
'''else'''
t.right = l
t.size = 1 + t.left.size + t.right.size
l.size = 1 + l.left.size + l.right.size
'''return''' l
Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным.
Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть <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-дерево]]*[[Декартово АВЛ-дерево]]*[[Декартово Красно-черное дерево по неявному ключу]]
==Примечания==
<references />
== Источники информации ==
* [http://en.wikipedia.org/wiki/Random_binary_tree Wikipedia {{---}} Random binary tree]
