Изменения

|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

<code> '''void''' flipColors(h : '''Node''' h): h.color = '''!'''h.color h.left.color = '''!'''h.left.color h.right.color Вставка== '''!'''h.right.colorВставка в ЛСКЧД базируется на <tex>4</codetex>простых операциях:

*Вставка нового узла к листу дерева:Если высота узла нулевая, возвращаем новый красный узел.[[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

<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) '''intif''' cmp key = key.compareTo(x.key) '''if''' cmp == 0 '''return''' x.val '''else''' '''if''' cmp key < 0x.key x = x.left

'''if''' cmp key > 0 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">//codeВращение <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| ]] Будем поддерживать инвариант: для любого узла либо сам узел, либо правый предок узла '''красный'''.Будем придерживаться тактики , что удалять лист легче, чем внутренний узел.

==Удаление==Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.<code> '''void''' deleteMin()[[File: root = deleteMin(root) rootMinEasy.png|400px|thumb|right| Перемещение красной ссылки.color = BLACK</code>Простой случай]]

<code> '''Node''' deleteMin( h [[File: '''Node'''): '''if''' h.left == ''null'' '''return''' ''null'' '''if''' !isRed(h.left) '''&&''' !isRed(h.left.left) h = moveRedLeft(h) hMinHard.left = deleteMin(hpng|400px|thumb|right| Перемещение красной ссылки.left) '''return''' fixUp(h)</code>Сложный случай]]

<code>===Псевдокод=== '''Nodevoid''' moveRedLeftdeleteMax('''Node''' h): colorFlip root = deleteMax(hroot): '''if''' isRed(h root.right.left) h.right color = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h </code> BLACK

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

<code> '''Node''' deletedeleteMax(h : '''Node''' : h, ) '''Keyif''' isRed(h.left) <span style="color: key#008000">// вращаем все 3-вершины вправо</span> h = rotateRight(h) <span style="color:#008000">// поддерживаем инвариант (h должен быть красным)</span> '''if''' key.compareTo(h.key) right == ''null'' return ''null'' <span style="color:#008000">// заимствуем у брата если необходимо< 0) /span> '''if''' !isRed(h.leftright) '''&&''' !isRed(h.leftright.left) h = moveRedLeftmoveRedRight(h) <span style="color:#008000">// опускаемся на один уровень глубже </span> h.left = deletedeleteMax(h.left, key) <span style="color:#008000">// исправление правых красных ссылок и 4-вершин на пути вверх</span> '''elsereturn''' fixUp(h) ==Удаление минимума==Поддерживаем инвариант: вершина или левый ребенок вершины красный. Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.[[File:MoveRedLeftEasy.png.png |400px|thumb|upright|Перемещение красной ссылки. Простой случай]][[File:MoveRedLeftNoEasy.png|400px|thumb|upright|Перемещение красной ссылки. Сложный случай]]===Псевдокод=== '''Node''' moveRedLeft(h : '''ifNode''' ) colorFlip(h) if isRed(h.right.left) h .right = rotateRight(h.right) h = rotateLeft(h) colorFlip(h) '''return''' h  '''ifvoid''' key.compareTodeleteMin(h.key) root =deleteMin(root) root.color = 0 BLACK  '''&&Node''' deleteMin(h : '''Node''' ) <span style="color:#008000">// удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span> if h.right left == ''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>[[Категория: Алгоритмы и структуры данных]]