Изменения
Нет описания правки
Рандомизированное бинарное дерево поиска (англ. ''Randomized binary search tree'', RBST) {{---}} структура данных, представляющая собой реализующая бинарное дерево поиска.
==Основная идея и связанные определения==
'''Node''' '''insert''' (T, x)
'''int''' r = '''random'''(0..size(T))
'''if''' (r == n)
T = insert_at_root(T, x)
'''if''' (x < root.key)
// результат: деревья L и R
'''split''' (T, x, L, R)
'''if''' (size(T) == 0)
// создать пустые L и R
L = RBST()
}}
Пусть <tex>K = \{x_{1}; , ... ;,x_{n}\}</tex> {{---}} множество ключей, <tex>P = \{x_{i_{1}}, ... ,x_{i_{n}}\}</tex> {{---}} какая-то фиксированная перестановка элементов <tex>K</tex>. Из приведённой выше теоремы следует, что если в изначально пустое дерево <tex>T</tex> добавлять ключи P по порядку, то получим дерево <tex>T</tex>, являющееся RBST.
===Удаление===
// удаляет ключ x из дерева T
'''Node''' '''remove'''(T, x)
'''if''' (size(T) == 0)
// выйти, вернув пустое дерево
T = RBST()
'''int''' n = R.size
'''int''' total = m + n
'''if''' (total == 0)
// вернуть пустое T
T = RBST()
==Анализ времени работы==
==См. также==
