红黑树的实现(int精简版)
最近在阅读SGI STL源代码，其中红黑树的实现比较有技术含量，但标准库里面是捆绑了其中的allocator, iterator(Rb_tree专用的)，使用很多模板变量，实现对多种数据类型的处理。这些情况对于有较扎实C++基础的人来说不成问题，但对于一般初学算法，而又没有太好的C++基础的人来说有点困难。并且SGI STL中的实现代码写得很精巧，节省代码，也高效运行，但会使得功能不够深厚的人读起来还是比较费劲。
这里使用简单的int类型节点，实现红黑树的创建、插入及相关内部操作的功能。目前代码中删除节点及其内部操作功能没有实现。
关于红黑树的五个条件（有的书上说四个，内容是等价的）以及插入节点后的调整，可以参考侯捷先生的《STL源码剖析》，里面有详细的原理介绍。也可以参考《算法导论》。下面代码可以直接使用运行，经测试正确，代码不追求在物理运行上的效率，尽量把算法步骤表现在代码里，不作过多合并优化，并且已经加上不少注释，方便阅读。
My_Rb_Tree.h
#pragma once#define node_black true#define node_red falsetypedef 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
/************************************************************************//* @brief Red-Black tree implement./* @author sail2010@163.com/* @date 2012.10.12/* @time 16:56:37 /************************************************************************/#include "StdAfx.h"#include "My_Rb_Tree.h"#include "assert.h"My_Rb_Tree::My_Rb_Tree(void):node_count(0),head(0){Init();}My_Rb_Tree::~My_Rb_Tree(void){}node * My_Rb_Tree::Root(){assert(head);if (!head){return 0;}return head->parent;}void My_Rb_Tree::Init(){head = CreateNode(0);if (!head){return;}head->color = node_red;head->left = head;head->right = head;head->parent = 0;}node * My_Rb_Tree::CreateNode(value_type _val){node * n = new node;n->parent = 0;n->left = 0;n->right = 0;n->color = node_red;n->val = _val;return n;}void My_Rb_Tree::DestoryNode(node * &_n){delete _n;_n = 0;}void My_Rb_Tree::RotateLeft(node * _cur){node * _root = Root();node * r = _cur->right;if (!r){return;}if ( _cur ==_root ){_root = r;r->parent = _cur->parent;_cur->parent->parent = r;}else{}r->parent = _cur->parent;if (_cur->parent->left == _cur){r->parent->left = r;}else{r->parent->right = r;}_cur->right = r->left;if (r->left){_cur->right->parent = _cur;}r->left = _cur;_cur->parent = r;}void My_Rb_Tree::RotateRight(node * _cur){node * _root = Root();node * l = _cur->left;if (!l){return;}if ( _cur == _root ){_root = l;l->parent = _cur->parent;//headl->parent->parent = l;// head->parent}else{l->parent = _cur->parent;if (l->parent->left == _cur){l->parent->left = l;}else{l->parent->right = l;}}_cur->left = l->right;if (l->right){_cur->left->parent = _cur;}l->right = _cur;_cur->parent = l;}void My_Rb_Tree::Rebalance(node * _cur){node * _root = Root();_cur->color = node_red;if (_cur->parent == head) // _cur is root node{_cur->color = node_black;return;}if ( _cur->parent->color == node_black ) // now is balance state.{return ;}// 根据原来的树是符合红黑规则，祖父节点必定为黑色while( (_cur != Root()) && (_cur->parent->color == node_red)) // 当前节点的父节点为红色，违反规则{if (_cur->parent->parent->left == _cur->parent) // 父节点为左子节点{if(_cur->parent->parent->right&& _cur->parent->parent->right->color == node_red) // 伯父节点为红{// 把父节点和伯父节点变成黑色，祖父节点变成红色_cur->parent->parent->right->color=node_black;_cur->parent->color = node_black;_cur->parent->parent->color = node_red;// 因为祖父节点为红色，需要继续向上测试是否满足规则_cur = _cur->parent->parent;continue;}else // 伯父节点为黑或不存在{if ( _cur == _cur->parent->right ){// 以父节点为轴，左旋转后变成两个左外节点连续为红。_cur = _cur->parent;RotateLeft(_cur/*,_root*/);}// 改变颜色，以祖父节点为轴，右旋转。_cur->parent->parent->color = node_red;_cur->parent->color = node_black;RotateRight(_cur->parent->parent/*,_root*/);// 此时进入下一次while判断跳出循环}}else // 父节点为右子节点，依照左子节点的同样方法解决。{if(_cur->parent->parent->left&& _cur->parent->parent->left->color == node_red) // 伯父节点为红{// 把父节点和伯父节点变成黑色，祖父节点变成红色_cur->parent->parent->left->color=node_black;_cur->parent->color = node_black;_cur->parent->parent->color = node_red;// 因为祖父节点为红色，需要继续向上测试是否满足规则_cur = _cur->parent->parent;continue;}else // 伯父节点为黑或不存在{if ( _cur == _cur->parent->left ){// 以父节点为轴，右旋转后变成两个右外节点连续为红。_cur = _cur->parent;RotateRight(_cur/*,_root*/);}// 改变颜色，以祖父节点为轴，左旋转。_cur->parent->parent->color = node_red;_cur->parent->color = node_black;RotateLeft(_cur->parent->parent/*,_root*/);// 此时进入下一次while判断跳出循环}}}//end while_root->color = node_black;}node * My_Rb_Tree::InsertUnique(value_type in_val){node * y = head;node * x = Root();bool comp = true;while( x )//一层一层深入找到合适的插入点{y = x;comp = ( in_val < x->val );if (in_val == x->val){return 0;}x = comp ? x->left : x->right;}return Insert(y,x,in_val);}node * My_Rb_Tree::Insert(node * in_parent, node * in_cur, value_type in_value){node * new_node = CreateNode(in_value);if (in_parent == head) // 插入的是根节点{head->parent = new_node;head->left = new_node;head->right = new_node;new_node->parent = head;new_node->color = node_black;}else // 插入的是非根节点{if ( new_node->val < in_parent->val ){in_parent->left = new_node;if (in_parent == head->left) // 若插入点的父节点是最小节点，更新最小值节点指针{head->left = new_node;}}else{in_parent->right = new_node;if (in_parent == head->right)// 若插入点的父节点是最大节点，更新最大值节点指针{head->right = new_node;}}new_node->parent = in_parent;if (in_parent == head){head->parent = new_node;in_parent->parent = Root();}}Rebalance(new_node/*,head->parent*/);node_count++;return new_node;}// 未实现，这个函数比较复杂void My_Rb_Tree::RebalanceForErase(node * _cur){return;}// 依赖RebalanceForErase的实现void My_Rb_Tree::Erase(node * in_cur){return;}node * My_Rb_Tree::Find(value_type _val){node * _t = Root();while(_t){if (_t->val == _val){return _t;}else if (_t->val > _val){_t = _t->right;}else{_t = _t->left;}}return 0;}