1632
правки
Изменения
м
* <tex> \mathrm{push}(i, x)</tex> {{---}} добавляет элемент <tex>x</tex> в стек узла <tex>i</tex>, '''StackNode''' pushmoveRedLeft(i h : '''Node''', x : ) colorFlip(h) '''Tif'''):isRed(h.right.left k h.value right = xrotateRight(h.right) k.prev h = irotateLeft(h) s.top = k colorFlip(h) '''return''' sh
* '''Node''' deleteMax(h : '''Node''') '''if''' isRed(h.left) <texspan style="color:#008000">\mathrm{pop}(i)// вращаем все 3-вершины вправо</texspan> {{---}} возвращает значение, хранящееся в узле h = rotateRight(h) <texspan style="color:#008000">i// поддерживаем инвариант (h должен быть красным)</texspan> и копирует элемент, предыдущий для него '''if''' h. right == ''null'' return 'pair<T, Stack>'null'' pop(i <span style="color: #008000">// заимствуем у брата если необходимо</span> '''Nodeif'''!isRed(h.right): '''T&&''' val !isRed(h.right.left) h = imoveRedRight(h) <span style="color:#008000">// опускаемся на один уровень глубже </span> h.left = deleteMax(h.value left) i <span style= i.prev"color:#008000">// исправление правых красных ссылок и 4-вершин на пути вверх</span> '''return''' pairfixUp(val, sh)
<code>Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.[[File:MoveRedLeftEasy.png.png |400px|thumb|upright|Перемещение красной ссылки. Простой случай]][[File:MoveRedLeftNoEasy.png|400px|thumb|upright|Перемещение красной ссылки. Сложный случай]]===Псевдокод=== '''Node '''rotateRightmoveRedLeft(h : '''Node '''): x = colorFlip(h) if isRed(h.right.left) h.leftright = xrotateRight(h.right) x.right= h x.color = rotateLeft(h.color) colorFlip(h.color = RED) '''return ''' x</code>h
<code> '''Nodevoid''' rotateLeftdeleteMin(h : '''Node'''): x root = h.right h.right = x.leftdeleteMin(root) x.left = h x.color = h.color h root.color = RED '''return''' x</code>BLACK
<code> '''voidNode''' flipColorsdeleteMin(h : '''Node''' ) <span style="color:#008000">// удаляем узел на нижнем уровне(hдолжен быть красным по инварианту):</span> if h.color left == ''null'' '''return''' ''null'' <span style= !h."color:#008000">// Если необходимо, пропушим красную ссылку вниз</span> '''if (!'''isRed(h.left.color = ) '''&& !'''isRed(h.left.colorleft)) h.right.color = !moveRedLeft(h.right.) <span style="color:#008000">// опускаемся на уровень ниже </codespan> h.left ==Методы==deleteMin(h.left) '''return''' fixUp(h)
<code> '''void''' insert( '''key''' : Key, '''value''' : Value ): root = insert(root, key, value);=Асимптотика== rootАсимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|базовой реализации красно-черных деревьях]].color = BLACK;</code>
<code> '''Node''' insert( h : Node, key : Key, value : Value) if (h == null) '''return''' ''new Node(key, value)''; 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); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); '''return''' ''h''* Robert Sedgewick "Left-leaning Red-Black Trees" ,Department of Computer Science, Princeton University</code>[[Категория: Алгоритмы и структуры данных]]
rollbackEdits.php mass rollback
{{Определение
|definition = Left Левостороннее красно-leaning Redчерное дерево {{-Black Trees --}} тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска. }} ==Свойства==*Корневой узел всегда черный.*Каждый новый узел всегда окрашен в красный цвет.*Каждый дочерний нулевой узел листа дерева считается черным.
==Вращения==
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
* Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.
* Количество черных узлов на каждом таком пути одинаково.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево. Первая операция трансформируют <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
==Удаление минимума==
Поддерживаем инвариант: вершина или левый ребенок вершины красный.
