Реализация красно-черного дерева в Go. Часть 2: Операция удаления
1 ноября 2023 г.Мы разобрались, как работает операция поиска и вставки в красно-черном дереве в файле первая часть. В этой части мы разберемся, как работает операция удаления. Операция удаления более сложна, чем операция вставки.
Операция удаления
Операция удаления, как и операция вставки, обеспечивает временную сложность O(log(n)). Во-первых, мы должны реализовать вспомогательный метод трансплантации, который пересаживает узел y на место узла x.
func (tree *Tree[K, V]) transplant(x *TreeNode[K, V], y *TreeNode[K, V]) {
if x.parent == tree.leaf {
tree.root = y
} else if x == x.parent.left {
x.parent.left = y
} else {
x.parent.right = y
}
y.parent = x.parent
}
Операция удаления аналогична операции удаления в дереве двоичного поиска, но имеет несколько отличий. Мы должны сохранить исходный цвет удаленного узла. Если удаленный узел красный, мы не нарушаем никаких свойств красно-черного дерева, но если удаленный узел черный, мы можем нарушить красно-черные свойства.
- Мы можем нарушить первое свойство: корень черный, если пересаженный узел красный, а удаленный узел черный.
2. Мы можем нарушить третье свойство: не может быть двух соседних красных узлов, если родитель удаленного узла красный, а пересаженный узел красный.
3. Мы нарушим пятое свойство: иметь одинаковое количество черных узлов от корня до каждого листа.
Нам необходимо запустить вспомогательный метод для восстановления красно-черных свойств.
Алгоритм удаления узла в красно-черном дереве следующий. n n 1. Нам нужно объявить переменную, в которой будет храниться цвет удаляемого узла.
2. Если у узла нет дочерних элементов или только один дочерний узел, мы можем пересадить этот узел или лист в случае, если у узла нет дочерних элементов, в удаляемый узел. Если цвет удаляемого узла черный, нам нужно запустить вспомогательный метод deleteFixup.
3. Если удаляемый узел имеет двух детей, необходимо найти наследника этого узла. Преемником узла является крайний левый узел его правого дочернего элемента. Крайне важно сохранить цвет потомка в переменную, так как после трансплантации там могут быть нарушения.
Если преемник не является правым дочерним элементом удаляемого узла, нам необходимо пересадить правое поддерево преемника преемнику. Затем мы должны пересадить преемника в удаляемый узел и установить цвет удаляемого узла.
Затем мы должны запустить метод deleteFixup, если это необходимо.
func (tree *Tree[K, V]) Delete(key K) {
x := tree.lookup(key)
if x == tree.leaf {
return
}
var y *TreeNode[K, V]
originalColor := x.color
if x.left == tree.leaf {
y = x.right
tree.transplant(x, x.right)
} else if x.right == tree.leaf {
y = x.left
tree.transplant(x, x.left)
} else {
successor := tree.leftmost(x.right)
originalColor = successor.color
y = successor.right
if successor != x.right {
tree.transplant(successor, successor.right)
successor.right = x.right
successor.right.parent = successor
} else {
y.parent = successor
}
tree.transplant(x, successor)
successor.left = x.left
successor.left.parent = successor
successor.color = x.color
}
tree.len--
if originalColor == black {
tree.deleteFixup(y)
}
}
4 случая используются для перебалансировки красно-черного дерева после удаления узла.
-
<ли>
Первый случай возникает, когда родственный узел узла красный. Мы должны поменять цвет родительского узла текущего узла и родственного узла текущего узла и повернуть родительский узел влево, если узел принадлежит левому поддереву, или повернуть вправо, если узел принадлежит правому поддереву, а затем обновить родственный узел. .
2. Второй случай имеет место, когда дети обоих братьев и сестер имеют черный цвет. Брат тоже черный. Мы должны изменить цвет родственного узла на красный и покинуть текущий узел. Если родительский узел красный, цикл завершается.
3. Случай 3 имеет место, когда и брат, и его правый дочерний элемент имеют черный цвет, а левый дочерний элемент имеет красный цвет. Необходимо поменять цвета левого дочернего элемента и родственного узла и повернуть его вправо, если узел принадлежит левому поддереву, и повернуть влево, если узел принадлежит правому поддереву, и обновить одноуровневый узел. Тогда мы переходим к четвертому случаю.
4. Случай 4 имеет место, когда правый дочерний элемент брата/сестры красный, а брат/сестра имеет чёрный цвет. Мы должны изменить цвет правого дочернего элемента родственного узла на черный, а также изменить цвет родителя текущего узла на черный.
Затем мы должны повернуть родителя узла влево, если узел принадлежит левому поддереву, или повернуть вправо, если узел принадлежит правому поддереву. Затем мы устанавливаем текущий узел в качестве корневого дерева.
func (tree *Tree[K, V]) deleteFixup(x *TreeNode[K, V]) {
for x != tree.root && x.color == black {
if x == x.parent.left {
y := x.parent.right
if y.color == red {
y.color = black
x.parent.color = red
tree.leftRotate(x.parent)
y = x.parent.right
}
if y.left.color == black && y.right.color == black {
y.color = red
x = x.parent
} else {
if y.right.color == black {
y.left.color = black
y.color = red
tree.rightRotate(y)
y = x.parent.right
}
y.color = x.parent.color
x.parent.color = black
y.right.color = black
tree.leftRotate(x.parent)
x = tree.root
}
} else {
y := x.parent.left
if y.color == red {
y.color = black
x.parent.color = red
tree.rightRotate(x.parent)
y = x.parent.left
}
if y.left.color == black && y.right.color == black {
y.color = red
x = x.parent
} else {
if y.left.color == black {
y.right.color = black
y.color = red
tree.leftRotate(y)
y = x.parent.left
}
y.color = x.parent.color
x.parent.color = black
x.left.color = black
tree.rightRotate(x.parent)
x = tree.root
}
}
}
tree.root.color = black
}
Надеюсь, теперь стало более понятно, как работает удаление узлов в красно-черном дереве.
Оригинал