Левосторонние красно-чёрные деревья

2018-05-23T22:54:40Z

138.197.160.42: /* Вставка */

{{Определение
|definition = Левосторонние красно-черные деревья {{---}} модификация [[Красно-черное дерево|красно-черных деревьев]], имеющая ряд преимуществ на классической структурой. Разработана Робертом Соджевиском в <tex>2008</tex> году.
}}
==Преимущества==
* необходимо менее <tex>80</tex> строчек кода для реализации структуры
* более быстрая вставка, удаление элементов
* простота

==Вращения==
Чтобы поддерживать красно-черные двоичное деревья поиска необходимо соблюдать следующие инвариантные свойства при вставке и удалении:
* Ни один обход от корня до листьев дерева не содержит двух последовательных красных узлов.
* Количество черных узлов на каждом таком пути одинаково.
Из этих инвариантов следует, что длина каждого пути от корня до листьев в красно-черном дереве с <tex>N</tex> узлами не превышает <tex>2 \cdot \log(N)</tex> .

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращениями. Эти операции трансформируют <tex>3</tex>-узел,левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный и наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
===Псевокод===
[[File:rotateRight.png|310px|thumb|upright|Rotate Right]]
'''Node''' rotateRight( h : '''Node''') :
x = h.left
h.left= x.right
x.right= h
x.color = h.color
h.color = RED
'''return''' x
[[File:rotateLeft.png|310px|thumb|upright|Rotate Left]]
'''Node''' rotateLeft( h : '''Node''') :
x = h.right
h.right = x.left
x.left = h
x.color = h.color
h.color = RED
'''return''' x

==Переворот цветов==

В красно-черных деревьях используется такая операция как '''Переворот цветов''' <tex>(flip color)</tex> , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов при любом обходе от корня до листьев дерева, но может привести к появлению двух последовательных красных узлов.
[[File: ColorFlip.png|320px|thumb|upright| Color Flip]]

'''void''' flipColors( h : '''Node''' h) :
h.color = '''!''' h.color
h.left.color = '''!''' h.left.color
h.right.color = <tex> !</tex> h.right.color

==Вставка==
Вставка в ЛСКЧД базируется на <tex>4</tex> простых операциях:

*Вставка нового узла к листу дерева:
Если высота узла нулевая, возвращаем новый красный узел.
[[File:insertNode.png|310px|thumb|upright|Вставка нового узла]]

if (h == null)
return new Node(key, value, RED);

*Расщепление узла с <tex>4</tex>-я потомками:
Если левый предок и правый предок красные, запускаем вращение цветов от текущего узла.
[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]
if (isRed(h.left) && isRed(h.right))
colorFlip(h);

*Принудительное вращение влево:
[[File:Enforce.png|310px|thumb|upright|Принудительное вращение]]
Если правый предок красный, вращаем текущую вершину влево.
if (isRed(h.right))
h = rotateLeft(h);

*Балансировка узла с <tex>4</tex>-я потомками:
[[File:Balance4node.png|310px|thumb|Балансировка]]
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
if (isRed(h.left) && isRed(h.left.left))
h = rotateRight(h);

===Псевдокод===
'''void''' insert( '''key''' : Key, '''value''' : Value ):
root = insert(root, key, value)
root.color = BLACK

