1632
правки
Изменения
м
'''if''' r < m r.left = merge(l, r.left) <font color="green">// с вероятностью m n / (m + n)</font> r.size = 1 + r.left.size + r.right.size '''return''' r
<references />
rollbackEdits.php mass rollback
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <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> обозначен тип вершины дерева, дерево представляется как указатель на корень).
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]
