Левосторонние красно-чёрные деревья — различия между версиями
(→Псевдокод) |
(→Псевдокод) |
||
| Строка 171: | Строка 171: | ||
'''Node''' moveRedLeft(h : '''Node''') | '''Node''' moveRedLeft(h : '''Node''') | ||
colorFlip(h) | colorFlip(h) | ||
| − | if | + | if isRed(h.right.left) |
h.right = rotateRight(h.right) | h.right = rotateRight(h.right) | ||
h = rotateLeft(h) | h = rotateLeft(h) | ||
| Строка 183: | Строка 183: | ||
'''Node''' deleteMin(h : '''Node''') | '''Node''' deleteMin(h : '''Node''') | ||
<span style="color:#008000">// удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span> | <span style="color:#008000">// удаляем узел на нижнем уровне(h должен быть красным по инварианту)</span> | ||
| − | if | + | if h.left == ''null'' |
'''return''' ''null'' | '''return''' ''null'' | ||
<span style="color:#008000">// Если необходимо, пропушим красную ссылку вниз</span> | <span style="color:#008000">// Если необходимо, пропушим красную ссылку вниз</span> | ||
Версия 14:09, 20 июня 2018
| Определение: |
| Левостороннее красно-черное дерево — тип сбалансированного двоичного дерева поиска, гарантирующий такую же асимптотическую сложность операций, как у красно-черного дерева поиска. |
Содержание
Свойства
- Корневой узел всегда ЧЕРНЫЙ в цвете.
- Каждый новый узел всегда окрашен в красный цвет.
- Каждый дочерний узел листа дерева считается черным.
Вращения
Чтобы поддерживать левосторонние красно-черные двоичные деревья поиска необходимо соблюдать следующие инварианты при вставке и удалении:
- Ни один путь от корня до листьев дерева не содержит двух последовательных красных узлов.
- Количество черных узлов на каждом таком пути одинаково.
Основные операции, используемые алгоритмами сбалансированного дерева для поддержания баланса при вставке и удалении, называются вращением вправо и вращением влево.Первая операция трансформируют -узел, левый потомок которого окрашен в красный, в -узел, правый потомок которого окрашен в красный,вторая операция — наоборот. Вращения сохраняют два указанных выше инварианта, не изменяют поддеревья узла.
Псевдокод
Node rotateRight(h : Node)
x = h.left
h.left = x.right
x.right = h
x.color = h.color
h.color = RED
return x
Node rotateLeft(h : Node)
x = h.right
h.right = x.left
x.left = h
x.color = h.color
h.color = RED
return x
Переворот цветов
В красно-черных деревьях используется такая операция как переворот цветов , которая инвертирует цвет узла и двух его детей. Она не изменяет количество черных узлов на любом пути от корня до листа, но может привести к появлению двух последовательных красных узлов.
Псевдокод
void flipColors(h : Node h)
h.color = ! h.color
h.left.color = ! h.left.color
h.right.color = ! h.right.color
Вставка
Вставка в ЛСКЧД базируется на простых операциях:
- Вставка нового узла к листу дерева:
Если высота узла нулевая, возвращаем новый красный узел.
- Расщепление узла с -я потомками:
Если левый предок и правый предок красные, запускаем переворот цветов от текущего узла.
- Принудительное вращение влево:
Если правый предок красный, вращаем текущую вершину влево.
- Балансировка узла с -я потомками:
Если левый предок красный и левый предок левого предка красный, то вращаем текущую вершину вправо.
Псевдокод
void insert(key : Key, value : Value )
root = insert(root, key, value)
root.color = BLACK
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)
// Стандартная вставка в дереве поиска
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)
// Принудительное вращение влево
if isRed(h.right) && !isRed(h.left)
h = rotateLeft(h)
// Балансировка узла с -я потомками
if isRed(h.left) && isRed(h.left.left)
h = rotateRight(h)
return h
Поиск
Поиск в левосторонних красно-черных деревьях эквивалентен поиску в наивной реализации дерева поиска. Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы , где — высота дерева.
Псевдокод
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
Исправление правых красных связей
- Использование Переворота цветов и вращений сохраняет баланс черной связи.
- После удаления необходимо исправить правые красные связи и устранить узлы с -я потомками
// Исправление правых красных связей Node fixUp(h : Node) if isRed(h.right) h = rotateLeft(h) // Вращение -ой красной пары пары if isRed(h.left) && isRed(h.left.left) h = rotateRight(h) // Балансировка узла с -я потомками if isRed(h.left) && isRed(h.right) colorFlip(h) return h
Удаление максимума
- Спускаемся вниз по правому краю дерева.
- Если поиск заканчивается на узле с -мя или -ю потомками, просто удаляем узел.
- Удаление узла с -я потомками нарушает баланс
Соответственно, спускаясь вниз по дереву необходимо поддерживать следующий инвариант : количество потомков узла не должно быть ровно -м.
Будем поддерживать инвариант: для любого узла либо сам узел, либо правый предок узла красный. Будем придерживаться тактики , что удалять лист легче, чем внутренний узел.
Заметим, что если правый потомок вершины и правый потомок правого потомка вершины черные, необходимо переместить левую красную ссылку вправо для сохранения инварианта.
Псевдокод
void deleteMax()
root = deleteMax(root)
root.color = BLACK
Node moveRedLeft(h : Node)
colorFlip(h)
if isRed(h.right.left
h.right = rotateRight(h.right)
h = rotateLeft(h)
colorFlip(h)
return h
Node deleteMax(h : Node)
if isRed(h.left)
// вращаем все 3-вершины вправо
h = rotateRight(h)
// поддерживаем инвариант (h должен быть красным)
if h.right == null
return null
// заимствуем у брата если необходимо
if !isRed(h.right) && !isRed(h.right.left)
h = moveRedRight(h)
// опускаемся на один уровень глубже
h.left = deleteMax(h.left)
// исправление правых красных ссылок и 4-вершин на пути вверх
return fixUp(h)
Удаление минимума
Поддерживаем инвариант: вершина или левый ребенок вершины красный.
Заметим, что если левый потомок вершины и левый потомок левого потомка вершины черные, необходимо переместить красную ссылку для сохранения инварианта.
Псевдокод
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()
root = deleteMin(root)
root.color = BLACK
Node deleteMin(h : Node)
// удаляем узел на нижнем уровне(h должен быть красным по инварианту)
if h.left == null
return null
// Если необходимо, пропушим красную ссылку вниз
if (!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h)
// опускаемся на уровень ниже
h.left = deleteMin(h.left)
return fixUp(h)
Асимптотика
Асимптотика методов в левосторонних красно-черных деревьях эквивалентна асимптотике базовой реализации красно-черных деревьях.
См.также
Источники информации
- Robert Sedgewick "Left-leaning Red-Black Trees" ,Department of Computer Science, Princeton University
