问题提出：

1.RedBlack Tree是一种简单的自平衡树。它通过属性约束来实现树的平衡，保证在树上没有一条路是别的路的2倍长。

 2. 它有以下五条属性约束：

1） 每个node是红色或者黑色；

2） 每个叶子node是黑色；

3）根node是黑色；

                4）若一个node是黑色，则它的两个孩子node是红色；

                5)   对每个node，若有从这个node到它的子孙叶子（node）的路上包含有相同数目的黑色节点；

  3. 本文的实现是参考introduction to algorithm 书中的讲述；

  4. 本文和STL map做了简单的性能比较，结果基本上不相上下；

代码如下：

#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_

#include <functional>
#include <algorithm>
#include <map>

/*
* encapsulate red black tree only for challenge self
*
*/

template<class T, class V, class Cmp = std::less<T> > 
class RedBlackTree
{
public:
	enum COLOR
	{
		RED,
		BLACK
	};

	typedef struct tagRedBlackNode
	{
		T    key;
		V    value;
		tagRedBlackNode* parent;
		tagRedBlackNode* leftChild;
		tagRedBlackNode* rightChild;
		COLOR            color;

		tagRedBlackNode():key(), value(), 
			              parent(0), leftChild(0),
						  rightChild(0), color()
		{

		}

		tagRedBlackNode( const T& _key, const T& _value ): key(_key), 
			            value(_value),
						leftChild(0),
						rightChild(0), 
						color(RED)
		{

		}

	}RedBlackNode, *pRedBlackNode;


	/*
	*
	*
	*/
	RedBlackTree():m_root(0), m_size(0)
	{

	}

	
	/*
	* Copy constructor
	*
	*/
	RedBlackTree( const RedBlackTree& rhs )
	{
		m_root = Clone( rhs.m_root );
		m_size = rhs.m_size;
	}


	/*
	*
	*
	*/
	~RedBlackTree()
	{
		Clear();
	}


	/*
	* assignment operator overload
	*
	*/
	RedBlackTree& operator = ( const RedBlackTree& rhs )
	{
		if( this != &rhs )
		{
			Clear();
			m_root = Clone( rhs.m_root );
			m_size = rhs.m_size;
		}

		return *this;
	}

	/*
	*
	*
	*/
	bool IsEmpty() const 
	{
		return Size == 0;
	}

	/*
	* Remove all node 
	*
	*/
	void Clear()
	{
		Clear( m_root );
		m_size = 0;
	}

	/*
	* Retrieve the number of node
	*
	*/
	size_t Size() const 
	{
		return m_size;
	}

	/*
	*
	*
	*/
	void Insert( const T& key, const V& value )
	{
		InsertUtil( key, value );
	}


	/*
	* Find value from tree for given key
	*
	*/
	V* Find( const T& key )
	{
		return Find( m_root, key );
	}

	/*
	* delete node from tree for given key
	*
	*/
	void Delete( const T& key )
	{
		Delete( m_root, key );
	}


	/*
	* Retrieve the element of min
	*
	*/
	V* FindMin( T& key )
	{
		pRedBlackNode node = FindMin( m_root );
		if( node )
		{
			key = node->key;
			return &node->value;
		}

		return 0;
	}


	/*
	* Retrieve the element of max
	*
	*/
	V* FindMax( T& key )
	{
		pRedBlackNode node = FindMax( m_root );
		if( node )
		{
			key = node->key;
			return &node->value;
		}

		return 0;
	}

	size_t GetSize() const 
	{
		return Size( m_root );
	}

protected:

	/*
	* get the number of node by recursive method
	*
	*/
	size_t Size( pRedBlackNode root ) const 
	{
		if( 0 == root )
			return 0;

		return 1 + Size( root->leftChild ) + Size( root->rightChild );
	}

	/*
	* Clone tree
	*
	*/
	pRedBlackNode Clone( pRedBlackNode root )
	{
		if( 0 == root )
			return root;

		pRedBlackNode newNode = new RedBlackNode( root->key, root->value );
		newNode->leftChild = Clone( root->leftChild );
		newNode->rightChild = Clone( root->rightChild );

		if( newNode->leftChild )
			newNode->leftChild->parent = newNode;

		if( newNode->rightChild )
			newNode->rightChild->parent = newNode;

		return newNode;
	}

	/*
	* Clear all elements
	*
	*/
	void Clear( pRedBlackNode& root )
	{
		if( 0 == root )
			return;

		Clear( root->leftChild );
		Clear( root->rightChild );

		delete root;
		root = 0;
	}

