C++红黑树的实现
最近在阅读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 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
/************************************************************************/ /* @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;//head l->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; }