Lucian Gabriel Popescu Lucian Gabriel Popescu - 3 months ago 13
C++ Question

Red Black Tree deletion algorithm (CLR 3rd edition)

I'm trying to implement a Red-Black-Tree using algorithms provided by CLR Introduction to Algorithms 3rd edition. Everything worked fine until I've tested deletion: there seems to be a bug in the algorithm. I could find no solution on the net: every other solution (based on 2nd edition algorithm) also fails on closer inspection.

Algorithms can be viewed here:

Red-Black-Tree: Introduction to Algorithms (3rd edition)

Not working algorithm:

RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.right
RB-TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
x = z.left
RB-TRANSPLANT(T, z, z.left)
else
y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y
else // ISSUE
RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)


When execution enters area marked as "ISSUE" above, it produces a cyclic loop: right child ultimately becomes same as its parent (as prints to STDOUT show).

Full code:

#include <vector>

template<typename T>
struct comparator {
int operator()(T& left, T& right) const {
return 0;
}
};

template<>
struct comparator<long> {
int operator()(const long& left, const long& right) const {
if(left<right) return -1;
else if (left>right) return 1;
else return 0;
}
};

template<typename _KEY, typename _VALUE>
struct MapEntry {
_KEY key;
_VALUE value;
};
enum TreeMapEntryColor { RED, BLACK };

template<typename _KEY, typename _VALUE>
struct TreeMapEntry {
MapEntry<_KEY,_VALUE> data;
TreeMapEntry<_KEY,_VALUE>* left;
TreeMapEntry<_KEY,_VALUE>* right;
TreeMapEntry<_KEY,_VALUE>* parent;
TreeMapEntryColor color;
};


template<typename _KEY, typename _VALUE>
class TreeMap {
public:
TreeMap() {
nil = new TreeMapEntry<_KEY,_VALUE>;
nil->color = BLACK;
nil->left = nil->right = nil->parent = nil;

root = nil;
}

void set(const _KEY& key, const _VALUE& value) {
TreeMapEntry<_KEY,_VALUE>* y = nil;
TreeMapEntry<_KEY,_VALUE>* x = root;
while(x!=nil) {
y = x;
int comparison = keyComparator(key, x->data.key);
if(comparison<0) {
x = x->left;
} else if(comparison==0) {
x->data.value = value;
return;
} else {
x = x->right;
}
}
TreeMapEntry<_KEY,_VALUE>* z = new TreeMapEntry<_KEY,_VALUE>;
z->data.key = key;
z->data.value = value;
z->parent = y;
if(y==nil) {
root = z;
} else if(keyComparator(key, y->data.key)<0) {
y->left = z;
} else {
y->right = z;
}
z->left = nil;
z->right = nil;
z->color = RED;
insertFixup(z);
}

void removeKey(const _KEY& key) {
TreeMapEntry<_KEY,_VALUE>* foundElement = nullptr;
TreeMapEntry<_KEY,_VALUE>* x = root;
while(x!=nil) {
int comparison = keyComparator(key, x->data.key);
if(comparison<0) {
x = x->left;
} else if(comparison==0) {
foundElement = x;
break;
} else {
x = x->right;
}
}

if(foundElement!=nullptr) {
deleteNode(foundElement);
}
}

void show() {
show(root);
}


~TreeMap() {
clear(root);
delete nil;
}
private:
void show(TreeMapEntry<_KEY,_VALUE>* const& h) {
std::cout << "Element: " << h->data.key << " Color: " << h->color << std::endl;
if(h->left!=nil) std::cout <<"Left: " << h->left->data.key << std::endl;
if(h->right!=nil) std::cout <<"Right: " << h->right->data.key << std::endl;
if(h->left!=nil) {
show(h->left);
}
if(h->right!=nil) {
show(h->right);
}
}

void clear(TreeMapEntry<_KEY,_VALUE>* const& h) {
if(h==nil) return;
clear(h->left);
clear(h->right);
delete h;
}

void deleteNode(TreeMapEntry<_KEY,_VALUE>*& z) {
TreeMapEntry<_KEY,_VALUE>* x = nil;
TreeMapEntry<_KEY,_VALUE>* y = z;
TreeMapEntryColor yOriginalColor = y->color;
if(z->left == nil) { // ok
x = z->right;
transplant(z, z->right);
} else if (z->right == nil) {
x = z->left;
transplant(z, z->left);
} else {
y = min(z->right);
yOriginalColor = y->color;
x = y->right;
if(y->parent == z) { // ok
x->parent = y;
} else {
// FIXME
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
transplant(y, y->right);
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
std::cout << __LINE__ << "#" << z->parent->data.key << ":" << z->data.key << ":" << z->left->data.key << ":" << z->right->data.key << std::endl;
y->right = z->right;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->right->parent = y;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
}
transplant(z, y);
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->left = z->left;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->left->parent = y;
std::cout << __LINE__ << "#" << y->parent->data.key << ":" << y->data.key << ":" << y->left->data.key << ":" << y->right->data.key << std::endl;
y->color = z->color;
}
delete z;
if(yOriginalColor == BLACK) {
deleteFixup(x);
}
}

void leftRotate(TreeMapEntry<_KEY,_VALUE>* x) {
TreeMapEntry<_KEY,_VALUE>* y = x->right;
x->right = y->left;
if (y->left != nil) {
y->left->parent=x;
}
y->parent=x->parent;
if(x->parent == nil) {
root=y;
} else if (x == x->parent->left) {
x->parent->left=y;
} else {
x->parent->right=y;
}
y->left=x;
x->parent=y;
}

void rightRotate(TreeMapEntry<_KEY,_VALUE>* x) {
TreeMapEntry<_KEY,_VALUE>* y = x->left;
x->left = y->right;
if (y->right != nil) {
y->right->parent=x;
}
y->parent=x->parent;
if(x->parent == nil) {
root=y;
} else if (x == x->parent->right) {
x->parent->right=y;
} else {
x->parent->left=y;
}
y->right=x;
x->parent=y;
}

void insertFixup(TreeMapEntry<_KEY,_VALUE>*& z) {
TreeMapEntry<_KEY,_VALUE>* y = nullptr;
while(z!=root && z->parent->color == RED) {
if(z->parent == z->parent->parent->left) {
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;
leftRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rightRotate(z->parent->parent);
}
} else {
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;
rightRotate(z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
leftRotate(z->parent->parent);
}
}
}
root->color = BLACK;
}

