最近在阅读SGI STL源代码，其中红黑树的实现比较有技术含量，但标准库里面是捆绑了其中的allocator, iterator(Rb_tree专用的)，使用很多模板变量，实现对多种数据类型的处理。这些情况对于有较扎实C++(www.cppentry.com)基础的人来说不成问题，但对于一般初学算法，而又没有太好的C++(www.cppentry.com)基础的人来说有点困难。并且SGI STL中的实现代码写得很精巧，节省代码，也高效运行，但会使得功能不够深厚的人读起来还是比较费劲。

      这里使用简单的int类型节点，实现红黑树的创建、插入及相关内部操作的功能。目前代码中删除节点及其内部操作功能没有实现。

      关于红黑树的五个条件（有的书上说四个，内容是等价的）以及插入节点后的调整，可以参考侯捷先生的《STL源码剖析》，里面有详细的原理介绍。也可以参考《算法导论》。下面代码可以直接使用运行，经测试正确，代码不追求在物理运行上的效率，尽量把算法步骤表现在代码里，不作过多合并优化，并且已经加上不少注释，方便阅读。

My_Rb_Tree.h

[cpp]
#pragma once 
 
#define node_black true 
#define node_red false 
 
typedef bool node_color; 
typedef int value_type; 
 
struct node 
{ 
    node_color color; 
    node * left; 
    node * right; 
    node * parent; 
    value_type val; 
}; 
 
class My_Rb_Tree 
{ 
public: 
    My_Rb_Tree(void); 
    ~My_Rb_Tree(void); 
 
    node * InsertUnique(value_type in_val); 
    void Erase(node * in_cur); 
    node * Find(value_type _val); 
 
private: 
    node * Root(); 
    void Init(); 
    node * CreateNode(value_type _val); 
 
    void DestoryNode(node * &_n); 
 
    void RotateLeft(node * _cur); 
    void RotateRight(node * _cur); 
 
    void Rebalance(node * _cur); 
    void RebalanceForErase(node * _cur); 
 
    node * Insert(node * in_parent, node * in_cur, value_type in_value); 
 
private: 
    int node_count; 
    node * head; 
 
}; 

My_Rb_Tree.cpp

[cpp] view plaincopy
/************************************************************************/ 
/*  @brief Red-Black tree implement.
/*  @author sail2010@163.com
/*  @date 2012.10.12
/*  @time 16:56:37                                        
/************************************************************************/