Взвешенное дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 41 промежуточная версия 3 участников)
Строка 1: Строка 1:
 
 
'''Scapegoat-tree'''  {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее  время поиска {{---}} <tex>O(\log N)</tex>, и  амортизирующее время вставки и удаления элемента {{---}} <tex>O(\log N)</tex>.
 
'''Scapegoat-tree'''  {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее  время поиска {{---}} <tex>O(\log N)</tex>, и  амортизирующее время вставки и удаления элемента {{---}} <tex>O(\log N)</tex>.
В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
+
В отличие от большинства других самобалансирующихся бинарных деревьев поиска, которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
 
 
  
 
== Операции ==
 
== Операции ==
 +
<center>
 +
{| class="wikitable"
 +
|-
 +
! rowspan="2" | Операции
 +
! colspan="2" | Insert
 +
! colspan="2" | Delete
 +
! colspan="2" | Search
 +
! colspan="2" | Память
 +
|-
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
! style="background: #ddffdd;" | Среднее
 +
! style="background: #ffdddd;" | Худшее
 +
|-
 +
| Scapegoat-tree
 +
| align="center" style="background: #ddffdd;" | <tex>O(log\ n)</tex>
 +
| align="center" style="background: #ffdddd;" | Амортизировано <tex>O(log\ n)</tex>
 +
| align="center" style="background: #ddffdd;" | <tex>O(log n)</tex>
 +
| align="center" style="background: #ffdddd;" | Амортизировано <tex>O(log\ n)</tex>
 +
| colspan="2" align="center" style="background: #ddffdd;" | <tex>O(log\ n)</tex>
 +
| colspan="2" align="center" style="background: #ffffdd;" | <tex>O(n)</tex>
 +
|}
 +
</center>
 
===Обозначения и Определения===
 
===Обозначения и Определения===
  
 
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
 
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
<tex>T</tex> — обозначение дерева,
+
 
<tex>root[T]</tex> — корень дерева <tex>T</tex>,  
+
<tex>\mathtt{T}</tex> — обозначение дерева,
<tex>left[x]</tex> — левый сын вершины <tex>x</tex>,
+
 
<tex>right[x]</tex> — правый сын вершины <tex>x</tex>,
+
<tex>\mathtt{root[T]}</tex> — корень дерева <tex>T</tex>,  
 +
 
 +
<tex>\mathtt{left[x]}</tex> — левый сын вершины <tex>x</tex>,
 +
 
 +
<tex>\mathtt{right[x]}</tex> — правый сын вершины <tex>x</tex>,
 +
 
 
<tex>\mathtt{brother(x)}</tex> — брат вершины <tex>x</tex> (вершина, которая имеет с <tex>x</tex> общего родителя),
 
<tex>\mathtt{brother(x)}</tex> — брат вершины <tex>x</tex> (вершина, которая имеет с <tex>x</tex> общего родителя),
<tex>\mathtt{depth(x)}</tex> — глубина вершины <tex>x</tex>(количество рёбер от нее до корня),
+
 
<tex>\mathtt{height(T)}</tex> — глубина дерева <tex>T</tex>(глубина самой глубокой вершины дерева <tex>T</tex>),
+
<tex>\mathtt{depth(x)}</tex> — глубина вершины <tex>x</tex> (количество рёбер от нее до корня),
<tex>\mathtt{weight(x)}</tex> — вес вершины <tex>x</tex>(количество всех её дочерних вершин плюс <tex>1</tex> {{---}} она сама),
+
 
<tex>\mathtt{weight[T]}</tex> — размер дерева <tex>T</tex>(количество вершин в нём),
+
<tex>\mathtt{height(T)}</tex> — глубина дерева <tex>T</tex> (глубина самой глубокой вершины дерева <tex>T</tex>),
<tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева(максимальное значение, которое параметр <tex>weight[T]</tex> принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>
+
 
[[Файл:0ce162a62b624da8ba02233b4b254f23.png]]
+
<tex>\mathtt{weight(x)}</tex> — вес вершины <tex>x</tex> (количество всех её дочерних вершин плюс <tex>1</tex> {{---}} она сама),
 +
 
 +
<tex>\mathtt{weight[T]}</tex> — размер дерева <tex>T</tex> (количество вершин в нём),
 +
 
 +
<tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева (максимальное значение, которое параметр <tex>\mathtt{weight[T]}</tex> принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>
 +
 
 +
[[Файл:0ce162a62b624da8ba02233b4b254f23.png|380px|right]]
  
 
Синим цветом обозначены '''глубины''' вершин, а красным {{---}} их '''веса'''.
 
Синим цветом обозначены '''глубины''' вершин, а красным {{---}} их '''веса'''.
Строка 27: Строка 63:
 
Коэффициeнт <tex>\alpha</tex> — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.  
 
Коэффициeнт <tex>\alpha</tex> — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.  
 
{{Определение
 
{{Определение
|definition=Некоторая вершина <tex>x</tex> называется '''<tex>\alpha</tex>-сбалансированной по весу''', если <tex>\mathtt{weight(left[x])} \leqslant \alpha  \cdot weight(x)</tex> и <tex>\mathtt{weight(right[x])} \leqslant \alpha \cdot size(x)</tex>.}}  
+
|definition=Некоторая вершина <tex>x</tex> называется '''<tex>\alpha</tex>-сбалансированной по весу''', если <tex>\mathtt{weight(left[x])} \leqslant \alpha  \cdot \mathtt{weight(x)}</tex> и <tex>\mathtt{weight(right[x])} \leqslant \alpha \cdot \mathtt{weight(x)}</tex>.}}  
 +
 
 +
 
 +
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>\mathtt {weight[T]}</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.
 +
 
 +
=== Структура вершины ===
  
 +
'''struct''' Node:
 +
  '''T''' key                  <font color=green> //значение в вершине </font>
 +
  '''Node''' left              <font color=green> //левый ребенок вершины </font>
 +
  '''Node''' right              <font color=green> //правый ребенок вершины </font>
 +
  '''Node''' height            <font color=green> //высота поддерева данной вершины </font>
 +
  '''Node''' depth              <font color=green> //глубина вершины </font>
 +
  '''Node''' parent            <font color=green> //ссылка на родителя </font>
 +
  '''Node''' sibling            <font color=green> //ссылки на "братьев" данной вершины </font>
  
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>weight[T]</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.
 
 
=== Поиск элемента ===
 
=== Поиск элемента ===
 
Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет <tex>O(\log_\frac{1}{\alpha} (N))</tex>.
 
Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет <tex>O(\log_\frac{1}{\alpha} (N))</tex>.
  
Таким образом, сложность получается логарифмическая, НО! При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную  скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
+
Таким образом, сложность получается логарифмическая, '''но!''' При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную  скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
 +
 
 +
*<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
 +
*<tex>k</tex> {{---}} искомый ключ в дереве.
 +
 
 +
'''Search'''(root, k):
 +
  '''if ''' root = <tex>\varnothing</tex> or root.key = k:
 +
      '''return ''' root
 +
  '''else if ''' k <tex>\leqslant</tex> root.left.key:
 +
      '''return ''' Search(root.left, k)
 +
  '''else''':
 +
      '''return ''' Search(root.right, k)
 +
 
 
=== Вставка элемента ===
 
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти  Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной  стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос - нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева —  есть стек, в котором находится весь путь от корня к новой вершине. Берутся родителей из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу.  
+
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти  Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной  стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос {{---}} нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева —  есть стек, в котором находится весь путь от корня к новой вершине. Берутся родители из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу.  
 
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
 
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
Есть 2 способа перебалансировки, {{---}} тривиальный и чуть более сложный.
+
Есть <tex>2</tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
 
====Тривиальный способ перебалансировки====
 
====Тривиальный способ перебалансировки====
 
# совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
 
# совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
Строка 44: Строка 104:
 
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
 
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
 
Данный способ требует  <tex>O\mathtt{(weight(Scapegoat-root))}</tex> времени и столько же памяти.
 
Данный способ требует  <tex>O\mathtt{(weight(Scapegoat-root))}</tex> времени и столько же памяти.
 +
 +
==== Получение списка ====
 +
 +
*<tex>root</tex> {{---}} корень дерева, которое будет преобразовано в список.
 +
 +
'''FlattenTree'''(root, head):
 +
  '''if''' root = <tex>\varnothing</tex>:
 +
      '''return''' head
 +
  root.right = FlattenTree(root.right, head)
 +
  '''return''' FlattenTree(root.left, root)
 +
 +
==== Построение дерева ====
 +
 +
*<tex>size</tex> {{---}} число вершин в списке.
 +
*<tex>head</tex> {{---}} первая вершина в списке.
 +
 +
BuildHeightBalancedTree(size, head):
 +
  '''if''' size = 1 then:
 +
      return head
 +
  '''else if''' size = 2 then:
 +
      (head.right).left = head
 +
      '''return''' head.right
 +
  root = (BuildHeightBalancedTree(⌊(size − 1)/2⌋, head)).right
 +
  last = BuildHeightBalancedTree(⌊(size − 1)/2⌋, root.right)
 +
  root.left = head
 +
  '''return''' last
 +
 +
==== Перестроение дерева ====
 +
 +
*<tex>size</tex> {{---}} число вершин в поддереве.
 +
*<tex>scapegoat</tex> {{---}} вершина, которая испортила баланс.
 +
'''RebuildTree'''(size, scapegoat):
 +
  head = '''FlattenTree'''(scapegoat, <tex>\varnothing</tex>)
 +
  '''BuildHeightBalancedTree'''(size, head)
 +
  '''while''' head.parent <tex>\ne \varnothing </tex>
 +
      head = head.parent
 +
  '''return''' head
 +
 
====Более сложный способ перебалансировки====
 
====Более сложный способ перебалансировки====
Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот выбирается медиану, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке,  будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема —  этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(weight(N))</tex>, а всего лишь <tex>O(\log N)</tex>.
+
Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на <tex>1</tex> способ алгоритма внимательнее. Выбирается медиана, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. То есть для некоторого списка вершин, отсортированных в возрастающем порядке,  будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема —  этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(weight(N))</tex>, а всего лишь <tex>O(\log N)</tex>.
 +
 
 +
Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. То есть расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>\log(3)</tex>.
 +
Таким образом, если нужно сэкономить память, то <tex>2</tex> способ перебалансировки дерева {{---}} лучший вариант.
 +
 
 +
<center>
 +
{| cellpadding="0"
 +
| [[Файл:Good_insert_1.png|400px|thumb|Вставка без нарушения баланса 1]] || [[Файл:Good_insert_2.png|400px|thumb|Вставка без нарушения баланса 2]]
 +
|}
 +
{| cellpadding="0"
 +
|align="center"|[[Файл:Bad_insert.png|595px|thumb|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка]]
 +
|}
 +
</center>
 +
 
 +
====Псевдокод====
 +
 
 +
*<tex>n</tex> {{---}} узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
 +
 
 +
'''FindScapegoat'''(n):
 +
  size = 1
 +
  height = 0
 +
  '''while''' n.parent <tex>\ne \varnothing</tex>:
 +
      height = height + 1
 +
      totalSize = 1 + size + n.sibling.size()
 +
      '''if''' height <tex> > \lfloor \log_\frac{1}{\alpha} (totalSize) \rfloor</tex>:
 +
        '''return''' n.parent
 +
      n = n.parent
 +
      size = totalSize
 +
 
 +
Сама вставка элемента:
 +
 
 +
*<tex>k</tex> {{---}} ключ, который будет добавлен в дерево.
 +
 
 +
'''Insert'''(k):
 +
  height = InsertKey(k)
 +
  '''if''' height = −1:
 +
      '''return''' false;
 +
  '''else if''' height > T.hα:
 +
      scapegoat = '''FindScapegoat'''(Search(T.root, k))
 +
      '''RebuildTree'''(n.size(), scapegoat)
 +
  '''return''' true
  
Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>\log(3)</tex>.
 
Таким образом, если нужно сэкономить память, то 2 способ перебалансировки дерева {{---}} лучший вариант.
 
 
=== Удаление элемента ===
 
=== Удаление элемента ===
 
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).  
 
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).  
 
Далее следует проверка выполнения условия:  
 
Далее следует проверка выполнения условия:  
:<tex>weight[T] < \alpha \cdot \mathtt {maxweight[T]}</tex>;
+
:<tex>\mathtt {weight[T]} < \alpha \cdot \mathtt {maxweight[T]}</tex>;
Если оно выполняется — дерево могло потерять <tex>\alpha</tex> - балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
+
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>\mathtt {maxweight[T]} = weight[T]</tex>;
+
:<tex>\mathtt {maxweight[T]} = \mathtt {weight[T]}</tex>;
 +
 
 +
====Псевдокод====
 +
 
 +
Функция <tex>Delete(k)</tex> удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
 +
 
 +
*<tex>k</tex> {{---}} ключ, который будет удален.
 +
'''Delete'''(k):
 +
  deleted = '''DeleteKey'''(k)
 +
  '''if''' deleted:
 +
      '''if''' T.size < (T.α · T.maxSize):
 +
        '''RebuildTree'''(T.size, T.root)
  
 
==Сравнение с другими деревьями==
 
==Сравнение с другими деревьями==
Строка 64: Строка 211:
 
* В худшем случае операции модификации дерева могут занять <tex>O(N)</tex> времени (амортизированная сложность у них по-прежнему <tex>O(\log N)</tex>, но защиты от плохих случаев нет).
 
* В худшем случае операции модификации дерева могут занять <tex>O(N)</tex> времени (амортизированная сложность у них по-прежнему <tex>O(\log N)</tex>, но защиты от плохих случаев нет).
 
* Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента <tex>\alpha</tex> — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.
 
* Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента <tex>\alpha</tex> — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.
 +
 
==См. также==
 
==См. также==
 
* [[Поисковые структуры данных]]
 
* [[Поисковые структуры данных]]
Строка 74: Строка 222:
 
*[https://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья]<br>
 
*[https://habrahabr.ru/company/infopulse/blog/246759/ Хабрахабр - Scapegoat деревья]<br>
 
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]
 
*[https://people.ksp.sk/~kuko/gnarley-trees/ Scapegoat Tree Applet by Kubo Kovac]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Деревья поиска]]

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

Scapegoat-tree — сбалансированное двоичное дерево поиска, обеспечивающее наихудшее время поиска — [math]O(\log N)[/math], и амортизирующее время вставки и удаления элемента — [math]O(\log N)[/math]. В отличие от большинства других самобалансирующихся бинарных деревьев поиска, которые обеспечивают худшем случае [math]O(\log N)[/math] время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.

Операции

Операции Insert Delete Search Память
Среднее Худшее Среднее Худшее Среднее Худшее Среднее Худшее
Scapegoat-tree [math]O(log\ n)[/math] Амортизировано [math]O(log\ n)[/math] [math]O(log n)[/math] Амортизировано [math]O(log\ n)[/math] [math]O(log\ n)[/math] [math]O(n)[/math]

Обозначения и Определения

Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время [math]O(1)[/math]. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.

[math]\mathtt{T}[/math] — обозначение дерева,

[math]\mathtt{root[T]}[/math] — корень дерева [math]T[/math],

[math]\mathtt{left[x]}[/math] — левый сын вершины [math]x[/math],

[math]\mathtt{right[x]}[/math] — правый сын вершины [math]x[/math],

[math]\mathtt{brother(x)}[/math] — брат вершины [math]x[/math] (вершина, которая имеет с [math]x[/math] общего родителя),

[math]\mathtt{depth(x)}[/math] — глубина вершины [math]x[/math] (количество рёбер от нее до корня),

[math]\mathtt{height(T)}[/math] — глубина дерева [math]T[/math] (глубина самой глубокой вершины дерева [math]T[/math]),

[math]\mathtt{weight(x)}[/math] — вес вершины [math]x[/math] (количество всех её дочерних вершин плюс [math]1[/math] — она сама),

[math]\mathtt{weight[T]}[/math] — размер дерева [math]T[/math] (количество вершин в нём),

[math]\mathtt{maxweight[T]}[/math] — максимальный размер дерева (максимальное значение, которое параметр [math]\mathtt{weight[T]}[/math] принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то [math]\mathtt{maxweight[T]} = \mathtt{weight[T]}[/math]

0ce162a62b624da8ba02233b4b254f23.png

Синим цветом обозначены глубины вершин, а красным — их веса. Считается вес вершины следующим образом: для новой вершины вес равен [math]1[/math]. Для её родителя [math]\mathtt{weight} = 1[/math] (вес новой вершины) [math]+ 1[/math] (вес самого родителя) [math]+ \mathtt{weight(brother(x))}[/math]. Возникает вопрос — как посчитать [math]\mathtt{weight(brother(x))}[/math]? Делается это рекурсивно. Это займёт время [math]O\mathtt{(weight(brother(x)))}[/math]. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность [math]O(N)[/math] в худшем случае, о которой говорилось в начале. Но поскольку совершается обход поддерева [math]\alpha[/math]-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит [math]O(\log N)[/math]. В данном Scapegoat-дереве [math]weight[T] = 4[/math], [math]\mathtt{maxweight[T]} \geqslant 4[/math]

Коэффициeнт [math]\alpha[/math] — это число в диапазоне от [math][0.5; 1)[/math], определяющее требуемую степень качества балансировки дерева.

Определение:
Некоторая вершина [math]x[/math] называется [math]\alpha[/math]-сбалансированной по весу, если [math]\mathtt{weight(left[x])} \leqslant \alpha \cdot \mathtt{weight(x)}[/math] и [math]\mathtt{weight(right[x])} \leqslant \alpha \cdot \mathtt{weight(x)}[/math].


Перед тем как приступить к работе с деревом, выбирается параметр [math]\alpha[/math] в диапазоне [math][0.5; 1)[/math]. Также нужно завести две переменные для хранения текущих значений [math]\mathtt {weight[T]}[/math] и [math]\mathtt{maxweight[T]}[/math] и обнулить их.

Структура вершины

struct Node:
 T key                    //значение в вершине 
 Node left                //левый ребенок вершины 
 Node right               //правый ребенок вершины 
 Node height              //высота поддерева данной вершины 
 Node depth               //глубина вершины 
 Node parent              //ссылка на родителя 
 Node sibling             //ссылки на "братьев" данной вершины 

Поиск элемента

Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет [math]O(\log_\frac{1}{\alpha} (N))[/math].

Таким образом, сложность получается логарифмическая, но! При [math]\alpha[/math] близком к [math]0.5[/math] мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При [math]\alpha[/math] близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к [math]O(N)[/math].

  • [math]root[/math] — корень дерева или поддерева, в котором происходит поиск.
  • [math]k[/math] — искомый ключ в дереве.
Search(root, k):
  if  root = [math]\varnothing[/math] or root.key = k:
     return  root
  else if  k [math]\leqslant[/math] root.left.key:
     return  Search(root.left, k)
  else:
     return  Search(root.right, k)

Вставка элемента

Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить [math]\alpha[/math]-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти Scapegoat-вершину — вершину, для которой потерян [math]\alpha[/math]-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос — нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева — есть стек, в котором находится весь путь от корня к новой вершине. Берутся родители из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий [math]\alpha[/math]-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить [math]\alpha[/math]-сбалансированность по весу. Сразу появляется вопрос — как делать перебалансировку найденной Scapegoat-вершины? Есть [math]2[/math] способа перебалансировки, — тривиальный и чуть более сложный.

Тривиальный способ перебалансировки

  1. совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
  2. Находится медиана на этом отрезке и подвешивается в качестве корня поддерева.
  3. Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.

Данный способ требует [math]O\mathtt{(weight(Scapegoat-root))}[/math] времени и столько же памяти.

Получение списка

  • [math]root[/math] — корень дерева, которое будет преобразовано в список.
FlattenTree(root, head):
  if root = [math]\varnothing[/math]:
     return head
  root.right = FlattenTree(root.right, head)
  return FlattenTree(root.left, root)

Построение дерева

  • [math]size[/math] — число вершин в списке.
  • [math]head[/math] — первая вершина в списке.
BuildHeightBalancedTree(size, head):
  if size = 1 then:
     return head
  else if size = 2 then:
     (head.right).left = head
     return head.right
  root = (BuildHeightBalancedTree(⌊(size − 1)/2⌋, head)).right
  last = BuildHeightBalancedTree(⌊(size − 1)/2⌋, root.right)
  root.left = head
  return last

Перестроение дерева

  • [math]size[/math] — число вершин в поддереве.
  • [math]scapegoat[/math] — вершина, которая испортила баланс.
RebuildTree(size, scapegoat):
  head = FlattenTree(scapegoat, [math]\varnothing[/math])
  BuildHeightBalancedTree(size, head)
  while head.parent [math]\ne \varnothing [/math]
     head = head.parent
  return head

Более сложный способ перебалансировки

Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на [math]1[/math] способ алгоритма внимательнее. Выбирается медиана, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. То есть для некоторого списка вершин, отсортированных в возрастающем порядке, будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не [math]O(weight(N))[/math], а всего лишь [math]O(\log N)[/math].

Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. То есть расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — [math]\log(3)[/math]. Таким образом, если нужно сэкономить память, то [math]2[/math] способ перебалансировки дерева — лучший вариант.

Вставка без нарушения баланса 1
Вставка без нарушения баланса 2
Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка

Псевдокод

  • [math]n[/math] — узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
FindScapegoat(n):
  size = 1
  height = 0
  while n.parent [math]\ne \varnothing[/math]:
     height = height + 1
     totalSize = 1 + size + n.sibling.size()
     if height [math] \gt  \lfloor \log_\frac{1}{\alpha} (totalSize) \rfloor[/math]:
        return n.parent
     n = n.parent
     size = totalSize

Сама вставка элемента:

  • [math]k[/math] — ключ, который будет добавлен в дерево.
Insert(k):
  height = InsertKey(k)
  if height = −1:
     return false;
  else if height > T.hα:
     scapegoat = FindScapegoat(Search(T.root, k))
     RebuildTree(n.size(), scapegoat)
  return true

Удаление элемента

Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). Далее следует проверка выполнения условия:

[math]\mathtt {weight[T]} \lt \alpha \cdot \mathtt {maxweight[T]}[/math];

Если оно выполняется — дерево могло потерять [math]\alpha[/math]-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:

[math]\mathtt {maxweight[T]} = \mathtt {weight[T]}[/math];

Псевдокод

Функция [math]Delete(k)[/math] удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.

  • [math]k[/math] — ключ, который будет удален.
Delete(k): 
  deleted = DeleteKey(k)
  if deleted:
     if T.size < (T.α · T.maxSize):
        RebuildTree(T.size, T.root)

Сравнение с другими деревьями

Достоинства Scapegoat дерева

  • По сравнению с такими структурами, как Красно-черное дерево, АВЛ-дерево и Декартово дерево, нет необходимости хранить какие-либо дополнительные данные в вершинах (а значит появляется выигрыш по памяти).
  • Отсутствие необходимости перебалансировать дерево при операции поиска (а значит гарантируется максимальное время поиска [math]O(\log N)[/math], в отличии от структуры данных Splay-дерево, где гарантируется только амортизированное [math]O(\log N)[/math])
  • При построении дерева выбирается некоторый коэффициент [math]\alpha[/math], который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.

Недостатки Scapegoat дерева

  • В худшем случае операции модификации дерева могут занять [math]O(N)[/math] времени (амортизированная сложность у них по-прежнему [math]O(\log N)[/math], но защиты от плохих случаев нет).
  • Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента [math]\alpha[/math] — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.

См. также

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