问题提出：

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->leftCh