Изменения

{{Определение|definition = Left Левостороннее красно-leaning Redчерное дерево {{-Black Trees --}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска. }} ==Свойства==*Корневой узел всегда черный.*Каждый новый узел всегда окрашен в красный цвет.*Каждый дочерний нулевой узел листа дерева считается черным. 

Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют <tex>3</tex>-узел (совокупность из <tex>3<code/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</code>

<code>==Переворот цветов==В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.===Псевдокод===[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]] '''Nodevoid''' rotateLeftflipColors(h : '''Node'''h): x h.color = '''!''' h.rightcolor h.right = x.left x.left color = '''!''' h x.color = hleft.color h.right.color = RED '''return!''' x</code>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<code/tex>-я потомками:[[File:Balance4node.png|310px|thumb|Балансировка]]Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.  ===Псевдокод=== '''void''' flipColorsinsert(h key : '''NodeKey''', value : '''Value''' h): h.color root = !h.colorinsert(root, key, value) h.left.color = !h.left.color h.right.color = !h.right root.color</code>==Методы==BLACK

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

<span style="color:#008000">// Расщепление узла с <tex>4</tex>-я потомками</span> '''if''' isRed(h.left) '''&&''' isRed(h.right) colorFlip(h) <span style="color:#008000">// Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span> '''intif''' cmp key = h.key.compareTo( h.key) val = value '''else''' '''if''' key < h.key cmp == 0 h.val left = insert(h.left, 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>

h = rotateRight(h) '''return''' ''h''</code>

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

'''if''' cmp key > 0 x.key x = x.right '''return''''' null</code>''

==УдалениеИсправление правых красных связей==*Использование Переворота цветов и вращений сохраняет баланс черной связи.*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4</tex>-я потомками <span style="color:#008000">// Исправление правых красных связей<code/span> '''Node''' fixUp(h : '''Node''') void deleteMin '''if''' isRed(h.right): root h = deleteMinrotateLeft(rooth) root <span style="color:#008000">// Вращение <tex>2</tex>-ой красной пары пары</span> '''if''' isRed(h.left) '''&&''' isRed(h.left.color left) h = BLACKrotateRight(h) <span style="color:#008000">/code/ Балансировка узла с <tex>4</tex>-я потомками</span> '''if''' isRed(h.left) '''&&''' isRed(h.right) colorFlip(h) '''return''' h

<code> '''Node''' deleteMin( h : '''Node'''): '''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)* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</codetex>-ю потомками, просто удаляем узел.

[[File:34-nodeRemove.png|310px|thumb|center| Узлы до и после удаления]] * Удаление узла с <codetex>2</tex>-я потомками нарушает баланс '''Node''' moveRedLeft('''Node''' h)Соответственно, спускаясь вниз по дереву необходимо поддерживать следующий инвариант :количество потомков узла не должно быть ровно <tex>2</tex>-м. colorFlip(h)[[File:changeNode.png|600px|thumb|center| ]] Будем поддерживать инвариант: для любого узла либо сам узел, либо правый предок узла '''ifкрасный''' isRed(h.right.left) hБудем придерживаться тактики , что удалять лист легче, чем внутренний узел.right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h </code>

Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.[[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) <codespan 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''' moveRedRightmoveRedLeft(h :'''Node''' ):

'''if''' isRed(h.leftright.left) h.right = rotateRight(h.right) h = rotateRightrotateLeft(h) colorFlip(h) '''return''' h </code><code> '''void''' delete(key : '''Key'''): root = delete(root, key) root.color = BLACK </code>

<code> '''Nodevoid''' deletedeleteMin('''Node''' : h, '''Key''' : key): '''if''' key.compareTo root = deleteMin(h.key) < 0root) '''if''' !isRed(h root.left) '''&&''' !isRed(h.left.left)color = BLACK h = moveRedLeft(h) h.left = delete(h.left, key) '''elseNode''' deleteMin(h : '''ifNode''' isRed(h.left) h <span style= rotateRight"color:#008000">// удаляем узел на нижнем уровне(hдолжен быть красным по инварианту)</span> ''' if''' key.compareTo(h.key) left == 0 ''null'&&''' (h.right == null) '''return''' ''null'' <span style="color:#008000">// Если необходимо, пропушим красную ссылку вниз</span> '''if (!''' !isRed(h.rightleft) '''&& !''' !isRed(h.rightleft.left)) h = moveRedRightmoveRedLeft(h) '''if''' key.compareTo(h.key) <span style== 0"color:#008000">// опускаемся на уровень ниже </span> h.val = get(h.right, min(h.right).key) h.key = min(h.right).key h.right left = deleteMin(h.rightleft) '''elsereturn''' fixUp(h)  h==Асимптотика==Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|базовой реализации красно-черных деревьях]].right  = delete(h= См.rightтакже ==*[[Красно-черное дерево]]*[[Дерево поиска, key)наивная реализация]]==Источники информации== '''return''' fixUp(h)* Robert Sedgewick "Left-leaning Red-Black Trees" ,Department of Computer Science, Princeton University</code>[[Категория: Алгоритмы и структуры данных]]