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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 5 участников)
Строка 2: Строка 2:
  
 
==Основная идея и связанные определения==
 
==Основная идея и связанные определения==
Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, а следовательно запрос будет выполняться за <tex>O(n)</tex>. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.
+
Как известно, можно подобрать такую последовательность операций с [[Дерево поиска, наивная реализация|бинарным деревом поиска в наивной реализации]], что его глубина будет пропорциональна количеству ключей, а следовательно операции будут выполняться за <tex>O(n)</tex>. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим.
 
Дадим рекурсивное определение '''рандомизированного бинарного дерева поиска (RBST)'''.
 
Дадим рекурсивное определение '''рандомизированного бинарного дерева поиска (RBST)'''.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
Пусть <tex>T</tex> {{---}} бинарное дерево поиска. Тогда
 
Пусть <tex>T</tex> {{---}} бинарное дерево поиска. Тогда
# Если <tex>T</tex> пусто, то оно является рандомизированным бинарным деревом поиска.
+
# Если <tex>T</tex> пусто, то оно является '''рандомизированным бинарным деревом поиска'''.
# Если <tex>T</tex> непусто (содержит <tex>n</tex> вершин, <tex>n > 0</tex>), то <tex>T</tex> {{---}} рандомизированное бинарное дерево поиска тогда и только тогда, когда его левое и правое поддеревья (<tex>L</tex> и <tex>R</tex>) оба являются RBST, а также выполняется соотношение
+
# Если <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] = \dfrac{1}n, i = 1..n</tex>.
<tex>P[size(L) = i] = \frac{1}n, i = 1..n</tex>.
 
 
}}
 
}}
Из определения следует, что каждый ключ в RBST размера n может оказаться корнем с вероятностью <tex dpi="150">\frac{1}{n}</tex>.
+
Из определения следует, что каждый ключ в RBST размера <tex>n</tex> может оказаться корнем с вероятностью <tex>\dfrac{1}{n}</tex>.
  
 
Идея RBST состоит в том, что хранимое дерево постоянно является рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
 
Идея RBST состоит в том, что хранимое дерево постоянно является рандомизированным бинарным деревом поиска. Далее подробно будет описана реализация операций над RBST, которая позволит добиться этой цели. Заметим лишь, что хранение RBST в памяти ничем не отличается от хранения обычного дерева поиска: хранится указатель на корень; в каждой вершине хранятся указатели на её сыновей.
Строка 23: Строка 22:
 
===Вставка===
 
===Вставка===
  
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex dpi = "150">\frac{1}{n+1}</tex> вставим ключ в корень дерева, используя процедуру <tex>\mathrm{insert\_at\_root}</tex>. С вероятностью <tex dpi = "150">1 - \frac{1}{n+1} = \frac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше. Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insert\_at\_root}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация. (через <tex>Node</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> обозначен тип вершины дерева, дерево представляется как указатель на корень).
  
  '''Node''' insert(T, x)
+
  '''Node''' insert(t : '''Node''', x : '''T'''):
     '''int''' r = '''random'''(0..T.size))
+
     '''int''' r = '''random'''(0 <tex>\dots</tex> t.size)
     '''if''' r == n
+
     '''if''' r == t.size
       T = insert_at_root(T, x)
+
       t = insertAtRoot(t, x)
     '''if''' x < root.key
+
     '''if''' x < t.key
       T = insert(T.left, x)
+
       t = insert(t.left, x)
 
     '''else'''
 
     '''else'''
       T = insert(T.right, x)
+
       t = insert(t.right, x)
     '''return''' T
+
    t.size = 1 + t.size
 +
     '''return''' t
  
 
Заметим, что если дерево пусто, то <tex>\mathrm{insert}</tex> с вероятностью 1 делает <tex>x</tex> корнем.
 
Заметим, что если дерево пусто, то <tex>\mathrm{insert}</tex> с вероятностью 1 делает <tex>x</tex> корнем.
  
  '''Node''' insert_at_root(T, x)        <font color="green">// вставляем в дерево T ключ x</font>
+
  '''Node''' insertAtRoot(t : '''Node''', x : '''T'''):       <font color="green">// вставляем в дерево t ключ x</font>
     L = RBST()                    <font color="green">// создать пустые L и R</font>
