Редактирование: Взвешенное дерево
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 34: | Строка 34: | ||
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление. | Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление. | ||
− | <tex> | + | <tex>T</tex> — обозначение дерева, |
− | <tex> | + | <tex>root[T]</tex> — корень дерева <tex>T</tex>, |
− | <tex> | + | <tex>left[x]</tex> — левый сын вершины <tex>x</tex>, |
− | <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> | + | <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 | + | |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> | + | Перед тем как приступить к работе с деревом, выбирается параметр <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>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск. | *<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск. | ||
Строка 88: | Строка 77: | ||
'''Search'''(root, k): | '''Search'''(root, k): | ||
− | '''if ''' root = | + | '''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>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти 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 = | + | '''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, | + | head = '''FlattenTree'''(scapegoat, null) |
'''BuildHeightBalancedTree'''(size, head) | '''BuildHeightBalancedTree'''(size, head) | ||
− | '''while''' head.parent <tex>\ne | + | '''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"> |
− | + | Файл:Good_insert_1.png|Вставка без нарушения баланса 1 | |
− | + | Файл:Good_insert_2.png|Вставка без нарушения баланса 2 | |
− | + | Файл:Bad_insert.png|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка | |
− | + | </gallery> | |
− | |||
− | |||
− | </ | ||
====Псевдокод==== | ====Псевдокод==== | ||
Строка 164: | Строка 150: | ||
size = 1 | size = 1 | ||
height = 0 | height = 0 | ||
− | '''while''' n.parent <tex>\ne | + | '''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> | + | :<tex>weight[T] < \alpha \cdot \mathtt {maxweight[T]}</tex>; |
− | Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить: | + | Если оно выполняется — дерево могло потерять <tex>\alpha</tex> - балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить: |
− | :<tex>\mathtt {maxweight[T]} = | + | :<tex>\mathtt {maxweight[T]} = weight[T]</tex>; |
====Псевдокод==== | ====Псевдокод==== |