Введение
Приоритетная очередь, реализованная с использованием варианта двоичной кучи.
В информатике левостороннее дерево (или левосторонняя куча) — это приоритетная очередь, реализованная с использованием варианта двоичной кучи. Каждый узел x имеет значение s, которое представляет собой расстояние до ближайшего листа в поддереве с корнем в x. В отличие от двоичной кучи, левостороннее дерево стремится быть сильно несбалансированным. Помимо свойства кучи, левосторонние деревья поддерживаются таким образом, чтобы правый потомок каждого узла имел меньшее значение s. Левостороннее дерево со смещением (height-biased leftist tree) было изобретено Кларком Алланом Крейном. Название происходит от того факта, что левое поддерево обычно выше правого. Левостороннее дерево является объединяемой кучей. При вставке нового узла в дерево создается новое одноузловое дерево и объединяется с существующим деревом. Для удаления элемента он заменяется объединением его левого и правого поддеревьев. Обе эти операции занимают O(log n) времени. Для вставки это медленнее, чем кучи Фибоначчи, которые поддерживают вставку за амортизированное время O(1) (постоянное) и в худшем случае O(log n). Левосторонние деревья полезны благодаря своей способности быстро объединяться, в отличие от двоичных куч, для которых требуется Θ(n). В большинстве случаев объединение скошенных куч (skew heaps) показывает лучшую производительность. Однако объединение левосторонних куч имеет сложность O(log n) в худшем случае, в то время как объединение скошенных куч имеет только амортизированную сложность O(log n).
In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s value which is the distance to the nearest leaf in subtree rooted at x. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s value. The height biased leftist tree was invented by Clark Allan Crane. The name comes from the fact that the left subtree is usually taller than the right subtree. A leftist tree is a mergeable heap. When inserting a new node into a tree, a new one node tree is created and merged into the existing tree. To delete an item, it is replaced by the merge of its left and right sub trees. Both these operations take O(log n) time. For insertions, this is slower than Fibonacci heaps, which support insertion in O(1) (constant) amortized time, and O(log n) worst case. Leftist trees are advantageous because of their ability to merge quickly, compared to binary heaps which take Θ(n). In almost all cases, the merging of skew heaps has better performance. However merging leftist heaps has worst case O(log n) complexity while merging skew heaps has only amortized O(log n) complexity.
Предвзятость
Обычное левостороннее дерево — это левостороннее дерево, ориентированное на высоту.
Значение S
Значение s (или ранг) узла — это расстояние от этого узла до ближайшей пустой позиции в поддереве, укорененном в этом узле. Другими словами, значение s нулевого потомка неявно равно нулю. Другие узлы имеют значение s, равное единице плюс минимум значений s их потомков. Таким образом, в примере справа все узлы с по крайней мере одним отсутствующим потомком имеют значение s, равное 1, в то время как узел 4 имеет значение s, равное 2, поскольку его правый потомок (8) имеет значение s, равное 1. (В некоторых описаниях значение s нулевых потомков принимается за −1.) Зная, что кратчайший путь к ближайшему отсутствующему листу в поддереве, укорененном в x, равен s(x), каждый узел на глубине s(x) − 1 или меньше имеет ровно 2 потомка, поскольку s(x) было бы меньше, если бы это не было так. Следовательно, размер дерева, укорененного в x, составляет не менее . Таким образом, s(x) не превышает , где m — количество узлов поддерева, укорененного в x.== Левосторонние деревья также могут быть взвешенными. В этом случае вместо хранения значений s в узле x мы храним атрибут w(x), обозначающий количество узлов в поддереве, укорененном в x:
Leftist trees can also be weight biased. In this case, instead of storing s values in node x, we store an attribute w(x) denoting the number of nodes in the subtree rooted at :
w(x) = w(x.right) + w(x.left) + 1
WBLT обеспечивают w(x.left) ≥ w(x.right) для всех внутренних узлов x. Операции WBLT поддерживают этот инвариант, меняя местами потомков узла, когда правое поддерево становится больше левого, как и в операциях HBLT.
Слияние двух Min WBLT
Операция слияния в WBLT может быть выполнена за один проход сверху вниз, поскольку количество узлов в поддеревьях известно до рекурсивного вызова функции слияния. Таким образом, мы можем поменять местами левое и правое поддеревья, если общее количество узлов в правом поддереве и объединяемом дереве больше, чем количество узлов в левом поддереве. Это позволяет выполнять операции по одному пути, что улучшает временную сложность операций на постоянный множитель. Операция слияния изображена на графике ниже.
Другие операции на WBLT
Вставка и удаление минимального элемента может быть выполнено аналогично HBLT с использованием операции слияния. Хотя WBLT превосходят HBLT в операциях слияния, вставки и удаления ключа Min по постоянному множителю, гарантированная сложность O(log n) не обеспечивается при удалении произвольного элемента из WBLT, поскольку необходимо просмотреть θ(n) узлов. Если бы это был HBLT, удаление листового узла с ключом 60 заняло бы время O(1), и обновление значений s не потребовалось бы, так как длина самой правой ветви для всех узлов не изменилась бы. Однако в дереве WBLT необходимо обновить вес каждого узла до корня, что в худшем случае занимает O(n).