Red Black Tree deletion algorithm
From "Introduction to Algorithms 2nd edition" I got this deletion algorithm:
/*
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y != z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y
*/
Now few problems with this algorithm, one main problem is that if you try to build tree ( you can do it here) with nodes 1,2,3,4,5,6 (placed in this order), and then delete node 2, lines 4,5 and 6 of this algorithm returns nullptr (x == nullptr). Can anyone help me with this?
Here are the helper algorithms (from same book):
TREE-SUCCESSOR(x)
1 if right[x] ≠ NIL
2 then return TREE-MINIMUM (right[x])
3 y ← p[x]
4 while y ≠ NIL and x = right[y]
5 do x ← y
6 y ← p[y]
7 return y
TREE-MINIMUM (x)
1 while left[x] ≠ NIL
2 do x ← left[x]
3 return x
RB-DELETE-FIXUP(T, x)
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED
5 then color[w] ← BLACK ▹ Case 1
6 color[p[x]] ← RED ▹ Case 1
7 LEFT-ROTATE(T, p[x]) ▹ Case 1
8 w ← right[p[x]] ▹ Case 1
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 2
11 x p[x] ▹ Case 2
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ▹ Case 3
14 color[w] ← RED ▹ Case 3
15 RIGHT-ROTATE(T, w) ▹ Case 3
16 w ← right[p[x]] ▹ Case 3
17 color[w] ← color[p[x]] ▹ Case 4
18 color[p[x]] ← BLACK ▹ Case 4
19 color[right[w]] ← BLACK ▹ Case 4
20 LEFT-ROTATE(T, p[x]) ▹ Case 4
21 x ← root[T] ▹ Case 4
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK
LEFT-ROTATE(T, x)
1 y ← right[x] ▹ Set y.
2 right[x] ← left[y] ▹ Turn y's left subtree into x's right subtree.
3 p[left[y]] ← x
4 p[y] ← p[x] ▹ Link x's parent to y.
5 if p[x] = nil[T]
6 then root[T] ← y
7 else if x = left[p[x]]
8 then left[p[x]] ← y
9 else right[p[x]] ← y
10 left[y] ← x ▹ Put x on y's left.
11 p[x] ← y
RB-INSERT(T, z)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ▹ Case 1
6 color[y] ← BLACK ▹ Case 1
7 color[p[p[z]]] ← RED ▹ Case 1
8 z ← p[p[z]] ▹ Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ▹ Case 2
11 LEFT-ROTATE(T, z) ▹ Case 2
12 color[p[z]] ← BLACK ▹ Case 3
13 color[p[p[z]]] ← RED ▹ Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ▹ Case 3
15 else (same as then clause
with "right" and "left" exchanged)
16 color[root[T]] ← BLACK
IMPLEMENTATION
enum Color {Black,Red};
template<class Key>
struct Node
{
Key* key_;
Color color_;
Node* parent_;
Node* left_;
Node* right_;
Node(Key k,Node* parent = nullptr, Node* left = nullptr,Node* right = nullptr):key_(new Key[2]),
color_(Red),
parent_(parent),
left_(left),
right_(right)
{
key_[0] = k;
key_[1] = '\0';
}
};
template<class Key>
class Tree
{
Node<Key>* head_;
typedef Key* key_pointer;
typedef Node<Key>* pointer;
typedef Node<Key> value_type;
public:
Tree(Key k):head_(new value_type(k))
{
head_->color_ = Black;
}
~Tree()
{
delete head_;
}
pointer root()const
{
auto root = head_;
while (root->parent_)
{
root = root->parent_;
}
return root;
}
void root(pointer root)
{
head_ = root;
}
pointer parent()const
{
return head_->parent_;
}
void parent(pointer parent)
{
head_->parent_ = parent;
}
pointer left()const
{
return head_->left_;
}
void left(pointer left)
{
head_->left_ = left;
}
pointer right()const
{
return head_->right_;
}
void right(pointer right)
{
head_->right_ = right;
}
key_pointer key()const
{
return head_->key_;
}
};
template<class Tree,class Node>
void left_rotate(Tree* t, Node* x)
{
auto y = x->right_;
x->right_ = y->left_;
if (y->left_)
{
y->left_->parent_ = x;
}
y->parent_ = x->parent_;
if (!x->parent_)
{
t->root(y);
}
else if(x == x->parent_->left_)
{
x->parent_->left_ = y;
}
else
{
x->parent_->right_ = y;
}
y->left_ = x;
x->parent_ = y;
}
template<class Tree,class Node>
void right_rotate(Tree* t, Node* x)
{
auto y = x->left_;
x->left_ = y->right_;
if (y->right_)
{
y->right_->parent_ = x;
}
y->parent_ = x->parent_;
if (!x->parent_)
{
t->root(y);
}
else if(x == x->parent_->right_)
{
x->parent_->right_ = y;
}
else
{
x->parent_->left_ = y;
}
y->right_ = x;
x->parent_ = y;
}
template<class Tree, class Node_Value>
void insert(Tree* t, Node_Value n)
{
auto z = make_node(n);
auto x = t->root();
decltype(z) y = nullptr;
while(x)
{
y = x;
if (*z->key_ < *x->key_)
{
x = x->left_;
}
else
{
x = x->right_;
}
}
z->parent_ = y;
if (!y)
{
t->root(z);
}
else
{
if (*z->key_ < *y->key_)
{
y->left_ = z;
}
else
{
y->right_ = z;
}
}
z->left_ = nullptr;
z->right_ = nullptr;
z->color_ = Red;
insert_fix_up(t,z);
}
template<class Tree, class Node>
void insert_fix_up(Tree* t, Node* z)
{
while (z->parent_->color_ == Red)
{
if (z->parent_ == z->parent_->parent_->left_)
{
auto y = z->parent_->parent_->right_;
if (y->color_ == Red)
{
z->parent_->color_ = Black;
y->color_ = Black;
z->parent_->parent_->color_ = Red;
z = z->parent_->parent_;
}
else if(z == z->parent_->right_)
{
z = z->parent_;
left_rotate(t,z);
}
z->parent_->color_ = Black;
z->parent_->parent_->color_ = Red;
right_rotate(t,z->parent_->parent_);
}
else
{
auto y = z->parent_->parent_->left_;
if (y->color_ == Red)
{
z->parent_->color_ = Black;
y->color_ = Black;
z->parent_->parent_->color_ = Red;
z = z->parent_->parent_;
}
else if(z == z->parent_->left_)
{
z = z->parent_;
right_rotate(t,z);
}
z->parent_->color_ = Black;
z->parent_->parent_->color_ = Red;
left_rotate(t,z->parent_->parent_);
}
}
t->root()->color_ = Black;
}
template<class Node>
Node* tree_minimum(Node* x)
{
while (x->left_)
{
x = x->left_;
}
return x;
}
template<class Node>
Node* tree_successor(Node* x)
{
if (x->right_)
{
return tree_minimum(x->right_);
}
auto y = x->parent_;
while (y && x == y->right_)
{
x = y;
y = y->parent_;
}
return y;
}
template<class Tree, class Node>
Node* rb_delete(Tree* t,Node* z)
{
Node* x = nullptr;
Node* y = nullptr;
if (!z->left_ || !z->right_)
{
y = z;
}
else
{
y = tree_successor(z);
}
if (y->left_)
{
x = y->left_;
}
else
{
x = y->right_;
}
x->parent_ = y->parent_;
if (!y->parent_)
{
t->root(x);
}
else if (y == y->parent_->left_)
{
y->parent_->left_ = x;
}
else
{
y->parent_->right_ = x;
}
if (y != z)
{
z->key_ = y->key_;
}
if (y->color_ = Black)
{
rb_delete_fix_up(t,x);
}
return y;
}
template<class Tree, class Node>
void rb_delete_fix_up(Tree*& t,Node*& x)
{
while (x != t->root() && x->color_ == Black)
{
Node* w = nullptr;
if (x == x->parent_->left_)
{
w = x->parent_->right_;
if (w->color_ == Red)
{
w->color_ = Black;
x->parent_->color_ = Red;
left_rotate(t,x->parent_);
w = x->parent_->right_;
}
if (w->left_->color_ == Black && w->right_->color_ == Black)
{
w->color_ = Red;
x = x->parent_;
}
else if(w->right_->color_ == Black)
{
w->left_->color_ = Black;
w->color_ = Red;
right_rotate(t,w);
w = x->parent_->right_;
}
w->color_ = x->parent_->color_;
x->parent_->color_ = Black;
w->right_->color_ = Black;
left_rotate(t,x->parent_);
x = t->root();
}
else
{
w = x->parent_->left_;
if (w->color_ == Red)
{
w->color_ = Black;
x->parent_->color_ = Red;
right_rotate(t,x->parent_);
w = x->parent_->left_;
}
if (w->right_->color_ == Black && w->left_->color_ == Black)
{
w->color_ = Red;
x = x->parent_;
}
else if(w->left_->color_ == Black)
{
w->right_->color_ = Black;
w->color_ = Red;
left_rotate(t,w);
w = x->parent_->left_;
}
w->color_ = x->parent_->color_;
x->parent_->color_ = Black;
w->left_->color_ = Black;
right_rotate(t,x->parent_);
x = t->root();
}
}
x->color_ = Black;
}
template<class Key>
Node<Key>* make_node(Key k)
{
return new Node<Key>(k);
}
int _tmain(int argc, _TCHAR* argv[])
{
auto t = new Tree<int>(1);
insert(t,2);
insert(t,3);
insert(t,4);
insert(t,5);
insert(t,6);
rb_delete(t,t->left());
return 0;
}
Answer
For a version of rb-tree without sentinels the delete operation implementation is as follows:
SWRedBlackNode delete(SWRedBlackTree tree, SWRedBlackNode node) {
SWRedBlackNode y;
if (node._left == null || node._right == null) {
y = node;
} else {
y = node.getSuccessor();
}
SWRedBlackNode x;
if (y._left != null) {
x = y._left;
} else {
x = y._right;
}
if (x != null) {
x._parent = y._parent;
}
SWRedBlackNode xParent = y._parent;
boolean yIsLeft = false;
if (y._parent == null) {
tree._root = x;
} else if (y == y._parent._left) {
y._parent._left = x;
yIsLeft = true;
} else {
y._parent._right = x;
yIsLeft = false;
}
if (y != node) {
node._value = y._value;
}
if (!y._isRed) {
deleteFixUp(tree, x, xParent, yIsLeft);
}
return y;
}
private void deleteFixUp(SWRedBlackTree tree, SWRedBlackNode node, SWRedBlackNode nodeParent, boolean nodeIsLeft) {
while (node != tree._root && isBlack(node)) {
SWRedBlackNode w;
if (nodeIsLeft) {
w = nodeParent._right;
if (isRed(w)) {
w._isRed = false;
nodeParent._isRed = true;
leftRotate(tree, nodeParent);
w = nodeParent._right;
}
if (isBlack(w._left) && isBlack(w._right)) {
w._isRed = true;
node = nodeParent;
nodeParent = node._parent;
nodeIsLeft = (node == nodeParent._left);
} else {
if (isBlack(w._right)) {
w._left._isRed = false;
w._isRed = true;
rightRotate(tree, w);
w = nodeParent._right;
}
w._isRed = nodeParent._isRed;
nodeParent._isRed = false;
if (w._right != null) {
w._right._isRed = false;
}
leftRotate(tree, nodeParent);
node = tree._root;
nodeParent = null;
}
} else { /* nodeIsLeft == false */
w = nodeParent._left;
if (isRed(w)) {
w._isRed = false;
nodeParent._isRed = true;
rightRotate(tree, nodeParent);
w = nodeParent._left;
}
if (isBlack(w._right) && isBlack(w._left)) {
w._isRed = true;
node = nodeParent;
nodeParent = node._parent;
nodeIsLeft = (node == nodeParent._left);
} else {
if (isBlack(w._left)) {
w._right._isRed = false;
w._isRed = true;
leftRotate(tree, w);
w = nodeParent._left;
}
w._isRed = nodeParent._isRed;
nodeParent._isRed = false;
if (w._left != null) {
w._left._isRed = false;
}
rightRotate(tree, nodeParent);
node = tree._root;
nodeParent = null;
}
}
}
node._isRed = false;
}
It's in Java but can easily be ported to any language.
The following code is different in respect to your implementation:
Nesting here:
} else {
if (isBlack(w._right)) {
and here:
} else {
if (isBlack(w._left)) {
Without-sentinel stuff here:
if (x != null) {
x._parent = y._parent;
}
SWRedBlackNode xParent = y._parent;
boolean yIsLeft = false;
if (y._parent == null) {
tree._root = x;
} else if (y == y._parent._left) {
y._parent._left = x;
yIsLeft = true;
} else {
y._parent._right = x;
yIsLeft = false;
}
then here:
deleteFixUp(tree, x, xParent, yIsLeft);
and in deleteFixUp() - just look for usage of nodeParent and nodeIsLeft, and finally at this place:
if (w._right != null) {
w._right._isRed = false;
}
and this:
if (w._left != null) {
w._left._isRed = false;
}