Редактирование: Взвешенное дерево

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 34: Строка 34:
 
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
 
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
  
<tex>\mathtt{T}</tex> — обозначение дерева,
+
<tex>T</tex> — обозначение дерева,
  
<tex>\mathtt{root[T]}</tex> — корень дерева <tex>T</tex>,  
+
<tex>root[T]</tex> — корень дерева <tex>T</tex>,  
  
<tex>\mathtt{left[x]}</tex> — левый сын вершины <tex>x</tex>,
+
<tex>left[x]</tex> — левый сын вершины <tex>x</tex>,
  
<tex>\mathtt{right[x]}</tex> — правый сын вершины <tex>x</tex>,
+
<tex>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{depth(x)}</tex> — глубина вершины <tex>x</tex>(количество рёбер от нее до корня),
  
<tex>\mathtt{height(T)}</tex> — глубина дерева <tex>T</tex> (глубина самой глубокой вершины дерева <tex>T</tex>),
+
<tex>\mathtt{height(T)}</tex> — глубина дерева <tex>T</tex>(глубина самой глубокой вершины дерева <tex>T</tex>),
  
<tex>\mathtt{weight(x)}</tex> — вес вершины <tex>x</tex> (количество всех её дочерних вершин плюс <tex>1</tex> {{---}} она сама),
+
<tex>\mathtt{weight(x)}</tex> — вес вершины <tex>x</tex>(количество всех её дочерних вершин плюс <tex>1</tex> {{---}} она сама),
  
<tex>\mathtt{weight[T]}</tex> — размер дерева <tex>T</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>
+
<tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева(максимальное значение, которое параметр <tex>weight[T]</tex> принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>
  
 
[[Файл:0ce162a62b624da8ba02233b4b254f23.png|380px|right]]
 
[[Файл:0ce162a62b624da8ba02233b4b254f23.png|380px|right]]
Строка 63: Строка 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 \mathtt{weight(x)}</tex> и <tex>\mathtt{weight(right[x])} \leqslant \alpha \cdot \mathtt{weight(x)}</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>.}}  
  
  
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>\mathtt {weight[T]}</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.
+
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>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>
 
  
 
=== Поиск элемента ===
 
=== Поиск элемента ===
 
Пусть требуется найти в данном 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>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
Строка 88: Строка 77:
  
 
  '''Search'''(root, k):
 
  '''Search'''(root, k):
   '''if ''' root = <tex>\varnothing</tex> or root.key = k:
+
   '''if ''' root = null or root.key = k:
 
       '''return ''' root
 
       '''return ''' root
 
   '''else if ''' k <tex>\leqslant</tex> root.left.key:
 
   '''else if ''' k <tex>\leqslant</tex> root.left.key:
Строка 96: Строка 85:
  
 
=== Вставка элемента ===
 
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <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-вершины?
 
Есть <tex>2</tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
 
Есть <tex>2</tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
Строка 110: Строка 99:
  
 
  '''FlattenTree'''(root, head):
 
  '''FlattenTree'''(root, head):
   '''if''' root = <tex>\varnothing</tex>:
+
   '''if''' root = null:
 
       '''return''' head
 
       '''return''' head
 
   root.right = FlattenTree(root.right, head)
 
   root.right = FlattenTree(root.right, head)
Строка 136: Строка 125:
 
*<tex>scapegoat</tex> {{---}} вершина, которая испортила баланс.
 
*<tex>scapegoat</tex> {{---}} вершина, которая испортила баланс.
 
  '''RebuildTree'''(size, scapegoat):
 
  '''RebuildTree'''(size, scapegoat):
   head = '''FlattenTree'''(scapegoat, <tex>\varnothing</tex>)
+
   head = '''FlattenTree'''(scapegoat, null)
 
   '''BuildHeightBalancedTree'''(size, head)
 
   '''BuildHeightBalancedTree'''(size, head)
   '''while''' head.parent <tex>\ne \varnothing </tex>
+
   '''while''' head.parent <tex>\ne null</tex> do
 
       head = head.parent
 
       head = head.parent
 
   '''return''' head
 
   '''return''' head
Строка 148: Строка 137:
 
Таким образом, если нужно сэкономить память, то <tex>2</tex> способ перебалансировки дерева {{---}} лучший вариант.
 
Таким образом, если нужно сэкономить память, то <tex>2</tex> способ перебалансировки дерева {{---}} лучший вариант.
  
<center>
+
<gallery align="center" heights="260px">
{| cellpadding="0"
+
Файл:Good_insert_1.png|Вставка без нарушения баланса 1
| [[Файл:Good_insert_1.png|400px|thumb|Вставка без нарушения баланса 1]] || [[Файл:Good_insert_2.png|400px|thumb|Вставка без нарушения баланса 2]]
+
Файл:Good_insert_2.png|Вставка без нарушения баланса 2
|}
+
Файл:Bad_insert.png|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка
{| cellpadding="0"
+
</gallery>
|align="center"|[[Файл:Bad_insert.png|595px|thumb|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка]]
 
|}
 
</center>
 
  
 
====Псевдокод====
 
====Псевдокод====
Строка 164: Строка 150:
 
   size = 1
 
   size = 1
 
   height = 0
 
   height = 0
   '''while''' n.parent <tex>\ne \varnothing</tex>:
+
   '''while''' (n.parent <tex>\ne</tex> null):
 
       height = height + 1
 
       height = height + 1
 
       totalSize = 1 + size + n.sibling.size()
 
       totalSize = 1 + size + n.sibling.size()
Строка 188: Строка 174:
 
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).  
 
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).  
 
Далее следует проверка выполнения условия:  
 
Далее следует проверка выполнения условия:  
:<tex>\mathtt {weight[T]} < \alpha \cdot \mathtt {maxweight[T]}</tex>;
+
:<tex>weight[T] < \alpha \cdot \mathtt {maxweight[T]}</tex>;
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
+
Если оно выполняется — дерево могло потерять <tex>\alpha</tex> - балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>\mathtt {maxweight[T]} = \mathtt {weight[T]}</tex>;
+
:<tex>\mathtt {maxweight[T]} = weight[T]</tex>;
  
 
====Псевдокод====
 
====Псевдокод====

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: