Изменения
Новая страница: «==Определение== Левосторонние деревья были изобретены Кларком Крейном (Clark Allan Crane), свое н...»
==Определение==
Левосторонние деревья были изобретены Кларком Крейном (Clark Allan Crane), свое название они получили из-за того, что левое поддерево обычно длиннее правого.
{{Определение
|definition='''Левосторонняя куча (leftist heap)''' — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи (heap order).}}
{{Лемма
|id=lemma1
|about=1
|statement=В двоичном дереве с n вершинами существует свободная позиция на глубине не более logn.
|proof=Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более n. }}
Левосторонняя куча накладывает на двоичное дерево дополнительное условие.
Ближайшая свободная позиция должна быть самой правой позицией в дереве. То есть помимо условия кучи выполняется следующее:
{{Определение
|definition=Условие левосторонней кучи. Пусть dist(х) – расстояние от вершины u до ближайшей свободной позиции в ее поддереве. У пустых позиций dist = 0. Тогда потребуем для любой вершины х: dist(x.L)>= dict(x.R).}}
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за О(1) поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
==Поддерживаемые операции==
===merge===
Слияние двух куч.
merge(x,y) //x,y – корни двух деревьев
if x == NULL return y
if y == NULL return x
if y.key < x.key :
x<-> y
//Воспользуемся тем, что куча левосторонняя. Правая ветка — самая короткая и не длиннее
//логарифма. Пойдем направо и сольем правое поддерево с у.
x.R<-merge(x.R, y)
//Могло возникнуть нарушение левостороннести кучи.
If dist(x.R) > dist(x.L): x.L<->x.R
update dist(x) //dist(x) = min(dist(x.L), dist(x.R)) + 1
return x;
//Каждый раз идет в уже существующей вершине только в правое поддерево — не более логарифма вызовов (по лемме).
Так как левосторонняя куча относится к сливаемым кучам, остальные операции легко реализуются с помощью операции слияния.
===insert===
Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.
===extractMin===
Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.
===delete===
Аналогично удаляется любой элемент — на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя — на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью decrease key. Уменьшаем ключ до -inf, затем извлекаем минимальное значение.
===decKey===
{{Лемма
|id=lemma2
|about=2
|statement=У левостороннего дерева с правой ветвью длинны h количество узлов n>= 2^h – 1.
|proof=Индукция по h.
При h = 1 – верно.
При h > 1 левое и правое поддеревья исходного дерева левосторонние, а dist от их корней >= h – 1. По индукции число узлов в каждом из них >=2^(h - 1) – 1, тогда во все дереве n >= (2^(h – 1) – 1) + (2^(h – 1) – 1) +1 = 2^h – 1 узлов.}}
====Алгоритм====
1. Найдем узел х, вырежем поддерево с корнем в этом узле.
2. Пройдем от предка вырезанной вершины, при этом пересчитывая dist. Если dist левого сына вершины меньше dist правого, то меняем местами поддеревья.
{{Лемма
|id=lemma3
|about=3
|statement= Нужно транспонировать не более logn поддеревьев.
|proof=Длина пути от вершины до корня может быть и O(n), но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левостороннести уже выполнено. Транспонируем только если dist(x.L) < dist(x.R), но dist(x.R) <= logn. На каждом шаге, если нужно транспонируем и увеличиваем dist++, тогда dist увеличится до logn и обменов уже не надо будет делать.}}
Таким образом, мы восстановили левостороннесть кучи за O(logn)
3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное. O(logn)
==Построение кучи за О(n)==
Храним список левосторонних куч. Пока их количество больше >1, из начала списка достаем две кучи, сливаем их и кладем в конец списка.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в merge. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация merge является персистентной.
Левосторонние деревья были изобретены Кларком Крейном (Clark Allan Crane), свое название они получили из-за того, что левое поддерево обычно длиннее правого.
{{Определение
|definition='''Левосторонняя куча (leftist heap)''' — двоичное левосторонее дерево (не обязательно сбалансированное), но с соблюдением порядка кучи (heap order).}}
{{Лемма
|id=lemma1
|about=1
|statement=В двоичном дереве с n вершинами существует свободная позиция на глубине не более logn.
|proof=Если бы все свободные позиции были на глубине более логарифма, то мы получили бы полное дерево с количеством вершин более n. }}
Левосторонняя куча накладывает на двоичное дерево дополнительное условие.
Ближайшая свободная позиция должна быть самой правой позицией в дереве. То есть помимо условия кучи выполняется следующее:
{{Определение
|definition=Условие левосторонней кучи. Пусть dist(х) – расстояние от вершины u до ближайшей свободной позиции в ее поддереве. У пустых позиций dist = 0. Тогда потребуем для любой вершины х: dist(x.L)>= dict(x.R).}}
Если для какой- то вершины это свойство не выполняется, то это легко устраняется: можно за О(1) поменять местами левого и правого ребенка, что не повлияет на порядок кучи.
==Поддерживаемые операции==
===merge===
Слияние двух куч.
merge(x,y) //x,y – корни двух деревьев
if x == NULL return y
if y == NULL return x
if y.key < x.key :
x<-> y
//Воспользуемся тем, что куча левосторонняя. Правая ветка — самая короткая и не длиннее
//логарифма. Пойдем направо и сольем правое поддерево с у.
x.R<-merge(x.R, y)
//Могло возникнуть нарушение левостороннести кучи.
If dist(x.R) > dist(x.L): x.L<->x.R
update dist(x) //dist(x) = min(dist(x.L), dist(x.R)) + 1
return x;
//Каждый раз идет в уже существующей вершине только в правое поддерево — не более логарифма вызовов (по лемме).
Так как левосторонняя куча относится к сливаемым кучам, остальные операции легко реализуются с помощью операции слияния.
===insert===
Вставка новой вершины в дерево. Новое левостороннее дерево, состоящее из одной вершины, сливается с исходным.
===extractMin===
Как и у любой другой двоичной кучи, минимум хранится в корне. Извлекаем минимальное значение, удаляем корень, сливаем левое и правое поддерево корня. Возвращает пару из извлеченной вершины и новой кучи.
===delete===
Аналогично удаляется любой элемент — на его место ставится результат слияния его детей. Но так просто любой элемент удалить нельзя — на пути от этого элемента к корню может нарушиться левостороннесть кучи. А до корня мы дойти не можем, так как элемент может находиться на линейной глубине. Поэтому удаление реализуется с помощью decrease key. Уменьшаем ключ до -inf, затем извлекаем минимальное значение.
===decKey===
{{Лемма
|id=lemma2
|about=2
|statement=У левостороннего дерева с правой ветвью длинны h количество узлов n>= 2^h – 1.
|proof=Индукция по h.
При h = 1 – верно.
При h > 1 левое и правое поддеревья исходного дерева левосторонние, а dist от их корней >= h – 1. По индукции число узлов в каждом из них >=2^(h - 1) – 1, тогда во все дереве n >= (2^(h – 1) – 1) + (2^(h – 1) – 1) +1 = 2^h – 1 узлов.}}
====Алгоритм====
1. Найдем узел х, вырежем поддерево с корнем в этом узле.
2. Пройдем от предка вырезанной вершины, при этом пересчитывая dist. Если dist левого сына вершины меньше dist правого, то меняем местами поддеревья.
{{Лемма
|id=lemma3
|about=3
|statement= Нужно транспонировать не более logn поддеревьев.
|proof=Длина пути от вершины до корня может быть и O(n), но нам не нужно подниматься до корня — достаточно подняться до вершины, у которой свойство левостороннести уже выполнено. Транспонируем только если dist(x.L) < dist(x.R), но dist(x.R) <= logn. На каждом шаге, если нужно транспонируем и увеличиваем dist++, тогда dist увеличится до logn и обменов уже не надо будет делать.}}
Таким образом, мы восстановили левостороннесть кучи за O(logn)
3. Уменьшаем ключ данного узла и сливаем два дерева: исходное и вырезанное. O(logn)
==Построение кучи за О(n)==
Храним список левосторонних куч. Пока их количество больше >1, из начала списка достаем две кучи, сливаем их и кладем в конец списка.
==Преимущества левосторонней кучи==
Нигде не делается уничтожающих присваиваний. Не создается новых узлов в merge. Эта реализация слияния является функциональной — ее легко реализовать на функциональном языке программирования. Также данная реалзация merge является персистентной.
