188
правок
Изменения
Нет описания правки
|definition=
Пусть <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] = \dfrac{1}n, i = 1..n</tex>.
}}
Из определения следует, что каждый ключ в RBST размера <tex>n</tex> может оказаться корнем с вероятностью <tex>\dfrac{1}{n}</tex>.
'''Node''' insert(t : '''Node''', x : '''T'''):
'''int''' r = '''random'''(0 <tex>\dots</tex> t.size)
'''if''' r == nt.size
t = insertAtRoot(t, x)
'''if''' x < t.key
'''else'''
t = insert(t.right, x)
t.size = 1 + t.size
'''return''' t
'''Node''' insertAtRoot(t : '''Node''', x : '''T'''): <font color="green">// вставляем в дерево t ключ x</font>
'''<Node''', '''Node>''' l, r <font color="green">// создать пустые l и r</font> split(t, x, l, r)
t.key = x
t.left = l
'''return''' t
'''func''' split(t : '''<Node''', x : '''TNode>''', l split(t : '''Node''', r x : '''NodeT'''): <font color="green"> // разделяет дерево t по x, результат {{---}} деревья пара деревьев r и l</font>
'''if''' t.size == 0
'''else if''' x < t.key
'''<Node''', '''Node>''' l, r = split(t.left, x)
t.left = r
t.size = 1 + t.left.size + t.right.size
r = t
'''else'''
'''<Node''', '''Node>''' l, r = split(t.right, x)
t.right = l
t.size = 1 + t.left.size + t.right.size
l = t
Далее рассмотрим как меняется свойство дерева быть рандомизированным при вставке в него ключей.
'''if''' r < m
l.right = merge(l.right, r) <font color="green">// с вероятностью m / (m + n)</font>
l.size = 1 + l.left.size + l.right.size
'''return''' l
'''if''' r < m
r.left = merge(l, r.left) <font color="green">// с вероятностью m / (m + n)</font>
r.size = 1 + r.left.size + r.right.size
'''return''' r
* Seidel, Raimund; Aragon, Cecilia R. [http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf «Randomized Search Trees»], 1996 г.
* [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.
* [https://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf Binary Search Trees]. Robert Sedgewick and Kevin Wayne - Algorithms and Data Structures course.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
[[Категория: Структуры данных]]