'''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''):
//Вставка нового узла к листу дерева
'''if''' h == ''null''
'''return''' '''new''' Node(key, value)
//Расщепление узла с <tex>4</tex>-я потомками
'''if''' isRed(h.left) '''&&''' isRed(h.right)
colorFlip(h)
//Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]
'''int''' cmp = key.compareTo(h.key)
'''if''' cmp == 0
h.val = value
'''else'''
'''if''' cmp < 0
h.left = insert(h.left, key, value)
'''else'''
h.right = insert(h.right, key, value)
//Принудительное вращение влево
'''if''' isRed(h.right) '''&&''' '''!'''isRed(h.left)
h = rotateLeft(h)
//Балансировка узла с <tex>4</tex>-я потомками
'''if''' isRed(h.left) '''&&''' isRed(h.left.left)
h = rotateRight(h)
'''return''' ''h''

==Поиск==
Поиск в левосторонних красно-черных деревьях эквивалентен поиску в [[Дерево поиска, наивная реализация|наивной реализации дерева поиска]].
Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом, проходит от вершины до искомого элемента. Если же элемент отсутствует цикл пройдет то листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.
===Псевдокод===
'''Value''' search(key : '''Key'''):
'''Node''' x = root
'''while''' (x '''!'''= null)
'''int''' cmp = key.compareTo(x.key)
'''if''' (cmp == 0)
'''return''' x.val
'''else'''
'''if''' (cmp < 0)
x = x.left
'''else'''
'''if''' (cmp > 0)
x = x.right
'''return''' ''null''

==Удаление==
===Исправление правых красных связей===
*Использование Переворота цветов и вращений сохраняет баланс черной связи.
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4-</tex>я потомками
//Исправление правых красных связей
'''Node''' fixUp(h : '''Node'''){
'''if''' (isRed(h.right))
h = rotateLeft(h);
//Вращение <tex>2</tex>-ой красной пары пары
'''if''' (isRed(h.left) '''&&''' isRed(h.left.left))
h = rotateRight(h);
//Балансировка узла с <tex>4</tex>-я потомками
'''if''' (isRed(h.left) '''&&''' isRed(h.right))
colorFlip(h);
'''return''' h;
}

===Удаление максимума===
* Спускаемся вниз по правому краю дерева.
* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел.

[[File:34-nodeRemove.png|310px|thumb|center| Узлы до и после удаления]]
* Удаление узла с <tex>2</tex>-я потомками разрушает баланс
Соответственно спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно <tex>2</tex>-м.
[[File:changeNode.png|600px|thumb|center| ]]

Будем поддерживать инвариант : Для любого узла либо сам узел, либо правый предок узла '''красный'''.
Будем придерживаться тактики , что удалять лист легче, чем внутренний узел.

Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.
[[File:MinEasy.png|400px|thumb|right| Перемещение красной ссылки. Простой случай]]

[[File:MinHard.png|400px|thumb|right| Перемещение красной ссылки. Сложный случай]]

===Псевдокод===
'''void''' deleteMax()
root = deleteMax(root);
root.color = BLACK;

'''Node''' moveRedLeft(h : '''Node''')
colorFlip(h);
if (isRed(h.right.left)
h.right = rotateRight(h.right);
h = rotateLeft(h);
colorFlip(h);
'''return''' h;

'''Node''' deleteMax(h : '''Node''')
if (isRed(h.left))
//вращаем все 3-вершины вправо
h = rotateRight(h);
//поддерживаем инвариант (h должен быть красным)
if (h.right == null)
return null;
//заимствуем у брата если необходимо
if (!isRed(h.right) '''&&''' !isRed(h.right.left))
h = moveRedRight(h);
// опускаемся на один уровень глубже 
h.left = deleteMax(h.left);
//исправление правых красных ссылок и 4-вершин на пути вверх
'''return''' fixUp(h);

==Удаление минимума==
Поддерживаем инвариант: вершина или левый ребенок вершины красный.

Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.
[[File:MoveRedLeftEasy.png.png |400px|thumb|upright|Перемещение красной ссылки. Простой случай]]
[[File:MoveRedLeftNoEasy.png|400px|thumb|upright|Перемещение красной ссылки. Сложный случай]]
===Псевдокод===
'''Node''' moveRedLeft(h : '''Node''')
colorFlip(h);
if (isRed(h.right.left))
h.right = rotateRight(h.right);
h = rotateLeft(h);
colorFlip(h);
'''return''' h;

'''void''' deleteMin()
root = deleteMin(root);
root.color = BLACK;

'''Node''' deleteMin(h : '''Node''')
//удаляем узел на нижнем уровне(h должен быть красным по инварианту)
if (h.left == ''null'')
'''return''' ''null'';
//Если необходимо, пропушим красную ссылку вниз
'''if !'''isRed(h.left) '''&& !'''isRed(h.left.left)
h = moveRedLeft(h);
//опускаемся на уровень ниже 
h.left = deleteMin(h.left);
'''return''' fixUp(h);

==Асимптотика==
Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|левосторонних красно-черных деревьях]].

==Источники информации==
* Robert Sedgewick "Left-leaning Red-Black Trees" ,Department of Computer Science, Princeton University
== См.также ==
*[[Красно-черное дерево]]
*[[Дерево поиска, наивная реализация]]

[[Категория: Алгоритмы и структуры данных]]

Викиконспекты - Вклад участника [ru]

Левосторонние красно-чёрные деревья