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

Самобалансирующееся двоичное дерево поиска

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

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

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

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

Описание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

функция joinRightWB(TL , k, T R ) (l, k', c) = Exposure(T L ) , если баланс(|T L |, |T R |) return Node(T L , k, T R ) else T' = joinRightWB(c, k, T R) ) (l', k', r') = выставлять(T') if (balance(|l|,|T'|)) return Node(l, k', T') else if (balance(|l|,|l'|) и Balance(|l|+|l'| ,|r'|)) return RotateLeft(Node(l, k', T')) else return RotateLeft(Node(l, k', RotateRight(T')) function joinLeftWB(T L , 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 , к, Т Р ) Узел(TL , k, TR )

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

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

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

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

function Union(t 1 , t 2 ): если t 1 = nil: вернуть t 2  если t 2 = nil: вернуть t 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 , но не имеют дело непосредственно с критериями балансировки деревьев со сбалансированным весом, такую ​​реализацию обычно называют алгоритмами на основе соединения .

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

Примечания

1. Это определение использовали Нивергельт и Рейнгольд. Адамс напрямую использует размер как вес, ^[6] что усложняет анализ его варианта и приводит к ошибкам в основных реализациях. ^[4]

Рекомендации

1. Цакалидис, АК (1984). «Поддержание порядка в обобщенном связанном списке». Акта Информатика . 21 : 101–112. дои : 10.1007/BF00289142. S2CID  26127563.
2. Нивергельт, Дж.; Рейнгольд, Э.М. (1973). «Двоичные деревья поиска ограниченного баланса». SIAM Journal по вычислительной технике . 2 : 33–43. дои : 10.1137/0202005.
3.  Эта статья включает общедоступные материалы Пола Э. Блэка. «Дерево BB(α)». Словарь алгоритмов и структур данных . НИСТ .
4. Хираи, Ю.; Ямамото, К. (2011). «Балансировка деревьев со сбалансированным весом» (PDF) . Журнал функционального программирования . 21 (3): 287. doi :10.1017/S0956796811000104.
5. Роура, Сальвадор (2001). Новый метод балансировки бинарных деревьев поиска . ИКАЛП . Конспекты лекций по информатике. Том. 2076. стр. 469–480. дои : 10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.
6. Адамс, Стивен (1993). «Функциональные жемчужины: эффективные наборы — баланс». Журнал функционального программирования . 3 (4): 553–561. дои : 10.1017/S0956796800000885 .
7. Брасс, Питер (2008). Расширенные структуры данных . Издательство Кембриджского университета. стр. 61–71.
8. Блюм, Норберт; Мельхорн, Курт (1980). «О среднем количестве операций ребалансировки в деревьях со сбалансированным весом» (PDF) . Теоретическая информатика . 11 (3): 303–320. дои : 10.1016/0304-3975(80)90018-3.
9. Чо, Сонхун; Сахни, Сартадж (2000). «Новое двоичное дерево поиска со сбалансированным весом». Международный журнал основ компьютерных наук . 11 (3): 485–513. CiteSeerX 10.1.1.36.3888 . дои : 10.1142/S0129054100000296. 
10. Блеллох, Гай Э.; Феризович, Дэниел; Сунь, Ихан (2016), «Просто присоединяйтесь к параллельным упорядоченным наборам», Симпозиум по параллельным алгоритмам и архитектурам, Proc. 28-го симпозиума ACM. Параллельные алгоритмы и архитектуры (SPAA 2016) , ACM, стр. 253–264, arXiv : 1602.02120 , doi : 10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID  2897793.
11. Адамс, Стивен (1992), Эффективная реализация наборов на функциональном языке, CiteSeerX 10.1.1.501.8427 .