Изменения

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

 ==ПреимуществаСвойства==* необходимо менее <tex>80</tex> строчек кода для реализации структуры Корневой узел всегда черный.* более быстрая вставка, удаление элементовКаждый новый узел всегда окрашен в красный цвет.* простотаКаждый дочерний нулевой узел листа дерева считается черным.

Чтобы поддерживать левосторонние красно-черные двоичное двоичные деревья поиска необходимо соблюдать следующие инвариантные свойства инварианты при вставке и удалении:* Ни один обход путь от корня до листьев дерева не содержит двух последовательных красных узлов.

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращениямивращением вправо и вращением влево. Эти операции Первая операция трансформируют <tex>3</tex>-узел(совокупность из <tex>3</tex> узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной),левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный и ,вторая операция {{---}} наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.===ПсевокодПсевдокод===

'''Node''' rotateRight( h : '''Node''') :

h.left= x.right x.right= h

'''return''' x

'''Node''' rotateLeft( h : '''Node''') :

'''return''' x

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

h.left.color = '''!''' h.left.color h.right.color = <tex> '''!</tex> ''' h.right.color

Если левый предок и правый предок красные, запускаем вращение переворот цветов от текущего узла.

'''void''' insert( key : '''keyKey''' , value : Key, '''valueValue''' : Value ):

'''Node''' insert( h : '''Node''', key : '''Key''', value : '''Value'''): <span style="color:#008000">//Вставка нового узла к листу деревалиста</span>

<span style="color:#008000">//Расщепление узла с <tex>4</tex>-я потомками</span>

<span style="color:#008000">//Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span> '''intif''' cmp key = key.compareTo(h.key) '''if''' cmp == 0

'''if''' cmp key < 0 h.key

<span style="color:#008000">//Принудительное вращение влево</span> '''if''' isRed(h.right) '''&&''' '''!'''isRed(h.left)

<span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span>

'''return''' ''h''

Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом, который проходит от вершины корня до искомого элемента. Если же элемент отсутствует , цикл пройдет то до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева.

'''Value''' search(key : '''Key'''):

'''intif''' cmp key = key.compareTo(x.key) '''if''' (cmp == 0)

'''if''' (cmp key < 0)x.key

'''if''' (cmp key > 0) x.key

'''return''' ''null''

==Удаление=====Исправление правых красных связей===

*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4--</tex>-я потомками <span style="color:#008000">//Исправление правых красных связей</span>

'''if''' (isRed(h.right)) h = rotateLeft(h); <span style="color:#008000">//Вращение <tex>2</tex>-ой красной пары пары</span> '''if''' (isRed(h.left) '''&&''' isRed(h.left.left)) h = rotateRight(h); <span style="color:#008000">//Балансировка узла с <tex>4</tex>-я потомками</span> '''if''' (isRed(h.left) '''&&''' isRed(h.right)) colorFlip(h); '''return''' h;

===Удаление максимума===

* Удаление узла с <tex>2</tex>-я потомками разрушает нарушает балансСоответственно , спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно <tex>2</tex>-м.

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

root = deleteMax(root); root.color = BLACK;

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

'''if (''' isRed(h.left)) <span style="color:#008000">//вращаем все 3-вершины вправо</span> h = rotateRight(h); <span style="color:#008000">//поддерживаем инвариант (h должен быть красным)</span> '''if (''' h.right == ''null) '' return ''null;'' <span style="color:#008000">//заимствуем у брата если необходимо</span> '''if (''' !isRed(h.right) '''&&''' !isRed(h.right.left)) h = moveRedRight(h);

h.left = deleteMax(h.left); <span style="color:#008000">//исправление правых красных ссылок и 4-вершин на пути вверх</span> '''return''' fixUp(h);

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

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

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

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