Дерево с балансировкой по весу

редактировать

Тип самобалансирующихся двоичных деревьев поиска, которые можно использовать для реализации динамических наборов, словарей (карт) и последовательностей

В информатике, сбалансированные по весу двоичные деревья (WBT ) - это тип самобалансирующихся двоичных деревьев поиска, которые можно использовать для реализации динамических устанавливает, словари (карты) и последовательности. Эти деревья были введены Нивергельтом и Рейнгольдом в 1970-х годах как деревья ограниченного баланса или BB [α] деревья . Их более распространенное название связано с Knuth.

Как и другие самобалансирующиеся деревья, WBT хранят бухгалтерскую информацию, относящуюся к балансу, в своих узлах и выполняют вращения для восстановления баланса, когда он нарушается вставкой или операции удаления. В частности, каждый узел хранит размер поддерева с корнем в этом узле, а размеры левого и правого поддеревьев сохраняются в пределах некоторого коэффициента друг от друга. В отличие от информации о балансе в деревьях AVL (которые хранят высоту поддеревьев) и красно-черных деревьях (которые хранят вымышленный бит "цвета"), бухгалтерская информация в WBT является действительно полезное свойство для приложений: количество элементов в дереве равно размеру его корня, а информация о размере - это в точности информация, необходимая для реализации операций дерева статистики порядка, а именно., получение n-го по величине элемента в наборе или определение индекса элемента в отсортированном порядке.

Весовые деревья популярны в сообществе функционального программирования и используются для реализации наборов и карты в схеме MIT, SLIB и реализациях Haskell.

Содержание

1 Описание
2 Операции установки и массовые операции
3 Примечания
4 Ссылки

Описание

Дерево со сбалансированным весом - это двоичное дерево поиска, в котором хранятся размеры поддеревьев в узлах. То есть узел имеет поля

ключ любого упорядоченного типа
значение (необязательно, только для сопоставлений)
слева, справа, указатель на узел
размер, типа integer.

По определению размер листа (обычно представленного нулевым указателем) равен нулю. Размер внутреннего узла - это сумма размеров двух его дочерних узлов плюс один (size [n] = size [n.left] + size [n.right] + 1). В зависимости от размера, вес определяется как вес [n] = размер [n] + 1.

Вращение двоичного дерева.

Операции, которые изменяют дерево, должны гарантировать, что вес левого и правого поддеревья каждого узла остаются в пределах некоторого коэффициента α друг от друга, используя те же операции перебалансировки, которые используются в деревьях AVL: вращения и двойные вращения. Формально баланс узла определяется следующим образом:

Узел является α-сбалансированным по весу, если weight [n.left] ≥ α · weight [n] и weight [n.right] ≥ α · weight [n].

Здесь α - числовой параметр, который должен быть определен при реализации деревьев со сбалансированным весом. Большие значения α создают «более сбалансированные» деревья, но не все значения α подходят; Нивергельт и Рейнгольд доказали, что

α < 1 − 2 2 ≈ 0.29289 {\displaystyle \alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289}

{\ displaystyle \ alpha <1 - {\ frac {\ sqrt {2}} {2}} \ приблизительно 0,29289}

является необходимым условием для работы алгоритма балансировки. Более поздняя работа показала нижнюю границу ⁄ 11 для α, хотя ее можно сделать сколь угодно малой, если использовать собственный (и более сложный) алгоритм перебалансировки.

Правильное применение балансировки гарантирует дерево из n элементов будет иметь высоту

h ≤ log 1 1 - α ⁡ n = log 2 ⁡ n log 2 ⁡ (1 1 - α) = O (log ⁡ n) {\ displaystyle h \ leq \ log _ { \ frac {1} {1- \ alpha}} n = {\ frac {\ log _ {2} n} {\ log _ {2} \ left ({\ frac {1} {1- \ alpha}} \ right)}} = O (\ log n)}

h \ leq \ log _ {{{\ frac {1} {1- \ alpha}}}} n = {\ frac {\ log _ {2} n} {\ log _ {2} \ left ({\ frac {1} {1- \ alpha}} \ right)}} = O (\ log n)

Количество операций балансировки, необходимых в последовательности из n вставок и удалений, линейно по n, т. е. балансировка требует постоянного количества накладных расходов в амортизированной sense.

При поддержании дерева с минимальной стоимостью поиска требуется четыре вида двойных вращений (LL, LR, RL, RR, как в дереве AVL) в операциях вставки / удаления, если мы хотим только логарифмической производительности, LR и RL - единственные повороты, необходимые для одного прохода сверху вниз.

Операции набора и массовые операции

Определено несколько операций набора на деревьях со сбалансированным весом: union, пересечение и устанавливает разницу. Затем на основе этих установленных функций могут быть реализованы быстрые массовые операции по вставке или удалению. Эти операции с наборами основаны на двух вспомогательных операциях: Split и Join. Благодаря новым операциям реализация сбалансированных по весу деревьев может быть более эффективной и высокопараллелизируемой.

