WikiDer > Левое дерево
В Информатика, а левое дерево или левая куча это приоритетная очередь реализован с вариантом двоичная куча. Каждый узел x имеет s-значение это расстояние до ближайшего лист в поддереве с корнем x.[1] В отличие от двоичная кучаЛевое дерево пытается быть очень неуравновешенным. В добавок к куча свойство, левые деревья поддерживаются, поэтому правый потомок каждого узла имеет более низкое s-значение.
Левое дерево со смещенной высотой было изобретено Кларк Аллан Крейн.[2] Название происходит от того факта, что левое поддерево обычно выше, чем правое поддерево.
Левое дерево - это объединяемая куча. При вставке нового узла в дерево создается новое одноузловое дерево, которое объединяется с существующим деревом. Чтобы удалить элемент, он заменяется объединением его левого и правого поддеревьев. Обе эти операции занимают O (log п) время. Для прошивок это медленнее, чем Куча Фибоначчи, поддерживающие вставку в O (1) (константа) амортизированный время и O (журнал п) худший случай.
Левые деревья выгодны из-за их способности быстро сливаться по сравнению с двоичными кучами, которые принимают Θ (п). Практически во всех случаях слияние косые кучи имеет лучшую производительность. Однако слияние левых куч в худшем случае имеет O (журнал п) сложность при объединении перекосов амортизировала только O (log п) сложность.
Смещение
Обычное левое дерево - это смещенный по высоте левое дерево.[2] Однако могут существовать и другие предубеждения, например, в склонный к весу левое дерево.[3]
S-значение
В s-значение (или ранг) узла - это расстояние от этого узла до ближайшего листа в поддереве с корнем в этом узле. Другими словами, s-значение значение NULL child неявно равен нулю. Другие узлы имеют s-значение, равное еще одному минимуму s-значений их дочерних узлов. Таким образом, в примере справа все узлы с хотя бы одним отсутствующим дочерним элементом имеют s-значение 1, тогда как узел 4 имеет s-значение 2, поскольку его правый дочерний элемент (8) имеет s-значение 1. (В некоторых описаниях предполагается, что s-значение нулевых потомков равно -1.[4])
Зная кратчайший путь к ближайшему отсутствующему листу в поддереве с корнем Икс точно из s(Икс), каждый узел на глубине s(Икс) −1 или меньше имеет ровно 2 детей, так как s(Икс) было бы меньше, если бы не было. Это означает, что размер дерева с корнями Икс по крайней мере . Таким образом, s(Икс) не более , м количество узлов поддерева с корнем Икс.[1]
Операции на левом дереве со смещением высоты[1]
Большинство операций с левым деревом со смещением по высоте выполняется с помощью операции слияния.
Объединение двух минимальных 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, свойство кучи также сохраняется.
Псевдокод для объединения двух левых деревьев с минимальной высотой
ОБЪЕДИНЕНИЕ (A, B) если A = ноль вернуть B если B = ноль вернуть А если A.key> B.key тогда SWAP (A, B) A.right: = MERGE (A.right, B) // результат не может быть нулевым, поскольку B не равно нулю если A.left = null тогда SWAP (A. слева, A. справа) A.s_value: = 1 // поскольку правое поддерево имеет значение NULL, кратчайший путь к листу-потомку от узла A равен 1 вернуть А если A.right.s_value> A.left.s_value тогда SWAP (A.right, A.left) A.s_value: = A.right.s_value + 1 вернуть А
Код Java для объединения двух левых деревьев с минимальной высотой
общественный Узел слияние(Узел Икс, Узел у) { если (Икс == значение NULL) вернуть у; если (у == значение NULL) вернуть Икс; // если бы это была максимальная куча, то // следующая строка будет: if (x.element если (Икс.элемент.по сравнению с(у.элемент) > 0) { // x.element> y.element Узел темп = Икс; Икс = у; у = темп; } Икс.rightChild = слияние(Икс.rightChild, у); если (Икс.leftChild == значение NULL) { // левый дочерний элемент не существует, поэтому переместите правого дочернего элемента в левую сторону Икс.leftChild = Икс.rightChild; Икс.rightChild = значение NULL; // x.s был и остается 1 } еще { // левый дочерний элемент существует, поэтому сравните s-значения если (Икс.leftChild.s < Икс.rightChild.s) { Узел темп = Икс.leftChild; Икс.leftChild = Икс.rightChild; Икс.rightChild = темп; } // поскольку мы знаем, что у правого потомка меньшее s-значение, мы можем просто // добавляем единицу к его s-значению Икс.s = Икс.rightChild.s + 1; } вернуть Икс;} пример
Изображен пример того, как работает операция слияния в левом дереве. Поля представляют каждый вызов слияния.
Когда рекурсия разворачивается, мы меняем местами левого и правого потомков, если x.right.s_value> x.left.s_value для каждого узла x. В этом случае мы поменяли местами поддеревья, основанные на узлах с ключами 7 и 10.
Вставка в Min HBLT
Вставка выполняется с помощью операции слияния. Вставка узла в уже существующий
Min HBLT, создает дерево HBLT размера один с этим узлом и объединяет его с существующим деревом.
ВСТАВИТЬ (А, Икс) B : = CREATE_TREE (Икс) вернуть ОБЪЕДИНЕНИЕ (А, B)
Удаление элемента Min из Min HBLT
Элемент Min в Min HBLT является корнем. Таким образом, чтобы удалить Min, корень удаляется, а его поддеревья объединяются, чтобы сформировать новый Min HBLT.
DELETE_MIN (А) Икс := А.key А : = ОБЪЕДИНЕНИЕ (А.правильно, А.осталось) вернуть Икс
Инициализация левого дерева со смещением высоты
Инициализация левого дерева со смещением по высоте в основном выполняется одним из двух способов. Первый - объединить каждый узел по одному в один HBLT. Этот процесс неэффективен и занимает O (nlogn) время. Другой подход - использовать очередь для хранения каждого узла и результирующего дерева. Первые два элемента в очереди удаляются, объединяются и снова помещаются в очередь. Это может инициализировать HBLT за O (п) время. Этот подход подробно описан на трех прилагаемых диаграммах. Показано дерево со смещением влево минимальной высоты.
Чтобы инициализировать минимальный 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 (Икс), обозначающее количество узлов в поддереве с корнем Икс:
w (Икс) = w (Икс.право) + w (Иксслева) + 1
WBLT гарантируют, что w (x.left) ≥ w (x.right) для всех внутренних узлов x. Операции WBLT обеспечивают этот инвариант, меняя местами дочерние элементы узла, когда правое поддерево превышает левое, как в операциях HBLT.
Объединение двух минимальных WBLT
Операция слияния в WBLT может быть выполнена с использованием одного обхода сверху вниз, поскольку количество узлов в поддеревьях известно до рекурсивного вызова слияния. Таким образом, мы можем поменять местами левое и правое поддеревья, если общее количество узлов в правом поддереве и объединяемом дереве больше, чем количество узлов в левом поддереве. Это позволяет выполнять операции по одному пути и, таким образом, увеличивает временную сложность операций на постоянный коэффициент.
Операция слияния изображена на графике ниже.
Другие операции на WBLT
Вставка и удаление элемента min могут выполняться так же, как для HBLT, с использованием операции слияния.
Хотя WBLT превосходят HBLT по слиянию, вставке и удалению ключа Min с постоянным коэффициентом, О(журнал п) граница не гарантируется при удалении произвольного элемента из WBLT, поскольку θ (п) узлы должны быть пройдены.
Если бы это был HBLT, то удаление листового узла с ключом 60 потребовало бы О(1) время и обновление s-значений не требуется, поскольку длина крайнего правого пути для всех узлов не меняется.
Но в дереве WBLT мы должны обновить вес каждого узла обратно до корня, что требует О(п) худший случай.
Варианты
Существует несколько вариантов основного левого дерева, которые вносят лишь незначительные изменения в основной алгоритм:
- Выбор левого ребенка как более высокий произвольный; "правое дерево" тоже подойдет.
- Можно избежать обмена дочерними элементами, а вместо этого записать который child - самый высокий (например, младший бит s-значения) и используйте его в операции слияния.
- Значение s, используемое для решения, с какой стороны объединяться, может использовать метрику, отличную от высоты. Например, можно использовать вес (количество узлов).
использованная литература
- ^ а б c "Левые деревья" (PDF). www.google.com. Получено 2019-05-31.
- ^ а б Крейн, Кларк А. (1972), Линейные списки и очереди приоритетов как сбалансированные двоичные деревья (Докторская диссертация), факультет компьютерных наук Стэнфордского университета, ISBN 0-8240-4407-X, STAN-CS-72-259
- ^ Сонхун Чо; Сартадж Сахни (1996), "Деревья с левым уклоном и модифицированные списки пропусков" (PDF), Журнал экспериментальной алгоритмики, 3, CiteSeerX 10.1.1.13.2962, Дои:10.1145/297096.297111
- ^ Стюарт, Джеймс (25 сентября 1988 г.). "ЛЕВЫЕ ДЕРЕВЬЯ". Проект динамической графики Университета Торонто. Получено 2019-05-31.
- ^ Чо, Сонхун; Сахни, Сартадж (сентябрь 1998 г.). "Левые деревья с упором на вес и модифицированные списки пропусков". J. Exp. Алгоритмика. 3. Дои: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.