/* You can use this code to your hearts content as long as
you leave this notice in your source code */
// *************************************
// ** Green Black Tree by Satin Hinge **
// *************************************
/*
accepts a pointer to the added node and propagates
and cleans up any green violations it might cause
*/
void GreenBlackTree::insertCleanup(BNodeBase *cur)
{
BNodeBase *parent, *gparent;
while ( (cur->color == green) && (cur != root ) ) {
// there's a parent because I added myself to something
parent = cur->parent;
if (parent->color == green) { // case 1: parent green, parent left child green
// if parent green, then it's not the root, so there's a grandparent
gparent = parent->parent;
if (parent->left->color == green) { // if parent is green, the only green left child would be us
parent->color = black;
rotateRight(parent);
rotateLeft(gparent);
// cur stays same
continue;
} else { // Case 2: Parent Green, Parent left child black
//since we're green, we must be right child
cur->color = black;
rotateLeft(gparent);
cur = parent;
continue;
}
} else { // Case 3: Parent Black
// if both children green, we must be left child, cause tree don't have left green children
if ( (parent->left->color == green)
&& (parent->right->color == green)
) {
cur->color = black;
parent->right->color = black;
parent->color = green;
cur = parent;
continue;
} else { // case 4: parent black, only left child green, which is us
if (parent->left->color == green) {
cur->color = black;
parent->color = green;
rotateRight(parent);
// cur stays same
continue;
} else { // only right child must be green
// no violation
break;
}
} // end if parent left green
} // end if parent green
} // endwhile
// The root can't be part of another node, because there are no nodes above it.
// so it's always black
root->color = black;
}
/*
accepts a pointer to the offending double black node and propagates
and cleans up any double black violations it might be causing
*/
void GreenBlackTree::deleteCleanup(BNodeBase *cur )
{
BNodeBase *parent, *sibling, *realsibling;
while ( (cur->color == double_black) && (cur != root ) ) {
// if we're not the root, we have a parent
parent = cur->parent;
if (parent->left == cur) { // we are left child
sibling = parent->right;
if (sibling->color == black) { // right sibling is black
if (sibling->right->color == green) {
// Case 1b: Black right sibling with green right child
cur->color = black;
// preserve local root color
sibling->color = parent->color; //is not null, because had green child
sibling->right->color = black;
parent->color = black;
rotateLeft(parent);
cur = sibling;
continue;
}
else {
// Case 2a: Black right sibling with black right child
cur->color = black;
sibling->color = green;
if (parent->color == green)
parent->color = black;
else
parent->color = double_black;
cur = parent;
continue;
}
} else { // right sibling is green
realsibling = sibling->left;
if (realsibling->right->color == green) {
// Case 3: Black right realsibling with green right child
cur->color = black;
realsibling->right->color = black; //is not null, because it was green
rotateRight(sibling);
rotateLeft(parent);
cur = realsibling;
continue;
}
else {
// Case 4: Black right realsibling with black right child
cur->color = black;
sibling->color = black;
if (!realsibling->isNull())
realsibling->color = green;
rotateLeft(parent);
cur = sibling;
continue;
}
}
} else { // we are right child
sibling = parent->left;
if (sibling->color == black) { // left sibling is black
if (sibling->right->color == green) {
// Case 1a: Black left sibling with green right child
cur->color = black;
// preserve local root color
sibling->right->color = parent->color; //is not null, because it was green
parent->color = black;
rotateLeft(sibling);
rotateRight(parent);
cur = sibling->right;
continue;
}
else {
// Case 2b: Black left sibling with black right child
cur->color = black;
// propagate new local root color based on old local root color
if (!sibling->isNull()) {
if (parent->color == green)
sibling->color = black;
else
sibling->color = double_black;
}
parent->color = green;
rotateRight(parent);
cur = sibling;
continue;
}
} else {} // left sibling is green, never happens
} // end if left or right
} // endwhile
// The root can't owe a debt, because it's not on the left or
// right of anything, it's always balanced, so it's black
root->color = black;
}