В информатике , левак дерево или левак куча является приоритетной очередь осуществляется с вариантом бинарной кучи . Каждый узел x имеет s-значение, которое представляет собой расстояние до ближайшего листа в поддереве с корнем x. [1] В отличие от двоичной кучи , левое дерево пытается быть очень несбалансированным. В дополнение к свойству кучи поддерживаются левые деревья, поэтому правый потомок каждого узла имеет более низкое s-значение.
Левое дерево со смещенной высотой было изобретено Кларком Алланом Крейном . [2] Название происходит от того факта, что левое поддерево обычно выше, чем правое поддерево.
Левое дерево - это объединяемая куча . При вставке нового узла в дерево создается новое одноузловое дерево, которое объединяется с существующим деревом. Чтобы удалить элемент, он заменяется объединением его левого и правого поддеревьев. Обе эти операции занимают время O (log n ). Для вставок это медленнее, чем кучи Фибоначчи , которые поддерживают вставку за O (1) (постоянное) амортизированное время и O (log n ) в худшем случае.
Левые деревья выгодны из-за их способности быстро сливаться по сравнению с двоичными кучами, которые принимают Θ ( n ). Практически во всех случаях слияние перекосов дает лучшую производительность. Однако слияние левых куч имеет наихудшую сложность O (log n ), в то время как слияние косых куч амортизирует сложность O (log n ).
Предвзятость [ править ]
Обычное левое дерево - это левое дерево со смещением по высоте . [2] Однако могут существовать и другие предубеждения, например, в левом дереве с учетом веса . [3]
S-значение [ править ]
S-значение (или ранг ) узла является расстоянием от этого узла до ближайшего листа в поддереве с корнем в этом узле. Другими словами, s-значение nullдочернего элемента неявно равно нулю. Другие узлы имеют s-значение, равное еще одному минимуму s-значений их дочерних узлов. Таким образом, в примере справа все узлы с хотя бы одним отсутствующим дочерним элементом имеют s-значение 1, тогда как узел 4 имеет s-значение 2, поскольку его правый дочерний элемент (8) имеет s-значение 1. (В некоторых описаниях предполагается, что s-значение нулевых потомков равно -1. [4] )
Зная, что кратчайший путь к ближайшему отсутствующему листу в поддереве с корнем x точно равен s ( x ), каждый узел на глубине s ( x ) -1 или меньше имеет ровно 2 дочерних элемента, поскольку s ( x ) было бы меньше, если бы не . Это означает, что размер дерева с корнем в x не меньше . Таким образом, s ( x ) не больше , m - количество узлов поддерева с корнем x . [1]
Операции над левым деревом со смещением высоты [1] [ править ]
Большинство операций с левым деревом со смещением по высоте выполняется с помощью операции слияния.
Объединение двух Min HBLT [ править ]
Операция слияния принимает два Min HBLT в качестве входных данных и возвращает Min HBLT, содержащий все узлы в исходных Min HBLT, вместе взятых.
Если один из A или B пуст, слияние возвращает другое.
В случае Min HBLT, предположим, что у нас есть два дерева с корнями в A и B, где A.key B.key. В противном случае мы можем поменять местами A и B, чтобы выполнялось указанное выше условие.
Слияние выполняется рекурсивно путем слияния B с правым поддеревом A. Это может изменить S-значение правого поддерева A. Чтобы сохранить свойство левого дерева, после каждого слияния мы проверяем, стало ли S-значение правого поддерева больше, чем S-значение левого поддерева во время рекурсивных вызовов слияния. Если это так, мы меняем местами правое и левое поддеревья (если один дочерний элемент отсутствует, он должен быть правым).
Поскольку мы предполагали, что корень A больше, чем корень B, свойство кучи также сохраняется.
Псевдокод для объединения двух левых деревьев с минимальной высотой [ править ]
MERGE (A, B), если A = null, вернуть B, если B = null, вернуть A, если A.key> B.key, тогда СВОП (A, B) A.right: = MERGE (A.right, B) // результат не может быть нулевым, так как B не равно нулю, если A.left = null, тогда SWAP (А. слева, А. справа) A.s_value: = 1 // поскольку правое поддерево имеет значение NULL, кратчайший путь к листу-потомку от узла A равен 1, возвращает A, если A.right.s_value> A.left.s_value, тогда SWAP (A. right, A. слева) A.s_value: = A.right.s_value + 1 вернуть A
Код Java для объединения двух левых деревьев с минимальной высотой [ править ]
слияние общедоступных узлов ( узел x , узел y ) { if ( x == null ) return y ; если ( y == null ) вернуть x ; // если бы это была максимальная куча, // следующая строка была бы такой: if (x.element <y.element) if ( x . element . compareTo ( y . element ) > 0 ) { // x.element > y.element Node temp = x ; х = у ; y = темп ; } х . rightChild = слияние ( x . rightChild , y ); if ( x . leftChild == null ) { // левый дочерний элемент не существует, поэтому переместите правого дочернего элемента в левую часть x . leftChild = х . rightChild ; х . RightChild = NULL ; // xs был и остается 1 } else { // левый дочерний элемент существует, поэтому сравните s-значения if ( x . leftChild . s < x . rightChild . s ) { Node temp = х . leftChild ; х . leftChild = х . rightChild ; х . rightChild = темп ; } // поскольку мы знаем, что правый дочерний элемент имеет меньшее s-значение, мы можем просто // добавить единицу к его s-значению x . s = х . rightChild . s + 1 ; } return x ; }Пример [ править ]
Изображен пример того, как работает операция слияния в левом дереве. Поля представляют каждый вызов слияния.
Когда рекурсия разворачивается, мы меняем местами левого и правого потомков, если x.right.s_value> x.left.s_value для каждого узла x. В этом случае мы поменяли местами поддеревья, основанные на узлах с ключами 7 и 10.
Вставка в Min HBLT [ править ]
Вставка выполняется с помощью операции слияния. Вставка узла в уже существующий
Min HBLT, создает дерево HBLT размера один с этим узлом и объединяет его с существующим деревом.
INSERT ( A , x ) B : = CREATE_TREE ( x ) return MERGE ( A , B )
Удаление элемента Min из Min HBLT [ править ]
Элемент Min в Min HBLT является корнем. Таким образом, чтобы удалить Min, удаляется корень и его поддеревья объединяются, чтобы сформировать новый Min HBLT.
DELETE_MIN ( A ) x : = A .key A : = MERGE ( A. Right, A .left) return x
Инициализация левого дерева со смещением по высоте [ править ]
Инициализация левого дерева со смещением высоты в основном выполняется одним из двух способов. Первый - объединить каждый узел по одному в один HBLT. Этот процесс неэффективен и занимает O ( nlogn ) времени. Другой подход - использовать очередь для хранения каждого узла и результирующего дерева. Первые два элемента в очереди удаляются, объединяются и снова помещаются в очередь. Это может инициализировать HBLT за время O ( n ). Этот подход подробно описан на трех прилагаемых диаграммах. Показано дерево со смещением влево по минимальной высоте.
Чтобы инициализировать минимальный HBLT, поместите каждый элемент, который нужно добавить в дерево, в очередь. В примере (см. Часть 1 слева) набор чисел [4, 8, 10, 9, 1, 3, 5, 6, 11] инициализирован. Каждая строка диаграммы представляет другой цикл алгоритма, отображающий содержимое очереди. Первые пять шагов легко выполнить. Обратите внимание, что только что созданный HBLT добавляется в конец очереди. На пятом шаге происходит первое появление значения s больше 1. Шестой шаг показывает два дерева, слитых друг с другом, с предсказуемыми результатами.
В части 2 происходит немного более сложное слияние. У дерева с меньшим значением (дерево x) есть правый дочерний элемент, поэтому слияние должно быть вызвано снова для поддерева, корнем которого является правый дочерний элемент дерева x и другое дерево. После слияния с поддеревом получившееся дерево снова помещается в дерево x. Значение s правого дочернего элемента (s = 2) теперь больше, чем значение s левого дочернего элемента (s = 1), поэтому их необходимо поменять местами. Значение s корневого узла 4 теперь также равно 2.
Часть 3 самая сложная. Здесь мы рекурсивно вызываем слияние дважды (каждый раз с правильным дочерним поддеревом, которое не отображается серым цветом). При этом используется тот же процесс, который описан в части 2.
Удаление произвольного элемента из Min HBLT [ править ]
Если у нас есть указатель на узел x в Min HBLT, мы можем удалить его следующим образом: Заменить узел x результатом слияния его двух поддеревьев и обновить s-значения узлов на пути от x до корня. , меняя местами правое и левое поддеревья, если необходимо, чтобы сохранить свойство левого дерева.
Переход вверх продолжается до тех пор, пока мы не достигнем корня или пока значения s не изменятся. Поскольку мы удаляем элемент, S-значения на пройденном пути не могут быть увеличены. Каждый узел, который уже является правым дочерним элементом своего родителя и приводит к уменьшению s-значения своего родителя, останется справа. Каждый узел, который является левым потомком своего родителя и вызывает уменьшение s-значения родителя, должен быть заменен его правым братом, если s-значение становится ниже текущего s-значения правого дочернего элемента.
У каждого узла должен быть указатель на своего родителя, чтобы мы могли пройти путь к корню, обновляя s-значения.
Когда обход заканчивается в некотором узле y, все пройденные узлы лежат на крайнем правом пути с корнем в узле y. Пример показан ниже. Отсюда следует, что количество пройденных узлов не превышает log (m), где m - это размер поддерева с корнем в y. Таким образом, для выполнения этой операции также требуется O (lg m).
Левое дерево со смещением веса [5] [ править ]
Левые деревья также могут быть смещены по весу. В этом случае вместо хранения s-значений в узле x мы сохраняем атрибут w ( x ), обозначающий количество узлов в поддереве с корнем x :
w ( x ) = w ( x. вправо) + w ( x. влево) + 1
WBLT гарантируют, что w (x.left) ≥ w (x.right) для всех внутренних узлов x. Операции WBLT обеспечивают этот инвариант, меняя местами дочерние элементы узла, когда правое поддерево превышает левое, как в операциях HBLT.
Объединение двух минимальных WBLT [ править ]
Операция слияния в WBLT может быть выполнена с использованием одного обхода сверху вниз, поскольку количество узлов в поддеревьях известно до рекурсивного вызова слияния. Таким образом, мы можем поменять местами левое и правое поддеревья, если общее количество узлов в правом поддереве и объединяемом дереве больше, чем количество узлов в левом поддереве. Это позволяет выполнять операции по единому пути и, таким образом, увеличивает временную сложность операций на постоянный коэффициент.
Операция слияния изображена на графике ниже.
Другие операции на WBLT [ править ]
Вставка и удаление элемента min могут выполняться так же, как для HBLT, с использованием операции слияния.
Хотя WBLT превосходит HBLT в слиянии, вставке и удалении ключа Min на постоянный коэффициент, граница O (log n ) не гарантируется при удалении произвольного элемента из WBLT, поскольку необходимо пройти по узлам θ ( n ).
Если бы это был HBLT, то удаление листового узла с ключом 60 заняло бы время O (1), и обновление s-значений не требуется, поскольку длина крайнего правого пути для всех узлов не изменяется.
Но в дереве WBLT мы должны обновить вес каждого узла до корня, что занимает O ( n ) в худшем случае.
Варианты [ править ]
Существует несколько вариантов основного левого дерева, которые вносят лишь незначительные изменения в основной алгоритм:
- Выбор левого ребенка как более высокого произвольный; "правое дерево" тоже подойдет.
- Можно избежать обмена дочерними элементами , но вместо этого запишите, какой дочерний элемент является самым высоким (например, в младшем разряде s-значения), и используйте его в операции слияния.
- Значение s, используемое для решения, с какой стороны объединяться, может использовать метрику, отличную от высоты. Например, можно использовать вес (количество узлов).
Ссылки [ править ]
- ^ a b c "Левые деревья" (PDF) . www.google.com . Проверено 31 мая 2019 .
- ^ a b Крейн, Кларк А. (1972), Линейные списки и приоритетные очереди как сбалансированные двоичные деревья (докторская диссертация), Департамент компьютерных наук Стэнфордского университета, ISBN 0-8240-4407-X, STAN-CS-72-259
- ^ Seonghun Cho; Сартадж Сахни (1996), «Левые деревья со смещением веса и модифицированные списки пропусков» (PDF) , Журнал экспериментальной алгоритмики , 3 , CiteSeerX 10.1.1.13.2962 , DOI : 10.1145 / 297096.297111
- ↑ Стюарт, Джеймс (25 сентября 1988 г.). «ЛЕВЫЕ ДЕРЕВЬЯ» . Проект динамической графики Университета Торонто . Проверено 31 мая 2019 .
- ^ Чо, Сонхун; Сахни, Сартадж (сентябрь 1998 г.). «Левые деревья с упором на вес и модифицированные списки пропусков» . J. Exp. Алгоритмика . 3 . DOI : 10.1145 / 297096.297111 . ISSN 1084-6654 .
Дальнейшее чтение [ править ]
- Роберт Э. Тарджан (1983). Структуры данных и сетевые алгоритмы . СИАМ. С. 38–42. ISBN 978-0-89871-187-5.
- Динеш П. Мехта; Сартадж Сахни (28 октября 2004 г.). «Глава 5: Левые деревья» . Справочник по структурам данных и приложениям . CRC Press. ISBN 978-1-4200-3517-9.
Внешние ссылки [ править ]
- Leftist Trees , Сартадж Сахни
