Рандомизированное бинарное дерево поиска — различия между версиями
м |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 4 участников) | |||
Строка 22: | Строка 22: | ||
===Вставка=== | ===Вставка=== | ||
− | Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex>\dfrac{1}{n+1}</tex> вставим ключ в корень дерева (разделим дерево по данному ключу и подвесим получившиеся | + | Рассмотрим рекурсивный алгоритм вставки ключа <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> обозначен тип вершины дерева, дерево представляется как указатель на корень). | Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insertAtRoot}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация (через <tex>Node</tex> обозначен тип вершины дерева, дерево представляется как указатель на корень). | ||
Строка 122: | Строка 122: | ||
l.size = 1 + l.left.size + l.right.size | l.size = 1 + l.left.size + l.right.size | ||
'''return''' l | '''return''' l | ||
− | + | r.left = merge(l, r.left) <font color="green">// с вероятностью n / (m + n)</font> | |
− | + | r.size = 1 + r.left.size + r.right.size | |
− | + | '''return''' r | |
− | |||
Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным. | Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным. | ||
Строка 166: | Строка 165: | ||
Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть <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>. | Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть <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] | * [http://en.wikipedia.org/wiki/Random_binary_tree Wikipedia {{---}} Random binary tree] |
Текущая версия на 19:17, 4 сентября 2022
Рандомизированное бинарное дерево поиска (англ. Randomized binary search tree, RBST) — структура данных, реализующая бинарное дерево поиска.
Основная идея и связанные определения
Как известно, можно подобрать такую последовательность операций с бинарным деревом поиска в наивной реализации, что его глубина будет пропорциональна количеству ключей, а следовательно операции будут выполняться за . Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим. Дадим рекурсивное определение рандомизированного бинарного дерева поиска (RBST).
Определение: |
Пусть
| — бинарное дерево поиска. Тогда
Из определения следует, что каждый ключ в RBST размера
может оказаться корнем с вероятностью .Идея RBST состоит в том, что хранимое дерево постоянно является рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
Похожие идеи используются в декартовом дереве, поэтому во многих русскоязычных ресурсах термин рандомизированное бинарное дерево поиска используется как синонимическое название декартового дерева и декартового дерева по неявному ключу.
Операции
Операции обхода дерева, поиска ключа, поиска максимума/минимума, поиск следующего/предыдущего элемента выполняются как в обычном дереве поиска, т.к. не меняют структуру дерева.
Вставка
Рассмотрим рекурсивный алгоритм вставки ключа
в RBST, состоящее из вершин. С вероятностью вставим ключ в корень дерева (разделим дерево по данному ключу и подвесим получившиеся деревья к новому корню), используя процедуру . С вероятностью вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки , процедуры , а также процедуры , разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше , а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация (через обозначен тип вершины дерева, дерево представляется как указатель на корень).Node insert(t : Node, x : T):
int r = random(0
t.size)
if r == t.size
t = insertAtRoot(t, x)
if x < t.key
t = insert(t.left, x)
else
t = insert(t.right, x)
t.size = 1 + t.size
return t
Заметим, что если дерево пусто, то
с вероятностью 1 делает корнем.Node insertAtRoot(t : Node, x : T): // вставляем в дерево t ключ x <l, r> = split(t, x) t.key = x t.left = l t.right = r return t
<Node, Node> split(t : Node, x : T): // разделяет дерево t по x, результат — пара деревьев r и l if t.size == 0 return <null, null> else if x < t.key <l, r> = split(t.left, x) t.left = r t.size = 1 + t.left.size + t.right.size r = t return <l, r> else <l, r> = split(t.right, x) t.right = l t.size = 1 + t.left.size + t.right.size l = t return <l, r>
Далее рассмотрим как меняется свойство дерева быть рандомизированным при вставке в него ключей.
Лемма: |
Пусть после операции от дерева по ключу были получены деревья и . Тогда если было рандомизированным бинарным деревом поиска, содержащим множество ключей , то деревья и — рандомизированные бинарные деревья поиска, содержащие соответственно множества ключей и . |
Доказательство: |
Применим индукцию по — размеру дерева. Если , то лемма верна (получим два пустых дерева).Пусть , и лемма верна при всех меньших размерах дерева.. Пусть также . Если , то — корень , — левое поддерево , а рекурсивно вызовется от , разделив его на — правое поддерево —, и , которые по предположению индукции будут рандомизированными бинарными деревьями поиска. Но также является RBST, т.к. является поддеревом .Итак для того, чтобы доказать, что — рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина с вероятностью окажется в корне, где — размер . Действительно:(пусть событие — является коренем )Случай, когда симметричен рассмотренному. |
Теорема: |
Если — рандомизированное бинарное дерево поиска, содержащее множество ключей , , тогда процедура вернёт рандомизированное бинарное дерево поиска , содержащее множество ключей . |
Доказательство: |
Применим индукцию по — размеру дерева. Если , то теорема верна: после операции получим дерево с корнем и двумя пустыми поддеревьями.Пусть , и теорема верна при всех меньших размерах дерева. Возможны два случая: вставляется в корень или рекурсивно в одно из поддеревьев.В первом случае правое и левое поддеревья Во втором случае корень у дерева останется прежнем. Заметим, что для каждого по лемме являются рандомизированными BST, а также вероятность того, что окажется в корне, равна . Т.е. новое дерево — рандомизированное BST. вероятность быть корнем была , а корнем он останется с вероятностью , тогда для каждого вероятность быть корнем равна . По предположению же индукции поддерево, в которое вставляется становится рандомизированным бинарным деревом поиска; а т.к. другое поддерево корня было рандомизированным, то новое дерево — рандомизированное BST. |
Пусть
— множество ключей, — какая-то фиксированная перестановка элементов . Из приведённой выше теоремы следует, что если в изначально пустое дерево добавлять ключи P по порядку, то получим дерево , являющееся RBST.Удаление
Алгоритм удаления использует операцию
— слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем , а корень образовавшегося дерева делаем новым сыном родителя . Псевдокод процедур удаления и слияния приведён ниже.Node remove(t : Node, x : T): // удаляет ключ x из дерева T if t.size == 0 t = null return t // вернуть пустое поддерево if x < t.key t.left = remove(t.left, x) else if x > t.key t.right = remove(t.right, x) else q = merge(t.left, t.right) t = q return t
Node merge(l : Node, r : Node): // сливает деревья l и r, результат — дерево t
int m = l.size
int n = r.size
int total = m + n
if total == 0
t = null
return t // вернуть пустое поддерево
int r = random(1
total)
if r < m
l.right = merge(l.right, r) // с вероятностью m / (m + n)
l.size = 1 + l.left.size + l.right.size
return l
r.left = merge(l, r.left) // с вероятностью n / (m + n)
r.size = 1 + r.left.size + r.right.size
return r
Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным.
Лемма: |
Пусть и — рандомизированные бинарные деревья поиска, содержащие соответственно множества ключей и , причём (то есть каждый элемент меньше каждого элемента ). Тогда операция вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей = . |
Доказательство: |
Пусть Пусть и — размеры и соответственно. Применим индукцию по и . Если или , то лемма верна. и , пусть также или . Без потери общности делаем корнем . После рекурсивного слияния правого поддерева и получим рандомизированное бинарное дерево поиска (которое является правым поддеревом нового дерева). Левое же поддерево нового дерева тоже рандомизированное. Также верно, что для любого вероятность быть корнем равна : действительно, вероятность оказаться в корне в до слияния равна , вероятность того, что элемент останется корнем после слияния равна ; осталось применить правило умножения. |
Теорема: |
Если — рандомизированное бинарное дерево поиска, содержащее множество ключей , тогда процедура вернёт рандомизированное бинарное дерево поиска , содержащее множество ключей |
Доказательство: |
Если удаляемый элемент отсутствует в дереве, то теорема верна. Пусть (дерево не пусто), — размер . Докажем теорему по индукции по . Для теорема очевидным образом верна. Пусть , и предположим, что теорема верна для всех деревьев размера меньше .Возможно два случая: если — корень , то по лемме, после удаления получим рандомизированное бинарное дерево поиска; если же — не корень , то рекурсивно удаляется из поддерева исходного дерева, и по предположению индукции после удаления получаем рандомизированное BST. Осталось лишь показать, что для любого вероятность оказаться корнем после удаления равна .Введём обозначения: событие — является коренем ;событие — был корнем (до операции );событие — стал корнем после операции (но до этого им не являлся);событие — был корнем (до операции );Тогда: . |
Анализ времени работы
Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть [1], то математическое ожидание времени работы поиска, вставки и удаления — также .
, где — число вершин в деревеСм. также
Примечания
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stei, "Introduction to Algorithms", Second Edition — Chapter 12.4
Источники информации
- Wikipedia — Random binary tree
- Wikipedia — Treap
- Martinez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM 45
- Seidel, Raimund; Aragon, Cecilia R. «Randomized Search Trees», 1996 г.
- Randomized binary search trees. Lecture notes from a course by Jeff Erickson at UIUC.
- Binary Search Trees. Robert Sedgewick and Kevin Wayne - Algorithms and Data Structures course.