+
     <l, r> = split(t, x)
    R = RBST()
+
     t.key = x
    split(T, x, L, R)
+
     t.left = l
     T = RBST()                    <font color="green">// создать пустое T</font>
+
     t.right = r
    T.key = x
+
     '''return''' t
     T.left = L
 
     T.left = R
 
     '''return''' T
 
  
  split(T, x, L, R)              <font color="green"> // разделяет дерево T по x, результат - деревья L и R</font>
+
  '''<Node''', '''Node>''' split(t : '''Node''', x : '''T'''):               <font color="green"> // разделяет дерево t по x, результат {{---}} пара деревьев r и l</font>
     '''if''' T.size == 0
+
     '''if''' t.size == 0
       L = RBST()
+
       '''return''' <''null'', ''null''>
      R = RBST()
+
     '''else if''' x < t.key
     '''else if''' x < T.key
+
       <l, r> = split(t.left, x)
       R = T
+
      t.left = r
      split(T.left, x, L, R.left)
+
      t.size = 1 + t.left.size + t.right.size
 +
      r = t
 +
      '''return''' <l, r>
 
     '''else'''
 
     '''else'''
       L = T
+
       <l, r> = split(t.right, x)
      split(T.right, x, L.right, R)
+
      t.right = l
 +
      t.size = 1 + t.left.size + t.right.size
 +
      l = t
 +
      '''return''' <l, r>
  
 
Далее рассмотрим как меняется свойство дерева быть рандомизированным при вставке в него ключей.
 
Далее рассмотрим как меняется свойство дерева быть рандомизированным при вставке в него ключей.
Строка 67: Строка 70:
 
Пусть <tex>n > 0</tex>, и лемма верна при всех меньших размерах дерева.. Пусть также <tex>y = T.key, L = T.left, R = T.right</tex>. Если <tex>x > y</tex>, то <tex>y</tex> {{---}} корень <tex>T_{L}</tex>, <tex>L</tex> {{---}} левое поддерево <tex>T_{L}</tex>, а <tex>\mathrm{split}</tex> рекурсивно вызовется от <tex>R</tex>, разделив его на <tex>R'</tex> {{---}} правое поддерево <tex>T_{L}</tex> {{---}}, и <tex>T_{R}</tex>, которые по предположению индукции будут рандомизированными бинарными деревьями поиска. Но <tex>L</tex> также является RBST, т.к. является поддеревом <tex>T</tex>.
 
Пусть <tex>n > 0</tex>, и лемма верна при всех меньших размерах дерева.. Пусть также <tex>y = T.key, L = T.left, R = T.right</tex>. Если <tex>x > y</tex>, то <tex>y</tex> {{---}} корень <tex>T_{L}</tex>, <tex>L</tex> {{---}} левое поддерево <tex>T_{L}</tex>, а <tex>\mathrm{split}</tex> рекурсивно вызовется от <tex>R</tex>, разделив его на <tex>R'</tex> {{---}} правое поддерево <tex>T_{L}</tex> {{---}}, и <tex>T_{R}</tex>, которые по предположению индукции будут рандомизированными бинарными деревьями поиска. Но <tex>L</tex> также является RBST, т.к. является поддеревом <tex>T</tex>.
  
Итак для того, чтобы доказать, что <tex>T_{L}</tex> {{---}} рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина <tex>z</tex> с вероятностью <tex dpi = "150">\frac{1}{m}</tex> окажется в корне, где <tex>m</tex> {{---}} размер <tex>T_{L}</tex>. Действительно:
+
Итак для того, чтобы доказать, что <tex>T_{L}</tex> {{---}} рандомизированное бинарное дерево поиска, осталось показать, что любая его вершина <tex>z</tex> с вероятностью <tex>\dfrac{1}{m}</tex> окажется в корне, где <tex>m</tex> {{---}} размер <tex>T_{L}</tex>. Действительно:
  
 
(пусть событие <tex>A</tex> {{---}} <tex>z</tex> является коренем <tex>T_{L}</tex>)
 
(пусть событие <tex>A</tex> {{---}} <tex>z</tex> является коренем <tex>T_{L}</tex>)
  