void transplant(TreeMapEntry<_KEY,_VALUE>*& u, TreeMapEntry<_KEY,_VALUE>*& v) {
if(u->parent == nil) {
root = v;
} else if(u==u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
v->parent = u->parent;
}

TreeMapEntry<_KEY,_VALUE>*& min(TreeMapEntry<_KEY,_VALUE>*& x) {
while(x->left != nil) {
x = x->left;
}
return x;
}

void deleteFixup(TreeMapEntry<_KEY,_VALUE>*& x) {
TreeMapEntry<_KEY,_VALUE>* w = nullptr;
while(x!=root && x->color == BLACK) {
if(x == x->parent->left) {
w = x->parent->right;
if(w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
leftRotate(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;
rightRotate(w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
leftRotate(x->parent);
x = root;
}
} else {
w = x->parent->left;
if(w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rightRotate(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;
leftRotate(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}

comparator<_KEY> keyComparator;
comparator<_VALUE> valueComparator;
TreeMapEntry<_KEY,_VALUE>* root;
TreeMapEntry<_KEY,_VALUE>* nil;
};


Test for cyclic loop:

int main() {
TreeMap<long,long> tm;
tm.set(5,5);
tm.set(1,1);
tm.set(3,3);
tm.set(4,4);
tm.set(2,2);
tm.set(6,6);
tm.set(9,9);
tm.set(7,7);
tm.set(8,8);
// tm.removeKey(9); WORKS!
// tm.removeKey(7); DOESN'T WORK
tm.removeKey(5); // ROOT
tm.show();
std::cout << "OK" << std::endl;
return 0;
}


Is there anyone who cracked this issue?

Answer

Your translation to C++ is wrong.

You changed the function call semantics almost everywhere from pass-by-value to pass-by-reference.
This is not a semantics-preserving change.
(CLR never uses pass-by-reference.)

In particular, min – which is only supposed to locate a specific node – ends up pointing its parameter to that node.

Passing and returning all the pointers by value instead of by reference makes your bug disappear.