105
правок
Изменения
м
===Удаление максимума===
Дмитрий Мурзин переименовал страницу Левосторонние красно-черные деревья в Левосторонние красно-чёрные деревья: Ёфикация
==Свойства==
*Корневой узел всегда ЧЕРНЫЙ в цветечерный.
*Каждый новый узел всегда окрашен в красный цвет.
*Каждый дочерний нулевой узел листа дерева считается черным.
==Вращения==
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
* Количество черных узлов на каждом таком пути одинаково.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют <tex>3</tex>-узел(совокупность из <tex>3</tex> узлов, где <tex>2</tex> узла являются наследниками третьего, причем одна из связей является красной), левый потомок которого окрашен в красный, в <tex>3</tex>-узел, правый потомок которого окрашен в красный,вторая операция {{---}} наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
===Псевдокод===
[[File:rotateRight.png|310px|thumb|upright|Rotate Right]]
h.color = RED
'''return''' x
==Переворот цветов==
В красно-черных деревьях используется такая операция как '''переворот цветов''' , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.
'''if''' isRed(h.left) '''&&''' isRed(h.right)
colorFlip(h)
'''return''' ''h''
* Спускаемся вниз по правому краю дерева.
* Если поиск заканчивается на узле с <tex>4</tex>-мя или <tex>5</tex>-ю потомками, просто удаляем узел.
h = rotateLeft(h)
colorFlip(h)
'''return''' ''h''
'''void''' deleteMin()
