www.pudn.com > Compression.rar > redblack.t

// 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_H

template 
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