Дерево со сбалансированным весом

Чтобы узнать о других целях, см. Оптимальное бинарное дерево поиска .

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

Хорошо известным примером является Хаффману кодирование корпуса по .

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

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

Описание

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

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

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

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

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

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

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

$\alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289$

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

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

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

Если α задано максимально допустимое значение, наихудшая высота дерева со сбалансированным весом такая же, как у красно-черного дерева в точке $2\log _{2}n$.

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

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

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

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

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

Алгоритм соединения следующий:

функция  joinRightWB(TL  ,  k, T  R  )    (l, k', c) = выставить(  TL  )     if  Balance(|T  L  |, |T  R  |)  return  Node(T  L  , k, T  R  )     еще          Т' = joinRightWB(c, k, T  R  )        (l', k', r') = выставлять(T')         if  (balance(|l|,|T'|))  return  Node(l, k', T')         иначе if  (баланс(|l|,|l'|) и баланс(|l|+|l'|,|r'|))              return  RotateLeft(Node(l, k', T'))         иначе  верните RotateLeft(Node(l, k', RotateRight(T')) функция  joinLeftWB(TL  ,  k, T  R  )    /* симметрично joinRightWB */ функция  join(  TL  , k, T  R  )     if  (heavy(TL  ,  TR  )  ) return joinRightWB(TL  ,  k,  TR  )     if  (heavy(TR  ,  T  L  )) return joinLeftWB(TL  ,  k,  TR  )    Узел(  TL  , k,  TR  ) 

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

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

функция  разделения (Т, к)     если  (T = ноль) вернуть (ноль, ложь, ноль)    (L, (m, c), R) = выставлять (T)     если  (k = m) вернуть (L, true, R)     если  (к < м)        (L', b, R') = расщепление(L, k)        return  (L', b, join(R', m, R))     если  (к > м)        (L', b, R') = расщепление(R, k)        return  (join(L, m, L'), b, R)) 

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

функция  объединение(т  1  , т  2  ):     если  t  1  = ноль:         вернуть  t  2,      если  t  2  = ноль:         вернуть  т  1     t  <  , t  >  ← разделить t  2  на t  1  .root     return  join(union(left(t  1  ), t  <  ), t  1  .root, Union(right(t  1  ), t  >  )) 

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

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

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