<tex dpi = "150">P[A \mid y < x] = \frac{P[A \; \wedge \; y < x]}{P[y < x]} = \frac{1 / n}{m / n} = \frac{1}{m}</tex>
+
<tex dpi = "150">P[A \mid y < x] = \dfrac{P[A \; \wedge \; y < x]}{P[y < x]} = \dfrac{1 / n}{m / n} = \dfrac{1}{m}</tex>
  
 
Случай, когда <tex>x < y</tex> симметричен рассмотренному.
 
Случай, когда <tex>x < y</tex> симметричен рассмотренному.
Строка 77: Строка 80:
  
 
{{Теорема  
 
{{Теорема  
|statement= Если <tex>T</tex> {{---}} рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура <tex>\mathrm{insert(x, T)}</tex> вернёт рандомизированное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cap x</tex>.
+
|statement= Если <tex>T</tex> {{---}} рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex>, <tex>x \notin K</tex>, тогда процедура <tex>\mathrm{insert(x, T)}</tex> вернёт рандомизированное бинарное дерево поиска <tex>T</tex>, содержащее множество ключей <tex>K \cup x</tex>.
 
|proof=
 
|proof=
 
Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то теорема верна: после операции <tex>\mathrm{insert(x, T)}</tex> получим дерево с корнем <tex>x</tex> и двумя пустыми поддеревьями.
 
Применим индукцию по <tex>n</tex> {{---}} размеру дерева. Если <tex>n = 0</tex>, то теорема верна: после операции <tex>\mathrm{insert(x, T)}</tex> получим дерево с корнем <tex>x</tex> и двумя пустыми поддеревьями.
Строка 83: Строка 86:
 
Пусть <tex>n > 0</tex>, и теорема верна при всех меньших размерах дерева. Возможны два случая: <tex>x</tex> вставляется в корень или рекурсивно в одно из поддеревьев.
 
Пусть <tex>n > 0</tex>, и теорема верна при всех меньших размерах дерева. Возможны два случая: <tex>x</tex> вставляется в корень или рекурсивно в одно из поддеревьев.
  
В первом случае правое и левое поддеревья <tex>x</tex> по лемме являются рандомизированными BST, а также вероятность того, что <tex>x</tex> окажется в корне, равна <tex dpi = "150">\frac{1}{n + 1}</tex>. Т.е. новое дерево {{---}} рандомизированное BST.
+
В первом случае правое и левое поддеревья <tex>x</tex> по лемме являются рандомизированными BST, а также вероятность того, что <tex>x</tex> окажется в корне, равна <tex>\dfrac{1}{n + 1}</tex>. Т.е. новое дерево {{---}} рандомизированное BST.
  
Во втором случае корень у дерева останется прежнем. Заметим, что для каждого <tex>y \in K</tex> вероятность быть корнем была <tex dpi = "150">\frac{1}{n}</tex>, а корнем он останется с вероятностью <tex dpi = "150">\frac{n}{n + 1}</tex>, тогда для каждого <tex>y \in K</tex> вероятность быть корнем равна <tex dpi = "150">\frac{1}{n} \cdot \frac{n}{n + 1} = \frac{1}{n + 1}</tex>. По предположению же индукции поддерево, в которое вставляется <tex>x</tex> становится рандомизированным бинарным деревом поиска; а т.к. другое поддерево корня было рандомизированным, то новое дерево {{---}} рандомизированное BST.
+
Во втором случае корень у дерева останется прежнем. Заметим, что для каждого <tex>y \in K</tex> вероятность быть корнем была <tex>\dfrac{1}{n}</tex>, а корнем он останется с вероятностью <tex>\dfrac{n}{n + 1}</tex>, тогда для каждого <tex>y \in K</tex> вероятность быть корнем равна <tex>\dfrac{1}{n} \cdot \dfrac{n}{n + 1} = \dfrac{1}{n + 1}</tex>. По предположению же индукции поддерево, в которое вставляется <tex>x</tex> становится рандомизированным бинарным деревом поиска; а т.к. другое поддерево корня было рандомизированным, то новое дерево {{---}} рандомизированное BST.
 
}}
 
}}
  
Строка 94: Строка 97:
 
