Red Black Tree in C++ adopted by Arkadi Kagan
id:studiokingyo:20050321のC++版デースケドガー
http://sourceforge.net/projects/compressions/
で、ダウンロードできるredblack.tに入っていたのデースケドガー
License: Academic Free License (AFL), Common Public License, GNU General Public License (GPL), GNU Library or Lesser General Public License (LGPL), Open Software License
だそうデースケドガー
// The RedBlack tree code was taken from free source in C language.
// Unfortunately I lost the author`s name :(
//
// The code adopted to project and turned into C++ template
// by Arkadi Kagan.
//
#ifndef __REDBLACK_H
#define __REDBLACK_Htemplate <class T>
class TRedBlack
{
private:
// Red-Black tree description
typedef enum { BLACK, RED } nodeColor;
public:
struct Node
{
Node *left; // left child
Node *right; // right child
Node *parent; // parent
nodeColor color; // node color (BLACK, RED)
T data; // data stored in node
};
Node sentinel;
Node *root; // root of Red-Black tree
Node *NIL;
public:
TRedBlack()
: NIL(&sentinel)
{
sentinel.left = NIL;
sentinel.right = NIL;
sentinel.parent = 0;
sentinel.color = BLACK;
sentinel.data = 0;
root = NIL;
}
~TRedBlack()
{
}
private:
////////////////////////////
// rotate node x to left //
////////////////////////////
void rotateLeft(Node *x)
{Node *y = x->right;
// establish x->right link
x->right = y->left;
if (y->left != NIL) y->left->parent = x;// establish y->parent link
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}// link x and y
y->left = x;
if (x != NIL) x->parent = y;
}void rotateRight(Node *x)
{
//////////////////////////////
// rotate node x to right //
//////////////////////////////Node *y = x->left;
// establish x->left link
x->left = y->right;
if (y->right != NIL) y->right->parent = x;// establish y->parent link
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}// link x and y
y->right = x;
if (x != NIL) x->parent = y;
}void insertFixup(Node *x)
{
///////////////////////////////////////
// maintain Red-Black tree balance //
// after inserting node x //
///////////////////////////////////////// check Red-Black properties
while (x != root && x->parent->color == RED) {
// we have a violation
if (x->parent == x->parent->parent->left) {
Node *y = x->parent->parent->right;
if (y->color == RED) {// uncle is RED
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {// uncle is BLACK
if (x == x->parent->right) {
// make x a left child
x = x->parent;
rotateLeft(x);
}// recolor and rotate
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {// mirror image of above code
Node *y = x->parent->parent->left;
if (y->color == RED) {// uncle is RED
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {// uncle is BLACK
if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}
public:
Node *insertNode(T data)
{
Node *current, *parent, *x;/////////////////////////////////////////////////
// allocate node for data and insert in tree //
/////////////////////////////////////////////////// find where node belongs
current = root;
parent = 0;
while (current != NIL) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data) ?
current->left : current->right;
}// setup new node
if ((x = new Node) == 0)
FatalError ("insufficient memory (insertNode)\n");
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;// insert node in tree
if(parent) {
if(compLT(data, parent->data))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}insertFixup(x);
return(x);
}void deleteFixup(Node *x)
{
///////////////////////////////////////
// maintain Red-Black tree balance //
// after deleting node x //
///////////////////////////////////////while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateLeft (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;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
} else {
Node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (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;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
}void deleteNode(Node *z)
{
///////////////////////////////
// delete node z from tree //
///////////////////////////////
Node *x, *y;
if (!z || z == NIL) return;if (z->left == NIL || z->right == NIL) {
// y has a NIL node as a child
y = z;
} else {
// find tree successor with a NIL node as a child
y = z->right;
while (y->left != NIL) y = y->left;
}// x is y's only child
if (y->left != NIL)
x = y->left;
else
x = y->right;// remove y from the parent chain
x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;if (y != z) z->data = y->data;
if (y->color == BLACK)
deleteFixup (x);delete y;
}Node *findNode(T data)
{
/////////////////////////////////
// find node containing data //
/////////////////////////////////Node *current = root;
while(current != NIL)
if(compEQ(data, current->data))
return (current);
else
current = compLT (data, current->data) ?
current->left : current->right;
return(0);
}
};#endif
