1632
правки
Изменения
м
Из этих инвариантов следует, что длина каждого пути от корня до листьев в красно-черном дереве с <tex>N</tex> узлами не превышает <tex>2 \cdot \log(N)</tex> .
'''return''' x
'''return''' x
if (h == null)
return new Node(key, value, RED)
if (isRed(h.left) && isRed(h.right))
colorFlip(h)
if (isRed(h.right))
h = rotateLeft(h)
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h)
'''return''' ''h''
'''return''' ''null''
==Удаление=====Исправление правых красных связей===
'''return''' h
===Удаление максимума===
'''return''' h
'''return''' h
'''return''' fixUp(h)
rollbackEdits.php mass rollback
{{Определение
|definition = Левосторонние Левостороннее красно-черные деревья черное дерево {{---}} модификация [[Красно-черное дерево|тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черных деревьев]], имеющая ряд преимуществ на классической структурой. Разработана Робертом Соджевиском в <tex>2008</tex> годучерного дерева поиска.
}}
==ПреимуществаСвойства==* необходимо менее <tex>80</tex> строчек кода для реализации структуры Корневой узел всегда черный.* более быстрая вставка, удаление элементовКаждый новый узел всегда окрашен в красный цвет.* простотаКаждый дочерний нулевой узел листа дерева считается черным.
==Вращения==
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
* Ни один обход путь от корня до листьев дерева не содержит двух последовательных красных узлов.
* Количество черных узлов на каждом таком пути одинаково.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращениямивращением вправо и вращением влево. Эти операции Первая операция трансформируют <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
[[File:rotateLeft.png|310px|thumb|upright|Rotate Left]]
'''Node''' rotateLeft(h : '''Node''')
x.color = h.color
h.color = RED
==Переворот цветов==
В красно-черных деревьях используется такая операция как '''Переворот переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов при на любом обходе пути от корня до листьев деревалиста, но может привести к появлению двух последовательных красных узлов. ===Псевдокод===
[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]]
'''void''' flipColors(h : '''Node''' h)
h.color = '''!''' h.color
h.left.color = '''!''' h.left.color h.right.color = <tex> '''!</tex> ''' h.right.color
==Вставка==
Если высота узла нулевая, возвращаем новый красный узел.
[[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 : '''keyKey''' , value : Key, '''valueValue''' : 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> '''intif''' cmp key = key.compareTo(h.key) '''if''' (cmp == 0)
h.val = value
'''else'''
'''if''' cmp key < 0 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)
==Поиск==
Поиск в левосторонних красно-черных деревьях эквивалентен поиску в [[Дерево поиска, наивная реализация|наивной реализации дерева поиска]].
Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от вершины корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы <tex>O(h)</tex>, где <tex>h</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 < 0)x.key
x = x.left
'''else'''
'''if''' (cmp key > 0) x.key
x = x.right
*Использование Переворота цветов и вращений сохраняет баланс черной связи.
*После удаления необходимо исправить правые красные связи и устранить узлы с <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)
* Спускаемся вниз по правому краю дерева.
* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел.
'''Node''' moveRedLeft(h : '''Node''')
colorFlip(h)
'''if (''' isRed(h.right.left)
h.right = rotateRight(h.right)
h = rotateLeft(h)
colorFlip(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)
'''Node''' moveRedLeft(h : '''Node''')
colorFlip(h)
if (isRed(h.right.left))
h.right = rotateRight(h.right)
h = rotateLeft(h)
colorFlip(h)
'''void''' deleteMin()
'''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)
==Асимптотика==
Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике [[Красно-черное дерево|левосторонних базовой реализации красно-черных деревьях]].
== См.также ==
