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

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

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

Как известно, можно подобрать такую последовательность операций с бинарным деревом поиска в наивной реализации, что его глубина будет пропорциональна количеству ключей, а следовательно запрос будет выполняться за [math]O(n)[/math]. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим. Дадим рекурсивное определение рандомизированного бинарного дерева поиска (RBST).

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

Пусть [math]T[/math] — бинарное дерево поиска. Тогда Если [math]T[/math] пусто, то оно является рандомизированным бинарным деревом поиска. Если [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].

Из определения следует, что каждый ключ в RBST размера n может оказаться корнем с вероятностью [math]\frac{1}{n}[/math].

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

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

Операции

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

Вставка

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

Node insert(T, x)
   int r = random(0 .. size(T))
   if r == n
      T = insert_at_root(T, x)
   if x < root.key
      T = insert(T.left, x)
   else
      T = insert(T.right, x)
   return T

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

Node insert_at_root(T, x)        // вставляем в дерево T ключ x
   L = RBST()                    // создать пустые L и R
   R = RBST()
   split(T, x, L, R)
   T = RBST()                    // создать пустое T
   T.key = x
   T.left = L
   T.left = R
   return T

split(T, x, L, R)           // разделяет дерево T по x, результат - деревья L и R
   if size(T) == 0
      L = RBST()
      R = RBST()
   else if x < T.key
      R = T
      split (T.left, x, L, R.left)
   else
      L = T
      split (T.right, x, L.right, R)

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

Лемма:

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

Доказательство:

[math]\triangleright[/math]

Применим индукцию по [math]n[/math] — размеру дерева. Если [math]n = 0[/math], то лемма верна (получим два пустых дерева). Пусть [math]n \gt 0[/math], и лемма верна при всех меньших размерах дерева.. Пусть также [math]y = T.key, L = T.left, R = T.right[/math]. Если [math]x \gt y[/math], то [math]y[/math] — корень [math]T_{L}[/math], [math]L[/math] — левое поддерево [math]T_{L}[/math], а [math]\mathrm{split}[/math] рекурсивно вызовется от [math]R[/math], разделив его на [math]R'[/math] — правое поддерево [math]T_{L}[/math] —, и [math]T_{R}[/math], которые по предположению индукции будут рандомизированными бинарными деревьями поиска. Но [math]L[/math] также является RBST, т.к. является поддеревом [math]T[/math]. Итак для того, чтобы доказать, что [math]T_{L}[/math] — рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина [math]z[/math] с вероятностью [math]\frac{1}{m}[/math] окажется в корне, где [math]m[/math] — размер [math]T_{L}[/math]. Действительно: (пусть событие [math]A[/math] — [math]z[/math] является коренем [math]T_{L}[/math]) [math]P[A | y \lt x] = \frac{P[A \; \wedge \; y \lt x]}{P[y \lt x]} = \frac{1 / n}{m / n} = \frac{1}{m}[/math] Случай, когда [math]x \lt y[/math] симметричен рассмотренному.

[math]\triangleleft[/math]

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Применим индукцию по [math]n[/math] — размеру дерева. Если [math]n = 0[/math], то теорема верна: после операции [math]\mathrm{insert(x, T)}[/math] получим дерево с корнем [math]x[/math] и двумя пустыми поддеревьями. Пусть [math]n \gt 0[/math], и теорема верна при всех меньших размерах дерева. Возможны два случая: [math]x[/math] вставляется в корень или рекурсивно в одно из поддеревьев. В первом случае правое и левое поддеревья [math]x[/math] по лемме являются рандомизированными BST, а также вероятность того, что [math]x[/math] окажется в корне, равна [math]\frac{1}{n + 1}[/math]. Т.е. новое дерево — рандомизированное BST. Во втором случае корень у дерева останется прежнем. Заметим, что для каждого [math]y \in K[/math] вероятность быть корнем была [math]\frac{1}{n}[/math], а корнем он останется с вероятностью [math]\frac{n}{n + 1}[/math], тогда для каждого [math]y \in K[/math] вероятность быть корнем равна [math]\frac{1}{n} \cdot \frac{n}{n + 1} = \frac{1}{n + 1}[/math]. По предположению же индукции поддерево, в которое вставляется [math]x[/math] становится рандомизированным бинарным деревом поиска; а т.к. другое поддерево корня было рандомизированным, то новое дерево — рандомизированное BST.

