Изменения

|definition = Левостороннее красно-черное дерево {{---}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска. }} ==Свойства==*Корневой узел всегда черный.*Каждый новый узел всегда окрашен в красный цвет.*Каждый дочерний нулевой узел листа дерева считается черным. ==Вращения==Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:* Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.* Количество черных узлов на каждом таком пути одинаково. Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют <tex>3</tex>-узел (совокупность из <tex>3</tex> узлов, где <tex>2</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 ==Переворот цветов==В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.===Псевдокод===[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]] '''void''' flipColors(h : '''Node''' h) h.color = '''!''' h.color h.left.color = '''!''' h.left.color h.right.color = '''!''' h.right.color ==Вставка==Вставка в ЛСКЧД базируется на <tex>4</tex> простых операциях: *Вставка нового узла к листу дерева:Если высота узла нулевая, возвращаем новый красный узел.[[File:insertNode.png|310px|thumb|upright|Вставка нового узла]]*Расщепление узла с <tex>4</tex>-я потомками:Если левый предок и правый предок красные, запускаем переворот цветов от текущего узла.[[File:Split4node.png|310px|thumb|upright|Расщепление узла]]*Принудительное вращение влево:[[File:Enforce.png|310px|thumb|upright|Принудительное вращение]]Если правый предок красный, вращаем текущую вершину влево.*Балансировка узла с <tex>4</tex>-я потомками:[[File:Balance4node.png|310px|thumb|Балансировка]]Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.  ===Псевдокод=== '''void''' insert(key : '''Key''', value : '''Value''' ) root = insert(root, key, value) root.color = BLACK   '''Node''' insert(h : '''Node''', key : '''Key''', value : '''Value''') <span style="color:#008000">// Вставка нового листа</span> '''if''' h == ''null'' '''return''' '''new''' Node(key, value) <span style="color:#008000">// Расщепление узла с <tex>4</tex>-я потомками</span> '''if''' isRed(h.left) '''&&''' isRed(h.right) colorFlip(h) <span style="color:#008000">// Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span> '''if''' key = h.key h.val = value '''else''' '''if''' key < h.key h.left = insert(h.left, key, value) '''else''' h.right = insert(h.right, key, value) <span style="color:#008000">// Принудительное вращение влево</span> '''if''' isRed(h.right) '''&&''' '''!'''isRed(h.left) h = rotateLeft(h) <span style="color:#008000">// Балансировка узла с <tex>4</tex>-я потомками</span> '''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) '''if''' key = x.key '''return''' x.val '''else''' '''if''' key < x.key x = x.left '''else''' '''if''' key > x.key x = x.right '''return''' ''null'' ==Исправление правых красных связей==*Использование Переворота цветов и вращений сохраняет баланс черной связи.*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4</tex>-я потомками <span style="color:#008000">// Исправление правых красных связей</span> '''Node''' fixUp(h : '''Node''') '''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>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) <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) <span style="color:#008000">// опускаемся на один уровень глубже </span> h.left = deleteMax(h.left) <span style="color:#008000">// исправление правых красных ссылок и 4-вершин на пути вверх</span> '''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''') <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) ==Асимптотика==Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|базовой реализации красно-черных деревьях]]. == См.также ==*[[Красно-черное дерево]]*[[Дерево поиска, наивная реализация]]==Источники информации==* Robert Sedgewick "Left-leaning Red-Black Trees . " ,Department of Computer Science, Princeton University}}[[Категория: Алгоритмы и структуры данных]]