	/*
	* Reabalance when complete delete operation
	*
	*/
	void DeleteReablance( pRedBlackNode root )
	{
		if(  0 == root->parent )
			return;

		while( root != m_root && BLACK == root->color )
		{
			if( root == root->parent->leftChild )
			{
				pRedBlackNode y = root->parent->rightChild;
				if( RED == y->color )
				{
					y->color = BLACK;
					root->parent->color = RED;
					LeftRotate( root->parent );
					y = root->parent->rightChild;
				}
				if( y->leftChild && BLACK == y->leftChild->color && y->rightChild && BLACK == y->rightChild->color )
				{
					y->color = RED;
					root = root->parent;
				}
				else
				{
					if( y->rightChild && BLACK == y->rightChild->color )
					{
						y->leftChild->color = BLACK;
						y->color = RED;
						RightRotate( y );
						y = root->parent;
					}

					y->color = root->parent->color;
					root->color = BLACK;

					if( y->rightChild )
						y->rightChild->color = BLACK;

					LeftRotate( root->parent );
					root = m_root;
	
				}
			}
			else if( root == root->parent->rightChild )
			{
				pRedBlackNode y = root->parent->leftChild;
				if( RED == y->color )
				{
					y->color = BLACK;
					root->parent->color = RED;
					RightRotate( root->parent );
					y = root->parent->leftChild;
				}
				if( y->leftChild && BLACK == y->leftChild->color && y->rightChild && BLACK == y->rightChild->color )
				{
					y->color = RED;
					root = root->parent;
				}
				else 
				{
					if( y->leftChild && BLACK == y->leftChild->color )
					{
						y->rightChild->color = BLACK;
						y->color = RED;
						LeftRotate( y );
						y = root->parent;
					}

					y->color = root->parent->color;
					root->color = BLACK;

					if( y->leftChild )
						y->leftChild->color = BLACK;

					RightRotate( root->parent );
					root = m_root;

				}
			}
		}// terminal while loop

		root->color = BLACK;
	}



	/*
	* reabalance tree when complete insert operation
	*
	*/
	void InsertReablance( pRedBlackNode root )
	{
		if( 0 == root->parent )
		{
			root->color = BLACK;
			return;
		}

		while( root->parent && RED == root->parent->color )
		{
			if( root->parent->parent )
			{
				if( root->parent == root->parent->parent->leftChild )  // uncle right
				{
					pRedBlackNode y = root->parent->parent->rightChild;		
					if( y && RED == y->color )  // case 1
					{
						root->parent->color = BLACK;
						y->color = BLACK;
						root->parent->parent->color = RED;

						root = root->parent->parent;
					}
					else
					{
						if( root == root->parent->rightChild )
						{
							root = root->parent;
							LeftRotate( root );
						}

						root->parent->color = BLACK;
						root->parent->parent->color = RED;

						RightRotate( root->parent->parent );
					}

				}
				else if( root->parent == root->parent->parent->rightChild ) // uncle left
				{
					pRedBlackNode y = root->parent->parent->leftChild;	
					if( y && RED == y->color )  // case 1
					{
						root->parent->color = BLACK;
						y->color = BLACK;
						root->parent->parent->color = RED;

						root = root->parent->parent;
					}
					else 
					{
						if( root == root->parent->leftChild )
						{
							root = root->parent;
							RightRotate( root );
						}

						root->parent->color = BLACK;
						root->parent->parent->color = RED;

						LeftRotate( root->parent->parent );

					}	
				}
			}
		}

		m_root->color = BLACK;
	}

	/*
	*Insert element to redblack tree
	*
	*/
	void InsertUtil( const T& key, const V& value )
	{
		pRedBlackNode root = m_root;
		pRedBlackNode cur = root;
		while( root )
		{
			cur = root;
			if( key < root->key )
			{
				root = root->leftChild;
			}
			else if( key > root->key )
			{
				root = root->rightChild;
			}
		}

		pRedBlackNode newNode = new RedBlackNode( key, value );
		newNode->parent = cur;
		if( 0 == cur )
		{
			m_root = newNode;
		}
		else if( cur->key > newNode->key )
		{
			cur->leftChild = newNode;
		}
		else if( cur->key < newNode->key )
		{
			cur->rightChild = newNode;
		}

		InsertReablance( newNode );
		m_size++;
	}

	/*
	* Delete element from redblack tree
	*
	*/
	pRedBlackNode DeleteUtil( pRedBlackNode root,  const T& key )
	{
		if( 0 == root )
			return 0;

		pRedBlackNode y = 0;
		if( 0 == root->leftChild ||
			0 == root->rightChild  )
		{
			y = root;
		}
		else
		{
			y = Successor( root );
		}

		pRedBlackNode x = 0;
		if( y->leftChild != 0 )
		{
			x = y->leftChild;
		}
		else 
		{
			 x = y->rightChild;
		}

		
		if( 0 == y->parent )
		{
			m_root = x;
		}
		else if( y == y->parent->leftChild )
		{
			x = y->parent->leftChild;
		}
		else
		{
			x = y->parent->rightChild;
		}

		x->parent = y->parent;

		if( y != root )
		{
			root->key = y->key;
			root->value = http://www.mamicode.com/y->value;>compile and run in visual studio 2005
泛型的RedBlack Tree的实现，并和STL map 做了简单的性能比较