Алгоритм удаления использует операцию <tex>\mathrm{merge}</tex> {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.
 
Алгоритм удаления использует операцию <tex>\mathrm{merge}</tex> {{---}} слияние двух деревьев, удовлетворяющих условию: все ключи в одном из деревьев меньше ключей во втором. Для того, чтобы удалить некоторый ключ <tex>x</tex> из RBST сначала найдём вершину с этим ключом в дереве, используя стандартный алгоритм поиска. Если вершина не найдена, то выходим из алгоритма; в противном случае сливаем правое и левое поддеревья <tex>x</tex> (заметим, что ключи в левом поддереве меньше ключей в правом), удаляем <tex>x</tex>, а корень образовавшегося дерева делаем новым сыном родителя <tex>x</tex>. Псевдокод процедур удаления и слияния приведён ниже.
  
  '''Node''' remove(T, x)                   <font color="green">// удаляет ключ x из дерева T</font>
+
  '''Node''' remove(t : '''Node''', x : '''T'''):      <font color="green">// удаляет ключ x из дерева T</font>
     '''if''' T.size == 0
+
     '''if''' t.size == 0
       T = RBST()
+
       t = ''null''
       '''return''' T                     <font color="green">// вернуть пустое поддерево</font>
+
       '''return''' t                     <font color="green">// вернуть пустое поддерево</font>
     '''if''' x < T.key
+
     '''if''' x < t.key
       T.left = remove(T.left, x)
+
       t.left = remove(t.left, x)
     '''else if''' x > T.key
+
     '''else if''' x > t.key
       T.right = remove(T.right, x)
+
       t.right = remove(t.right, x)
 
     '''else'''
 
     '''else'''
       Q = RBST()
+
       q = merge(t.left, t.right)
      Q = merge(T.left, T.right)
+
       t = q
       T = Q
+
     '''return''' t
     '''return''' T
 
  
  '''Node''' merge(L, R)                           <font color="green">// сливает деревья L и R, результат - дерево T</font>
+
  '''Node''' merge(l : '''Node''', r : '''Node'''):            <font color="green">// сливает деревья l и r, результат {{---}} дерево t</font>
     '''int''' m = L.size
+
     '''int''' m = l.size
     '''int''' n = R.size
+
     '''int''' n = r.size
 
     '''int''' total = m + n
 
     '''int''' total = m + n
 
     '''if''' total == 0
 
     '''if''' total == 0
       T = RBST()
+
       t = ''null''
       '''return''' T                             <font color="green">// вернуть пустое поддерево</font>
+
       '''return''' t                             <font color="green">// вернуть пустое поддерево</font>
     '''int''' r = '''random'''(1..total)
+
     '''int''' r = '''random'''(1 <tex>\dots</tex> total)
 
     '''if''' r < m
 
     '''if''' r < m
       L.right = merge(L.right, R)          <font color="green">// с вероятностью m / (m + n)</font>
+
       l.right = merge(l.right, r)          <font color="green">// с вероятностью m / (m + n)</font>
       '''return''' L
+
      l.size = 1 + l.left.size + l.right.size
     '''if''' r < m
+
       '''return''' l
      R.left = merge(L, R.left)            <font color="green">// с вероятностью m / (m + n)</font>
+
     r.left = merge(l, r.left)            <font color="green">// с вероятностью n / (m + n)</font>
      '''return''' R
+
    r.size = 1 + r.left.size + r.right.size
 +
    '''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>\mathrm{merge(L, R)}</tex> вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex> = <tex>K_{L} \cap K_{R}</tex>.
+
|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>\mathrm{merge(L, R)}</tex> вернёт рандомизированное бинарное дерево поиска, содержащее множество ключей <tex>K</tex> = <tex>K_{L} \cup K_{R}</tex>.
 
|proof=
 
|proof=
 
Пусть <tex>m</tex> и <tex>n</tex> {{---}} размеры <tex>L</tex> и <tex>R</tex> соответственно. Применим индукцию по <tex>m</tex> и <tex>n</tex>. Если <tex>m = 0</tex> или <tex>n = 0</tex>, то лемма верна.
 
Пусть <tex>m</tex> и <tex>n</tex> {{---}} размеры <tex>L</tex> и <tex>R</tex> соответственно. Применим индукцию по <tex>m</tex> и <tex>n</tex>. Если <tex>m = 0</tex> или <tex>n = 0</tex>, то лемма верна.
  
Пусть <tex>m > 0</tex> и <tex>n > 0</tex>, пусть также <tex>L.key = a</tex> или <tex>L.key = b</tex>. Без потери общности делаем корнем <tex>a</tex>. После рекурсивного слияния правого поддерева <tex>L</tex> и <tex>R</tex> получим рандомизированное бинарное дерево поиска (которое является правым поддеревом нового дерева). Левое же поддерево нового дерева тоже рандомизированное. Также верно, что для любого <tex>x \in K_{L}</tex> вероятность быть корнем равна <tex dpi = "150">\frac{1}{m + n}</tex>: действительно, вероятность оказаться в корне в <tex>L</tex> до слияния равна <tex dpi = "150">\frac{1}{m}</tex>, вероятность того, что элемент останется корнем после слияния равна <tex dpi = "150">\frac{m}{m + n}</tex>; осталось применить правило умножения.
+
Пусть <tex>m > 0</tex> и <tex>n > 0</tex>, пусть также <tex>L.key = a</tex> или <tex>L.key = b</tex>. Без потери общности делаем корнем <tex>a</tex>. После рекурсивного слияния правого поддерева <tex>L</tex> и <tex>R</tex> получим рандомизированное бинарное дерево поиска (которое является правым поддеревом нового дерева). Левое же поддерево нового дерева тоже рандомизированное. Также верно, что для любого <tex>x \in K_{L}</tex> вероятность быть корнем равна <tex>\dfrac{1}{m + n}</tex>: действительно, вероятность оказаться в корне в <tex>L</tex> до слияния равна <tex>\dfrac{1}{m}</tex>, вероятность того, что элемент останется корнем после слияния равна <tex>\dfrac{m}{m + n}</tex>; осталось применить правило умножения.
 
}}
 
}}
  
Строка 140: Строка 143:
 
Пусть <tex>x \in T</tex> (дерево не пусто), <tex>n</tex> {{---}} размер <tex>T</tex>. Докажем теорему по индукции по <tex>n</tex>. Для <tex>n = 1</tex> теорема очевидным образом верна. Пусть <tex>n > 1</tex>, и предположим, что теорема верна для всех деревьев размера меньше <tex>n</tex>.
 
Пусть <tex>x \in T</tex> (дерево не пусто), <tex>n</tex> {{---}} размер <tex>T</tex>. Докажем теорему по индукции по <tex>n</tex>. Для <tex>n = 1</tex> теорема очевидным образом верна. Пусть <tex>n > 1</tex>, и предположим, что теорема верна для всех деревьев размера меньше <tex>n</tex>.
  
Возможно два случая: если <tex>x</tex> {{---}} корень <tex>T</tex>, то по лемме, после удаления получим рандомизированное бинарное дерево поиска; если же <tex>x</tex> {{---}} не корень <tex>T</tex>, то <tex>x</tex> рекурсивно удаляется из поддерева исходного дерева, и по предположению индукции после удаления получаем рандомизированное BST. Осталось лишь показать, что для любого <tex>y \in T, y \neq x</tex> вероятность оказаться корнем после удаления равна <tex dpi = "150">\frac{1}{n - 1}</tex>.
+
Возможно два случая: если <tex>x</tex> {{---}} корень <tex>T</tex>, то по лемме, после удаления получим рандомизированное бинарное дерево поиска; если же <tex>x</tex> {{---}} не корень <tex>T</tex>, то <tex>x</tex> рекурсивно удаляется из поддерева исходного дерева, и по предположению индукции после удаления получаем рандомизированное BST. Осталось лишь показать, что для любого <tex>y \in T, y \neq x</tex> вероятность оказаться корнем после удаления равна <tex>\dfrac{1}{n - 1}</tex>.
  
 
Введём обозначения:
 
Введём обозначения:
Строка 155: Строка 158:
  
 
<tex>P[A] = P[A \mid B] \cdot P[B] + P[A\mid\neg B] \cdot P[\neg B] = P[C] \cdot 1/n + P[D\mid\neg B] \cdot (n - 1)/n = </tex>
 
<tex>P[A] = P[A \mid B] \cdot P[B] + P[A\mid\neg B] \cdot P[\neg B] = P[C] \cdot 1/n + P[D\mid\neg B] \cdot (n - 1)/n = </tex>
<tex dpi = "150">\frac{1}{n - 1} \cdot \frac{1}{n} + \frac{1}{n - 1} \cdot \frac{n - 1}{n} = \frac{1}{n - 1}</tex>.
+
<tex>\dfrac{1}{n - 1} \cdot \dfrac{1}{n} + \dfrac{1}{n - 1} \cdot \dfrac{n - 1}{n} = \dfrac{1}{n - 1}</tex>.
 
}}
 
}}
  
 
==Анализ времени работы==
 
==Анализ времени работы==
  
Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <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 />
*[[Дерево поиска, наивная реализация]]
 
*[[Декартово дерево]]
 
*[[Декартово дерево по неявному ключу]]
 
  
 
== Источники информации ==
 
== Источники информации ==
Строка 174: Строка 181:
 
* Seidel, Raimund; Aragon, Cecilia R. [http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf «Randomized Search Trees»], 1996 г.
 
* 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.
 
* [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.
 +
* [https://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf Binary Search Trees]. Robert Sedgewick and Kevin Wayne - Algorithms and Data Structures course.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Деревья поиска]]
 
[[Категория: Деревья поиска]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:17, 4 сентября 2022

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

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

Как известно, можно подобрать такую последовательность операций с бинарным деревом поиска в наивной реализации, что его глубина будет пропорциональна количеству ключей, а следовательно операции будут выполняться за [math]O(n)[/math]. Поэтому, если поддерживать инвариант "случайности" в дереве, то можно добиться того, что математическое ожидание глубины дерева будет небольшим. Дадим рекурсивное определение рандомизированного бинарного дерева поиска (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] = \dfrac{1}n, i = 1..n[/math].

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

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

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

Операции

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

Вставка

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

Node insert(t : Node, x : T):
   int r = random(0 [math]\dots[/math] 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

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

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>

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

Лемма:
Пусть после операции [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 \mid y \lt x\}[/math] и [math]K_{R} = \{y \in K \mid 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]\dfrac{1}{m}[/math] окажется в корне, где [math]m[/math] — размер [math]T_{L}[/math]. Действительно:

(пусть событие [math]A[/math][math]z[/math] является коренем [math]T_{L}[/math])

[math]P[A \mid y \lt x] = \dfrac{P[A \; \wedge \; y \lt x]}{P[y \lt x]} = \dfrac{1 / n}{m / n} = \dfrac{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 \cup 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]\dfrac{1}{n + 1}[/math]. Т.е. новое дерево — рандомизированное BST.

Во втором случае корень у дерева останется прежнем. Заметим, что для каждого [math]y \in K[/math] вероятность быть корнем была [math]\dfrac{1}{n}[/math], а корнем он останется с вероятностью [math]\dfrac{n}{n + 1}[/math], тогда для каждого [math]y \in K[/math] вероятность быть корнем равна [math]\dfrac{1}{n} \cdot \dfrac{n}{n + 1} = \dfrac{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 : 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 [math]\dots[/math] 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

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

Лемма:
Пусть [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} \cup 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]\dfrac{1}{m + n}[/math]: действительно, вероятность оказаться в корне в [math]L[/math] до слияния равна [math]\dfrac{1}{m}[/math], вероятность того, что элемент останется корнем после слияния равна [math]\dfrac{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]\dfrac{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 \mid B] \cdot P[B] + P[A\mid\neg B] \cdot P[\neg B] = P[C] \cdot 1/n + P[D\mid\neg B] \cdot (n - 1)/n = [/math]

[math]\dfrac{1}{n - 1} \cdot \dfrac{1}{n} + \dfrac{1}{n - 1} \cdot \dfrac{n - 1}{n} = \dfrac{1}{n - 1}[/math].
[math]\triangleleft[/math]

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

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

См. также

Примечания

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stei, "Introduction to Algorithms", Second Edition — Chapter 12.4

Источники информации