74
правки
Изменения
заготовка
Рандомизированное бинарное дерево поиска (англ. Randomized binary search tree, RBST) {{---}} структура данных, представляющая собой бинарное дерево поиска.
==Основная идея и связанные определения==
Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, что отрицательно скажется на быстродействии. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.
Дадим рекурсивное определение '''случайного бинарного дерева поиска'''.
{{Определение
|definition=
Пусть <tex>T</tex> {{---}} бинарное дерево поиска. Тогда
1) Если <tex>T</tex> пусто, то оно является случайным бинарным деревом поиска.
2) Если <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] = \frac{1}n, i = 1..n</tex>.
}}
Из определения следует, что каждый ключ в случайном размера n может оказаться корнем с вероятностью 1/n.
Идея RBST состоит в том, что хранимое дерево постоянно является случайным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
(Похожие идеи используются в [[Декартово дерево| декартовом дереве]], поэтому во многих русскоязычных ресурсах термин '''рандомизированное бинарное дерево поиска''' используется как синонимическое название декартового дерева и [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]])
==Операции==
Операции, не связанные с изменением структуры дерева, выполняются как в [[Дерево поиска, наивная реализация|обычном дереве поиска]].
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST состоящее из <tex>n</tex> вершин. С вероятностью <tex>\frac{1}{n+1}</tex> вставим ключ в корень дерева, использую процедуру insert_at_root. С вероятностью <tex>1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддереао, если он больше корня, или в левое поддерево, если меньше. Ниже представлен псевдокод процедуры вставки insert, процедуры insert_at_root, а также процедуры split(k), разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через Node обозначен тип вершины дерева, дерево представляется как указатель на корень)
'''Node''' '''insert''' (x, T)
'''int''' r = '''random'''(0..size(t))
'''if''' (r = n)
T = '''insert_at_root'''(x, T)
'''if''' (x < root <tex>\rightarrow</tex> key)
T = '''insert(x, T <tex>\rightarrow</tex> left)'''
'''else'''
T = insert(x, T <tex>\rightarrow</tex> right)
'''return''' T
Заметим, что если дерево пусто, то insert с вероятностью 1 делает <tex>x</tex> корнем.
'''Node''' '''insert_at_root''' (x, T)
...создать вершины L и R
'''split(x, T, L, R)'''
...создать новую вершину T
T T <tex>\rightarrow</tex> key = x
T <tex>\rightarrow</tex> left = L
T <tex>\rightarrow</tex> left = R
'''return''' T
'''split''' (x, T, L, R)
'''if''' (T пусто)
...создать пустые L И R
'''else''' '''if''' (x < T T <tex>\rightarrow</tex> key)
R = T
'''split''' (x, T <tex>\rightarrow</tex> left, L, R <tex>\rightarrow</tex> left)
'''else'''
L = T
'''split''' (x, T <tex>\rightarrow</tex> right, L <tex>\rightarrow</tex> right, R)
Далее рассмотрим как меняется свойство дерева быть случайным при вставке в него ключей.
{{Лемма
|statement= Пусть после операции split от дерева <tex>T</tex> по ключу <tex>x</tex> были получены деревья <tex>L</tex> и <tex>R</tex>. Тогда если <tex>T</tex> было случайным бинарным деревом поиска, содержащим множество ключей <tex>K</tex>, то деревья <tex>L</tex> и <tex>R</tex> {{---}} независимые случайные бинарные деревья поиска, содержащие соответственно множества ключей <tex>K_{<} = \{y \in K | y < x\}</tex> и <tex>K_{>} = \{y \in K | y > x\}</tex>
|proof=
}}
{{Теорема
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура insert(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>
|proof=
}}
Пусть <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.
===Удаление===
==Анализ времени работы==
==Смотри также==
*[[Дерево поиска, наивная реализация]]
*[[Декартово дерево]]
*[[Декартово дерево по неявному ключу]]
==Ссылки==
*[http://en.wikipedia.org/wiki/Treap Википедия {{---}} Дерамида и RBST]
*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия {{---}} случайное бинарное дерево]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
==Основная идея и связанные определения==
Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, что отрицательно скажется на быстродействии. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.
Дадим рекурсивное определение '''случайного бинарного дерева поиска'''.
{{Определение
|definition=
Пусть <tex>T</tex> {{---}} бинарное дерево поиска. Тогда
1) Если <tex>T</tex> пусто, то оно является случайным бинарным деревом поиска.
2) Если <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] = \frac{1}n, i = 1..n</tex>.
}}
Из определения следует, что каждый ключ в случайном размера n может оказаться корнем с вероятностью 1/n.
Идея RBST состоит в том, что хранимое дерево постоянно является случайным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
(Похожие идеи используются в [[Декартово дерево| декартовом дереве]], поэтому во многих русскоязычных ресурсах термин '''рандомизированное бинарное дерево поиска''' используется как синонимическое название декартового дерева и [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]])
==Операции==
Операции, не связанные с изменением структуры дерева, выполняются как в [[Дерево поиска, наивная реализация|обычном дереве поиска]].
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST состоящее из <tex>n</tex> вершин. С вероятностью <tex>\frac{1}{n+1}</tex> вставим ключ в корень дерева, использую процедуру insert_at_root. С вероятностью <tex>1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддереао, если он больше корня, или в левое поддерево, если меньше. Ниже представлен псевдокод процедуры вставки insert, процедуры insert_at_root, а также процедуры split(k), разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через Node обозначен тип вершины дерева, дерево представляется как указатель на корень)
'''Node''' '''insert''' (x, T)
'''int''' r = '''random'''(0..size(t))
'''if''' (r = n)
T = '''insert_at_root'''(x, T)
'''if''' (x < root <tex>\rightarrow</tex> key)
T = '''insert(x, T <tex>\rightarrow</tex> left)'''
'''else'''
T = insert(x, T <tex>\rightarrow</tex> right)
'''return''' T
Заметим, что если дерево пусто, то insert с вероятностью 1 делает <tex>x</tex> корнем.
'''Node''' '''insert_at_root''' (x, T)
...создать вершины L и R
'''split(x, T, L, R)'''
...создать новую вершину T
T T <tex>\rightarrow</tex> key = x
T <tex>\rightarrow</tex> left = L
T <tex>\rightarrow</tex> left = R
'''return''' T
'''split''' (x, T, L, R)
'''if''' (T пусто)
...создать пустые L И R
'''else''' '''if''' (x < T T <tex>\rightarrow</tex> key)
R = T
'''split''' (x, T <tex>\rightarrow</tex> left, L, R <tex>\rightarrow</tex> left)
'''else'''
L = T
'''split''' (x, T <tex>\rightarrow</tex> right, L <tex>\rightarrow</tex> right, R)
Далее рассмотрим как меняется свойство дерева быть случайным при вставке в него ключей.
{{Лемма
|statement= Пусть после операции split от дерева <tex>T</tex> по ключу <tex>x</tex> были получены деревья <tex>L</tex> и <tex>R</tex>. Тогда если <tex>T</tex> было случайным бинарным деревом поиска, содержащим множество ключей <tex>K</tex>, то деревья <tex>L</tex> и <tex>R</tex> {{---}} независимые случайные бинарные деревья поиска, содержащие соответственно множества ключей <tex>K_{<} = \{y \in K | y < x\}</tex> и <tex>K_{>} = \{y \in K | y > x\}</tex>
|proof=
}}
{{Теорема
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура insert(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>
|proof=
}}
Пусть <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.
===Удаление===
==Анализ времени работы==
==Смотри также==
*[[Дерево поиска, наивная реализация]]
*[[Декартово дерево]]
*[[Декартово дерево по неявному ключу]]
==Ссылки==
*[http://en.wikipedia.org/wiki/Treap Википедия {{---}} Дерамида и RBST]
*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия {{---}} случайное бинарное дерево]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Деревья поиска]]
