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

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

В информатике , бинарные деревья со сбалансированным весом ( 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 .

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

function joinRightWB(TL, k, TR)
    (l, k', c) = expose(TL)
    if balance(|TL|, |TR|) return Node(TL, k, TR)
    else 
        T' = joinRightWB(c, k, TR)
        (l', k', r') = expose(T')
        if (balance(|l|,|T'|)) return Node(l, k', T')
        else if (balance(|l|,|l'|) and balance(|l|+|l'|,|r'|))
             return rotateLeft(Node(l, k', T'))
        else return rotateLeft(Node(l, k', rotateRight(T'))
function joinLeftWB(TL, k, TR)
    /* symmetric to joinRightWB */
function join(TL, k, TR)
    if (heavy(TL, TR)) return joinRightWB(TL, k, TR)
    if (heavy(TR, TL)) return joinLeftWB(TL, k, TR)
    Node(TL, k, TR)

Здесь баланс $(x,y)$ значит два веса $x$ и $y$ сбалансированы. Exposure(v)=(l, k, r) означает извлечение узла дерева $v$левый ребенок $l$, ключ узла $k$ и правильный ребенок $r$. Node(l, k, r) означает создание узла левого дочернего элемента $l$, ключ $k$ и правильный ребенок $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(L, k)
       return (L', b, join(R', m, R))
    if (k > m) 
       (L', b, R') = split(R, k)
       return (join(L, m, L'), b, R))

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

function union(t1, t2):
    if t1 = nil:
        return t2
    if t2 = nil:
        return t1
    t<, t> ← split t2 on t1.root
    return join(union(left(t1), t<), t1.root, union(right(t1), 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), что и одноэлементная вставка и удаление, если корень большего дерева используется для разделения меньшего дерева.