105
правок
Изменения
м
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный атрибут — цвет и для которого выполняются следующие свойства:*Корневой узел всегда черный.*Каждый новый узел промаркирован красным или чёрным цветомвсегда окрашен в красный цвет.*Корень и конечные узлы (листья) Каждый дочерний нулевой узел листа дерева — чёрныесчитается черным.*У красного узла родительский узел — чёрный*Все простые пути из любого узла 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)
==Удаление=====Исправление правых красных связей===
===Удаление максимума===
Дмитрий Мурзин переименовал страницу Левосторонние красно-черные деревья в Левосторонние красно-чёрные деревья: Ёфикация
{{Определение
|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''')
h.color = RED
'''return''' x
==Переворот цветов==
В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.
===Псевдокод===
[[File: ColorFlip.png|320px|thumb|upright| Переворот цветов]]
'''void''' flipColors(h : '''Node''' h)
Если высота узла нулевая, возвращаем новый красный узел.
[[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|Балансировка]]
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
===Псевдокод===
colorFlip(h)
<span style="color:#008000">// Стандартная вставка [[Дерево поиска, наивная реализация|в дереве поиска]]</span>
'''if''' key > = h.key cmp = 1 '''else''' cmp = 0 '''if''' cmp == 0
h.val = value
'''else'''
'''if''' cmp key < 0 h.key
h.left = insert(h.left, key, value)
'''else'''
'''if''' isRed(h.left) '''&&''' isRed(h.left.left)
h = rotateRight(h)
'''return''' ''h''
==Поиск==
'''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
'''else'''
'''if''' cmp key > 0 x.key
x = x.right
'''return''' ''null''
*Использование Переворота цветов и вращений сохраняет баланс черной связи.
*После удаления необходимо исправить правые красные связи и устранить узлы с <tex>4</tex>-я потомками
'''if''' isRed(h.left) '''&&''' isRed(h.right)
colorFlip(h)
'''return''' ''h''
* Спускаемся вниз по правому краю дерева.
* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел.
h = rotateLeft(h)
colorFlip(h)
'''return''' ''h''
'''Node''' deleteMax(h : '''Node''')
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)
'''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()
'''Node''' deleteMin(h : '''Node''')
<span style="color:#008000">// удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span>
if (h.left == ''null'')
'''return''' ''null''
<span style="color:#008000">// Если необходимо, пропушим красную ссылку вниз</span>
