Рандомизированное бинарное дерево поиска

Рандомизированное бинарное дерево поиска (англ. Randomized binary search tree, RBST) — структура данных, представляющая собой бинарное дерево поиска.

Основная идея и связанные определения

Как известно, можно подобрать такую последовательность операций с бинарным деревом поиска в наивной реализации, что его глубина будет пропорциональна количеству ключей, что отрицательно скажется на быстродействии. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим. Дадим рекурсивное определение случайного бинарного дерева поиска.

Определение:

Пусть [math]T[/math] — бинарное дерево поиска. Тогда 1) Если [math]T[/math] пусто, то оно является случайным бинарным деревом поиска. 2) Если [math]T[/math] непусто (содержит [math]n[/math] вершин, [math]n \gt 0[/math]), то [math]T[/math] — случайное бинарное дерево поиска тогда и только тогда, когда его левое и правое поддеревья ([math]L[/math] и [math]R[/math]) оба являются RBST, а также выполняется соотношение [math]P[size(L) = i] = \frac{1}n, i = 1..n[/math].

Из определения следует, что каждый ключ в случайном размера n может оказаться корнем с вероятностью 1/n.

Идея RBST состоит в том, что хранимое дерево постоянно является случайным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.

(Похожие идеи используются в декартовом дереве, поэтому во многих русскоязычных ресурсах термин рандомизированное бинарное дерево поиска используется как синонимическое название декартового дерева и декартового дерева по неявному ключу)

Операции

Операции, не связанные с изменением структуры дерева, выполняются как в обычном дереве поиска.

Вставка

Рассмотрим рекурсивный алгоритм вставки ключа [math]x[/math] в RBST состоящее из [math]n[/math] вершин. С вероятностью [math]\frac{1}{n+1}[/math] вставим ключ в корень дерева, использую процедуру insert_at_root. С вероятностью [math]1 - \frac{1}{n+1} = \frac{n}{n+1}[/math] вставим его в правое поддереао, если он больше корня, или в левое поддерево, если меньше. Ниже представлен псевдокод процедуры вставки insert, процедуры insert_at_root, а также процедуры split(k), разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше [math]k[/math], а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через Node обозначен тип вершины дерева, дерево представляется как указатель на корень)

Node insert (x, T)
   int r = random(0..size(t))
   if (r = n)
      T = insert_at_root(x, T)
   if (x < root [math]\rightarrow[/math] key)
      T = insert(x, T [math]\rightarrow[/math] left)
   else
      T = insert(x, T [math]\rightarrow[/math] right)
   return T

Заметим, что если дерево пусто, то insert с вероятностью 1 делает [math]x[/math] корнем.

Node insert_at_root (x, T)
   ...создать вершины L и R
   split(x, T, L, R)
   ...создать новую вершину T
   T T [math]\rightarrow[/math] key = x
   T [math]\rightarrow[/math] left = L
   T [math]\rightarrow[/math] left = R
   return T

split (x, T, L, R)
   if (T пусто)
      ...создать пустые L И R
   else if (x < T T [math]\rightarrow[/math] key)
      R = T
      split (x, T [math]\rightarrow[/math] left, L, R [math]\rightarrow[/math] left)
   else
      L = T
      split (x, T [math]\rightarrow[/math] right, L [math]\rightarrow[/math] right, R)

Далее рассмотрим как меняется свойство дерева быть случайным при вставке в него ключей.

Лемма:

Пусть после операции split от дерева [math]T[/math] по ключу [math]x[/math] были получены деревья [math]L[/math] и [math]R[/math]. Тогда если [math]T[/math] было случайным бинарным деревом поиска, содержащим множество ключей [math]K[/math], то деревья [math]L[/math] и [math]R[/math] — независимые случайные бинарные деревья поиска, содержащие соответственно множества ключей [math]K_{\lt } = \{y \in K | y \lt x\}[/math] и [math]K_{\gt } = \{y \in K | y \gt x\}[/math]

Теорема:

Если [math]T[/math] — случайное бинарное дерево поиска, содержащее множество ключей [math]K[/math], [math]x \notin K[/math], тогда процедура insert(x, T) вернёт случайное бинарное дерево поиска [math]T[/math], содержащее множество ключей [math]K \cap x[/math]

Пусть [math]K = \{x_{1}; ... ;x_{n}\}[/math] — множество ключей, [math]P = \{x_{i_{1}}, ... ,x_{i_{n}}\}[/math] — какая-то фиксированная перестановка элементов [math]K[/math]. Из приведённой выше теоремы следует, что если в изначально пустое дерево [math]T[/math] добавлять ключи P по порядку, то получим дерево [math]T[/math], являющееся RBST.

Смотри также

• Дерево поиска, наивная реализация
• Декартово дерево
• Декартово дерево по неявному ключу

Ссылки

• Википедия — Дерамида и RBST
• Википедия — случайное бинарное дерево