Join: функция Join находится на двух сбалансированных по весу деревьях t 1 и t 2 и ключ k и вернет дерево, содержащее все элементы в t 1, t 2, а также k. Это требует, чтобы k было больше, чем все ключи в t 1, и меньше, чем все ключи в t 2. Если два дерева имеют сбалансированный вес, Join просто создаст новый узел с левым поддеревом t 1, корнем k и правым поддеревом t 2. Предположим, что t 1 имеет больший вес, чем t 2 (другой случай симметричен). Соединение следует за правым стержнем t 1 до узла c, который сбалансирован с t 2. На этом этапе создается новый узел с левым дочерним элементом c, корнем k и правым дочерним элементом t 2 для замены c. Новый узел может сделать недействительным инвариант сбалансированного веса. Это можно исправить с помощью одинарного или двойного вращения при условии $α < 1 − 1 2 {\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}$ $\ alpha <1 - {\ frac {1} {{\ sqrt {2}}}}$
Split: чтобы разделить дерево со сбалансированным весом на два меньших дерева, меньших, чем ключ x, и тех, которые больше ключа x, сначала нарисуйте путь от корня с помощью вставка x в дерево. После этой вставки все значения меньше x будут найдены слева от пути, а все значения больше x будут найдены справа. Применяя Join, все поддеревья на левой стороне объединяются снизу вверх с использованием ключей на пути в качестве промежуточных узлов снизу вверх, чтобы сформировать левое дерево, а правая часть является симметричной. Для некоторых приложений Split также возвращает логическое значение, обозначающее, появляется ли x в дереве. Стоимость разделения составляет $O (log ⁡ n) {\ displaystyle O (\ log n)}$ $O (\ log n)$ , порядок высоты дерева. Этот алгоритм на самом деле не имеет ничего общего с какими-либо специальными свойствами сбалансированного по весу дерева и, следовательно, является общим для других схем балансировки, таких как деревья AVL.

. Алгоритм объединения выглядит следующим образом:

функция joinRightWB (T L, k, T R) (l, k ', c) = выставить (T L) ifбаланс (| T L |, | T L |) return Node (T L, k, T Relse T '= joinRightWB (c, k, T R) (l 1,k1, r 1) = выставить (T ') if (balance (l, T')) return Узел (l, k'T ') иначе, если (баланс (| l |, | l 1 |) и баланс (| l | + | l 1 |, | r 1 |)) return rotateLeft (Node (l, k ', T')) else return rotateLeft (Node (l, k ', rotateRight (T')) function joinLeftWB (T L, k, T R) / * симметрично joinRightWB * / function join (T L, k, T R) if(тяжелый (T L, T R)) return joinRightWB (T L, k, T R) if(тяжелый (T R, T L)) return joinLeftWB (T L, k, T R) Узел (T L, k, T R)

Здесь баланс $( x, y) {\ displaystyle (x, y)}$ $(x, y)$ означает два веса $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ сбалансированы. expose (v) = (l, k, r) означает извлечь левый дочерний элемент дерева $v {\ displaystyle v}$ $v$ $l {\ displaystyle l}$ $l$ , ключ узла $k {\ displaystyle k}$ $k$ и правого дочернего элемента $r {\ displaystyle r}$ $r$ . Узел (l, k, r) означает создание узла левого дочернего $l {\ displaystyle l}$ $l$ , ключа $k {\ displaystyle k}$ $k$ и правого child $r {\ displaystyle r}$ $r$ .

Алгоритм разделения выглядит следующим образом:

function split (T, k) if (T = nil) return (nil, false, nil) (L, (m, c), R) = expose (T) if (k = m) return (L, true, R) if (k m) (L ', b, R') = split (R, k) return (join (L, m, L '), b, R))

Объединение два сбалансированных по весу дерева t 1 и t 2, представляющие множества A и B, представляют собой сбалансированное по весу дерево t, которое представляет A ∪ B. Следующая рекурсивная функция вычисляет это объединение:

функция union (t 1, t 2): ift1= nil: return t2ift2= nil: return t1t<, t>← разделить t 2 на t 1.root return join (union (left (t 1), t <), t 1.root, union (right (t 1), t>))

Здесь предполагается разделение t o вернуть два дерева: одно содержит ключи минус его вводной ключ, а второе - большие ключи. (Алгоритм является неразрушающим, но также существует деструктивная версия на месте.)

Алгоритм для пересечения или различия аналогичен, но требует вспомогательной подпрограммы Join2, которая является То же, что и Join, но без среднего ключа. На основе новых функций для объединения, пересечения или разницы, один или несколько ключей могут быть вставлены или удалены из сбалансированного по весу дерева. Поскольку Split и Union вызывают Join, но не имеют непосредственного отношения к критериям балансировки деревьев с балансировкой по весу, такая реализация обычно называется алгоритмами на основе соединения.

Сложность каждого из объединения, пересечения и разности составляет $O (m log ⁡ (nm + 1)) {\ displaystyle O \ left (m \ log \ left ({n \ over m} +1 \ right) \ right)}$ ${\ displaystyle O \ left (m \ log \ left ({n \ over m} +1 \ right) \ right)}$ для двух весов -балансированные деревья размеров $m {\ displaystyle m}$ $m$ и $n (≥ m) {\ displaystyle n (\ geq m)}$ ${\ displaystyle n (\ geq m)}$ . Эта сложность оптимальна по количеству сравнений. Что еще более важно, поскольку рекурсивные вызовы объединения, пересечения или разницы не зависят друг от друга, они могут выполняться параллельно с глубиной параллельности $O (log ⁡ m log ⁡ N) {\ Displaystyle O (\ log m \ log n)}$ ${\ displaystyle O (\ log m \ log n)}$ . Когда $m = 1 {\ displaystyle m = 1}$ $m = 1$ , реализация на основе соединения имеет тот же вычислительный направленный ациклический граф (DAG), что и вставка и удаление одиночных элементов, если корень большего дерева используется для разделения меньшего дерева.

Примечания

Ссылки