Сбалансированное по весу дерево
-
Описание деревьев с балансировкой по весу
- Бинарные деревья с балансировкой по весу (WBT) хранят размеры поддеревьев в узлах.
- Каждый узел хранит размер поддерева, коренящегося в этом узле.
- Размеры левого и правого поддеревьев находятся в пределах некоторого коэффициента друг от друга.
-
Операции и балансировка
- Операции вставки и удаления должны поддерживать баланс узлов.
- Балансировка выполняется с помощью поворотов и двойных поворотов.
- Значение α определяет степень балансировки дерева.
-
Операции с множествами
- Определены операции объединения, пересечения и разности множеств.
- Эти операции зависят от вспомогательных операций разделения и объединения.
- Реализация на основе объединения позволяет вставлять и удалять несколько ключей одновременно.
-
Сложность и параллелизм
- Сложность операций объединения, пересечения и разности составляет O(m log(n/m + 1)).
- Параллельная глубина выполнения составляет O(log m log n).
- Реализация на основе объединения имеет тот же вычислительный граф, что и вставка и удаление отдельных элементов.