Рандомизированное бинарное дерево поиска — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(заготовка)
 
Строка 23: Строка 23:
 
===Вставка===
 
===Вставка===
  
Рассмотрим рекурсивный алгоритм вставки ключа <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 обозначен тип вершины дерева, дерево представляется как указатель на корень)
+
Рассмотрим рекурсивный алгоритм вставки ключа <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)
 
  '''Node''' '''insert''' (x, T)
Строка 37: Строка 37:
 
Заметим, что если дерево пусто, то insert с вероятностью 1 делает <tex>x</tex> корнем.
 
Заметим, что если дерево пусто, то insert с вероятностью 1 делает <tex>x</tex> корнем.
  
 +
// вставляет ключ x в дерево T
 
  '''Node''' '''insert_at_root''' (x, T)
 
  '''Node''' '''insert_at_root''' (x, T)
 
     ...создать вершины L и R
 
     ...создать вершины L и R
Строка 46: Строка 47:
 
     '''return''' T
 
     '''return''' T
  
 +
// разделяет дерево T по x
 +
// результат: деревья L и R
 
  '''split''' (x, T, L, R)
 
  '''split''' (x, T, L, R)
 
     '''if''' (T пусто)
 
     '''if''' (T пусто)
Строка 59: Строка 62:
  
 
{{Лемма
 
{{Лемма
|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>
+
|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=
 
|proof=
  
Строка 65: Строка 68:
  
 
{{Теорема  
 
{{Теорема  
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура insert(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>
+
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура insert(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>.
 
|proof=
 
|proof=
  
Строка 73: Строка 76:
  
 
===Удаление===
 
===Удаление===
 +
 +
Алгоритм удаления использует операцию merge {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.
 +
 +
// удаляет ключ x из дерева T
 +
'''Node''' '''remove'''(x, T)
 +
    '''if''' (T пусто)
 +
      ...выйти, вернув пустое дерево
 +
    '''if''' (x < T T <tex>\rightarrow</tex> key)
 +
      T <tex>\rightarrow</tex> left = delete(x, T <tex>\rightarrow</tex> left)
 +
    '''else''' '''if''' (x > T T <tex>\rightarrow</tex> key)
 +
      T <tex>\rightarrow</tex> right = delete(x, T <tex>\rightarrow</tex> right)
 +
    '''else'''
 +
      ...создать пустое дерево Q
 +
      Q = merge(T <tex>\rightarrow</tex> left, T <tex>\rightarrow</tex> right)
 +
      T = Q
 +
    '''return''' T
 +
 +
// сливает деревья L и R
 +
// результат: дерево T
 +
'''Node''' '''merge'''(L, R)
 +
    '''int''' m = L <tex>\rightarrow</tex> size
 +
    '''int''' n = R <tex>\rightarrow</tex> size
 +
    '''int''' total = m + n
 +
    '''if''' (total = 0)
 +
      ...вернуть пустое T
 +
    '''int''' r = random(1..total)
 +
    '''if''' (r < m)
 +
      // с вероятностью m / (m + n)
 +
      L <tex>\rightarrow</tex> right = merge(L <tex>\rightarrow</tex> right, R)
 +
      '''return''' L
 +
    '''if''' (r < m)
 +
      // с вероятностью m / (m + n)
 +
      R <tex>\rightarrow</tex> left = merge(L, R <tex>\rightarrow</tex> left)
 +
      '''return''' R
 +
 +
Докажем, что данный алгоритм не оставляет случайное дерево случайным.
 +
 +
{{Лемма
 +
|statement= Пусть <tex>L</tex> и <tex>R</tex> {{---}} независимые случайные бинарные деревья поиска, содержащие соответственно множества ключей <tex>K_{L}</tex> и <tex>K_{R}</tex>, причём <tex>K_{L} < K_{R}</tex> (то есть каждый элемент <tex>K_{L}</tex> меньше каждого элемента <tex>K_{R}</tex>). Тогда <tex>T = merge(L, R)</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex> = <tex>K_{L} \cap K_{R}</tex>.
 +
|proof=
 +
 +
}}
 +
 +
{{Теорема
 +
|statement= Если <tex>T</tex> {{---}} случайное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, тогда процедура delete(x, T) вернёт случайное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \ x</tex>
 +
|proof=
 +
 +
}}
  
 
==Анализ времени работы==
 
==Анализ времени работы==
 +
 +
Достаточно очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины случайного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <tex>O (\log n)</tex>.
  
 
==Смотри также==
 
==Смотри также==
Строка 84: Строка 137:
 
*[http://en.wikipedia.org/wiki/Treap Википедия {{---}} Дерамида и RBST]
 
*[http://en.wikipedia.org/wiki/Treap Википедия {{---}} Дерамида и RBST]
 
*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия {{---}} случайное бинарное дерево]
 
*[http://en.wikipedia.org/wiki/Random_binary_tree Википедия {{---}} случайное бинарное дерево]
 +
 +
== Литература ==
 +
* Martínez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM 45 (2): 288–323
 +
* Seidel, Raimund; Aragon, Cecilia R. [http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf «Randomized Search Trees»], 1996 г.
 +
* [http://www.cs.uiuc.edu/class/sp09/cs473/notes/08-treaps.pdf Randomized binary search trees]. Lecture notes from a course by Jeff Erickson at UIUC. Despite the title, this is primarily about treaps and [[skip list]]s; randomized binary search trees are mentioned only briefly.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Деревья поиска]]
 
[[Категория: Деревья поиска]]

Версия 22:58, 28 апреля 2012

Рандомизированное бинарное дерево поиска (англ. 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] корнем.

// вставляет ключ x в дерево T
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
// разделяет дерево T по x
// результат: деревья L и R
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.

Удаление

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

// удаляет ключ x из дерева T
Node remove(x, T)
   if (T пусто)
      ...выйти, вернув пустое дерево
   if (x < T T [math]\rightarrow[/math] key)
      T [math]\rightarrow[/math] left = delete(x, T [math]\rightarrow[/math] left)
   else if (x > T T [math]\rightarrow[/math] key)
      T [math]\rightarrow[/math] right = delete(x, T [math]\rightarrow[/math] right)
   else
      ...создать пустое дерево Q
      Q = merge(T [math]\rightarrow[/math] left, T [math]\rightarrow[/math] right)
      T = Q
   return T
// сливает деревья L и R
// результат: дерево T
Node merge(L, R)
   int m = L [math]\rightarrow[/math] size
   int n = R [math]\rightarrow[/math] size
   int total = m + n
   if (total = 0)
      ...вернуть пустое T
   int r = random(1..total)
   if (r < m)
      // с вероятностью m / (m + n)
      L [math]\rightarrow[/math] right = merge(L [math]\rightarrow[/math] right, R)
      return L
   if (r < m)
      // с вероятностью m / (m + n)
      R [math]\rightarrow[/math] left = merge(L, R [math]\rightarrow[/math] left)
      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]T = merge(L, R)[/math] — случайное бинарное дерево поиска, содержащее множество ключей [math]K[/math] = [math]K_{L} \cap K_{R}[/math].
Теорема:
Если [math]T[/math] — случайное бинарное дерево поиска, содержащее множество ключей [math]K[/math], тогда процедура delete(x, T) вернёт случайное бинарное дерево поиска [math]T[/math], содержащее множество ключей [math]K \ x[/math]

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

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

Смотри также

Ссылки

Литература

  • Martínez, Conrado; Roura, Salvador (1997), "Randomized binary search trees", Journal of the ACM 45 (2): 288–323
  • Seidel, Raimund; Aragon, Cecilia R. «Randomized Search Trees», 1996 г.
  • Randomized binary search trees. Lecture notes from a course by Jeff Erickson at UIUC. Despite the title, this is primarily about treaps and skip lists; randomized binary search trees are mentioned only briefly.