Левосторонние красно-чёрные деревья — различия между версиями
(→Удаление) |
(→Удаление минимума) |
||
| Строка 187: | Строка 187: | ||
h = rotateLeft(h) | h = rotateLeft(h) | ||
colorFlip(h) | colorFlip(h) | ||
| − | + | '''return''' ''h'' | |
'''void''' deleteMin() | '''void''' deleteMin() | ||
| Строка 202: | Строка 202: | ||
<span style="color:#008000">// опускаемся на уровень ниже </span> | <span style="color:#008000">// опускаемся на уровень ниже </span> | ||
h.left = deleteMin(h.left) | h.left = deleteMin(h.left) | ||
| − | + | '''return''' fixUp(h) | |
==Асимптотика== | ==Асимптотика== | ||
Версия 15:46, 18 июня 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
Вставка
Вставка в ЛСКЧД базируется на простых операциях:
- Вставка нового узла к листу дерева:
Если высота узла нулевая, возвращаем новый красный узел.
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)
Псевдокод
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)
// Стандартная вставка в дереве поиска
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
Поиск
Поиск в левосторонних красно-черных деревьях эквивалентен поиску в наивной реализации дерева поиска. Для поиска элемента в красно-черных деревьях дереве поиска можно воспользоваться циклом,который проходит от корня до искомого элемента. Если же элемент отсутствует, цикл пройдет до листа дерева и прервется. Для каждого узла цикл сравнивает значение его ключа с искомым ключом. Если ключи одинаковы, то функция возвращает текущий узел, в противном случае цикл повторяет для левого или правого поддерева. Узлы, которые посещает функция образуют нисходящий путь от корня, так что время ее работы , где — высота дерева.
Псевдокод
Value search(key : Key)
Node x = root
while (x != null)
int cmp = key.compareTo(x.key)
if cmp == 0
return x.val
else
if cmp < 0
x = x.left
else
if cmp > 0
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
