Левое дерево
-
Определение и свойства левого дерева
- Левое дерево (левая куча) — приоритетная очередь, реализованная с использованием двоичной кучи.
- Каждый узел имеет значение s, представляющее расстояние до ближайшего листа.
- Левое дерево стремится быть очень несбалансированным.
- Правый потомок каждого узла имеет меньшее значение s.
-
История и преимущества
- Левое дерево, зависящее от высоты, изобретено Кларком Алланом Крейном.
- Левые деревья выгодны из-за быстрой объединяемости по сравнению с бинарными кучами.
- Объединение левых куч имеет наихудшую сложность O(log n).
-
Операции с левым деревом
- Большинство операций выполняются с помощью операции слияния.
- Слияние двух минимальных HBLT возвращает Min HBLT с объединенными узлами.
- Вставка выполняется с помощью слияния, удаление — слиянием поддеревьев.
-
Инициализация левого дерева
- Инициализация выполняется с помощью очереди или объединения узлов по одному.
- Очередь позволяет инициализировать HBLT за O(n) времени.
-
Удаление элемента из минимального HBLT
- Удаление элемента выполняется слиянием поддеревьев и обновлением s-значений.
- Операция требует O(lgm) времени.
-
Смещенное по весу левое дерево
- Левые деревья могут быть смещены по весу, сохраняя атрибут w(x), обозначающий количество узлов.
- Операции WBLT обеспечивают w(x.слева) ≥ w(x.справа) для всех внутренних узлов.
- Слияние WBLT выполняется с использованием единственного обхода сверху вниз.
-
Варианты и рекомендации
- Существуют варианты базового левого дерева с незначительными изменениями.
- Рекомендуется дальнейшее чтение и внешние ссылки для более глубокого изучения.