[math]\triangleleft[/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.

Удаление

Алгоритм удаления использует операцию [math]\mathrm{merge}[/math] — слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ [math]x[/math] из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья [math]x[/math] (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем [math]x[/math], а корень образовавшегося дерева делаем новым сыном родителя [math]x[/math]. Псевдокод процедур удаления и слияния приведён ниже.

Node remove(T, x)                   // удаляет ключ x из дерева T
   if size(T) == 0
      T = RBST()
      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 = RBST()
      Q = merge(T.left, T.right)
      T = Q
   return T

Node merge(L, R)                           // сливает деревья L и R, результат - дерево T
   int m = L.size
   int n = R.size
   int total = m + n
   if total == 0
      T = RBST()
      return T                             // вернуть пустое поддерево
   int r = random(1 .. total)
   if r < m
      L.right = merge(L.right, R)          // с вероятностью m / (m + n)
      return L
   if r < m
      R.left = merge(L, R.left)            // с вероятностью m / (m + n)
      return R

Докажем, что данный алгоритм оставляет рандомизированное дерево рандомизированным.

Лемма:

Пусть [math]L[/math] и [math]R[/math] — рандомизированные бинарные деревья поиска, содержащие соответственно множества ключей [math]K_{L}[/math] и [math]K_{R}[/math], причём [math]K_{L} \lt K_{R}[/math] (то есть каждый элемент [math]K_{L}[/math] меньше каждого элемента [math]K_{R}[/math]). Тогда операция [math]\mathrm{merge(L, R)}[/math] вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей [math]K[/math] = [math]K_{L} \cap K_{R}[/math].

Доказательство:

[math]\triangleright[/math]

Пусть [math]m[/math] и [math]n[/math] — размеры [math]L[/math] и [math]R[/math] соответственно. Применим индукцию по [math]m[/math] и [math]n[/math]. Если [math]m = 0[/math] или [math]n = 0[/math], то лемма верна. Пусть [math]m \gt 0[/math] и [math]n \gt 0[/math], пусть также [math]L.key = a[/math] или [math]L.key = b[/math]. Без потери общности делаем корнем [math]a[/math]. После рекурсивного слияния правого поддерева [math]L[/math] и [math]R[/math] получим рандомизированное бинарное дерево поиска (которое является правым поддеревом нового дерева). Левое же поддерево нового дерева тоже рандомизированное. Также верно, что для любого [math]x \in K_{L}[/math] вероятность быть корнем равна [math]\frac{1}{m + n}[/math]: действительно, вероятность оказаться в корне в [math]L[/math] до слияния равна [math]\frac{1}{m}[/math], вероятность того, что элемент останется корнем после слияния равна [math]\frac{m}{m + n}[/math]; осталось применить правило умножения.

[math]\triangleleft[/math]

Теорема:

Если [math]T[/math] — рандомизированное бинарное дерево поиска, содержащее множество ключей [math]K[/math], тогда процедура [math]\mathrm{remove(x, T)}[/math] вернёт рандомизированное бинарное дерево поиска [math]T'[/math], содержащее множество ключей [math]K \backslash \{x\}[/math]

Доказательство:

[math]\triangleright[/math]

Если удаляемый элемент отсутствует в дереве, то теорема верна. Пусть [math]x \in T[/math] (дерево не пусто), [math]n[/math] — размер [math]T[/math]. Докажем теорему по индукции по [math]n[/math]. Для [math]n = 1[/math] теорема очевидным образом верна. Пусть [math]n \gt 1[/math], и предположим, что теорема верна для всех деревьев размера меньше [math]n[/math]. Возможно два случая: если [math]x[/math] — корень [math]T[/math], то по лемме, после удаления получим рандомизированное бинарное дерево поиска; если же [math]x[/math] — не корень [math]T[/math], то [math]x[/math] рекурсивно удаляется из поддерева исходного дерева, и по предположению индукции после удаления получаем рандомизированное BST. Осталось лишь показать, что для любого [math]y \in T, y \neq x[/math] вероятность оказаться корнем после удаления равна [math]\frac{1}{n - 1}[/math]. Введём обозначения: событие [math]A[/math] — [math]y[/math] является коренем [math]T'[/math]; событие [math]B[/math] — [math]x[/math] был корнем [math]T[/math] (до операции [math]\mathrm{remove}[/math]); событие [math]C[/math] — [math]y[/math] стал корнем [math]T'[/math] после операции [math]\mathrm{merge}[/math] (но до этого им не являлся); событие [math]D[/math] — [math]y[/math] был корнем [math]T[/math] (до операции [math]\mathrm{remove}[/math]); Тогда: [math]P[A] = P[A|B] \cdot P[B] + P[A|\neg B] \cdot P[\neg B] = P[C] \cdot 1/n + P[D|\neg B] \cdot (n - 1)/n = [/math] [math]\frac{1}{n - 1} \cdot \frac{1}{n} + \frac{1}{n - 1} \cdot \frac{n - 1}{n} = \frac{1}{n - 1}[/math].

[math]\triangleleft[/math]

Анализ времени работы

Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть [math]O (\log n)[/math], где [math]n[/math] — число вершин в дереве, то математическое ожидание времени работы поиска, вставки и удаления — также [math]O (\log n)[/math].

См. также

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

Ссылки

• Wikipedia — Treap
• Wikipedia — Random binary tree

Литература

• 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.