算法导论-------------红黑树
红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。本章主要介绍了红黑树的性质、左右旋转、插入和删除。重点分析了在红黑树中插入和删除元素的过程,分情况进行详细讨论。一棵高度为h的二叉查找树可以实现任何一种基本的动态集合操作,如SEARCH、PREDECESSOR、SUCCESSOR、MIMMUM、MAXMUM、INSERT、DELETE等。当二叉查找树的高度较低时,这些操作执行的比较快,但是当树的高度较高时,这些操作的性能可能没有链表好。红黑树(red-black tree)是一种平衡的二叉查找树,它能保证在最坏情况下,基本的动态操作集合运行时间为O(lgn)。本章内容有些复杂,看了两天,才大概清楚其插入和删除过程,日后需要经常回顾,争取完全消化掉。红黑树的用途非常广泛,例如STL中的map就是采用红黑树实现的,效率非常之高,有机会可以研究一下STL的源代码。
不说了,看了两天的算法导论,终于把红黑树实现了,为了下半辈子过的好点,我也是蛮拼的。
红黑树的5个重要的性质:
(1)每个结点或是红色,或是黑色。
(2)根结点是黑色。
(3)每个叶子结点(NIL)是黑色。
(4)如果有一个结点是红色,则它的两个儿子都是黑色。
(5)对每个结点,从该结点到其孙子结点的所有路径上包含相同数目的黑色结点。
引理:一棵有n个内结点的红黑树的高度之多为2lg(n+1)。
还有一条重要性质:红黑树会确保没有一条路径会比其它路径长出两倍。
红黑树的一些操作在算法导论上都有详细的讲解,还有推理过程,讲的非常仔细,需要花一定的时间去理解,俺奋斗了2天,周末放假都呆在家里面没出去,这就是做一个码农的生活.
写了一个晚上好几个小时都在的调试代码,因为自己的粗心,在代码中对称操作的时候,有一个地方左右没有改过来导致我改了几个小时,NND,。
//*********************************************************************/ //time:2014.12.8 0:22 //author:ugly_chen(stallman) //csdn: http://blog.csdn.net/chenxun_2010 //*********************************************************************/ #include<iostream> #include<stack> using namespace std; static const int RED = 0; static const int BLACK = 1; template <class T> class Red_Black_Tree_Node { public: Red_Black_Tree_Node(T k) :key(k), color(BLACK), p(NULL), left(NULL), right(NULL) {} T key; int color; Red_Black_Tree_Node<T>* p; Red_Black_Tree_Node<T>* left; Red_Black_Tree_Node<T>* right; }; template <class T> class Red_Black_Tree { public: Red_Black_Tree(); Red_Black_Tree_Node<T>* get_root() const;//获取根节点 Red_Black_Tree_Node<T>* search_tree_node(const T& k)const;//查找关键字为k的节点 Red_Black_Tree_Node<T>* tree_maxmum(Red_Black_Tree_Node<T> *root) const;//查找最大关键字的节点 Red_Black_Tree_Node<T>* tree_minmum(Red_Black_Tree_Node<T> *root) const;//查找最小关键字的节点 Red_Black_Tree_Node<T>* tree_successor(Red_Black_Tree_Node<T> *pnode) const;//查找后继节点 Red_Black_Tree_Node<T>* tree_predecessor(Red_Black_Tree_Node<T> *pnode) const;//查找钱继节点 void left_rotate(Red_Black_Tree_Node<T> *pnode);//左旋转操作 void right_rotate(Red_Black_Tree_Node<T> *pnode);//右旋转操作 void rb_insert_fixup(Red_Black_Tree_Node<T> *pnode);//修正插入操作引起的违反红黑树性质的行为 void rb_delete_fixup(Red_Black_Tree_Node<T> *pnode);//修正删除操作引起的违反红黑树性质的行为 void rb_insert(Red_Black_Tree_Node<T>* z);//插入节点 void rb_delete(Red_Black_Tree_Node<T>* z);//删除节点 void inorder_tree_walk()const;//中序遍历红黑树:这样就是从小到大的顺序输出红黑树 void make_empty(Red_Black_Tree_Node<T>* root); //~Red_Black_Tree(); public: static Red_Black_Tree_Node<T> *NIL; private: Red_Black_Tree_Node<T>* root; }; //初始化nil template <class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::NIL = new Red_Black_Tree_Node<T>(-1); //初始化root节点 利用默认构造函数 template <class T> Red_Black_Tree<T>::Red_Black_Tree() { root = NIL; }; //--------------------------------------------------------------------------------------- template<class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::get_root() const//获取根节点 { return root; } //------------------------------------------------------------------------------------------ //查找树中关键字key的节点 template <class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::search_tree_node(const T& key) const { Red_Black_Tree_Node<T>* p = root; while (p != NIL) { if (p->key == key) break; else if (p -> key > key) p = p->left; else p = p->right; } return p; } //---------------------------------------------------------------------------------------- //查找最大关键字的节点 template <class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_maxmum(Red_Black_Tree_Node<T> *root) const { Red_Black_Tree_Node<T>* p = root; while (p->right != NIL) { p = p->right; } return p; } //------------------------------------------------------------------------------------------ //查找数中最小关键字的节点 template<class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_minmum(Red_Black_Tree_Node<T>* root) const { Red_Black_Tree_Node<T>* p = root; while (p->left != NIL) { p = p->left; } return p; } //---------------------------------------------------------------------------------------------- //查找后继节点:大于x的最小点 template<class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_successor(Red_Black_Tree_Node<T>* x) const { if (x->right != NIL) return tree_minmum(x->right); Red_Black_Tree_Node<T>* y = x->p; while (y != NIL &&x == y->right) { x = y; y = y->p; } return y; } //-------------------------------------------------------------------------------------------------- //查找前驱节点://查找中序遍历下x的前驱,即小于x的最大值 template<class T> Red_Black_Tree_Node<T>* Red_Black_Tree<T>::tree_predecessor(Red_Black_Tree_Node<T> *x) const { if (x->left != NIL) return tree_maxmum(x->left); Red_Black_Tree_Node<T>* y = x->p; while (y != NIL&&x == y->left) { x = y; y = y->p; } return y; } //---------------------------------------------------------------------------------------------------- //左旋转 template<class T> void Red_Black_Tree<T>::left_rotate(Red_Black_Tree_Node<T> *x) { Red_Black_Tree_Node<T> *y = x->right; x->right = y->left; if (y->left != NIL) y->left->p = x; y->p = x->p; if (x->p == NIL) root = y; else if (x == x->p->left) x->p->left = y; else x->p->right = y; y->left = x; x->p = y; } //右旋转 //------------------------------------------------------------------------------------------------------ template<class T> void Red_Black_Tree<T>::right_rotate(Red_Black_Tree_Node<T> *x) { Red_Black_Tree_Node<T> *y = x->left; x->left = y->right; if (y->right != NIL) y->right->p = x; y->p = x->p; if (x->p == NIL) root = y; else if (x == x->p->left) x->p->left = y; else x->p->right = y; y->right = x; x->p = y; } //-------------------------------------------------------------------------------- //插入的子过程:修正插入过后可能违反红黑树的节点 template<class T> void Red_Black_Tree<T>::rb_insert_fixup(Red_Black_Tree_Node<T>* z) { Red_Black_Tree_Node<T> *y; while (z->p->color == RED) { if (z->p == z->p->p->left)//z.p是z祖父的左孩子 { y = z->p->p->right; if (y->color == RED)//case1 z的叔节点为红色 { z->p->color = BLACK; y->color = BLACK; z->p->p->color = RED; z = z->p->p; } else //case 2 or case 3:叔节点是黑色 { if (z == z->p->right)//z是右孩子 { z = z->p; left_rotate(z); } //case3 z为左孩子 z->p->color = BLACK; z->p->p->color = RED; right_rotate(z->p->p); } } else if (z->p == z->p->p->right)//z.p是z祖父的右孩子,和上边情况相同也有三种情形 { y = z->p->p->left; if (y->color == RED) { z->p->color = BLACK; y->color = BLACK; z->p->p->color = RED; z = z->p->p; } else { if (z == z->p->left) { z = z->p; right_rotate(z); } z->p->color = BLACK; z->p->p->color = RED; left_rotate(z->p->p); } } } root->color = BLACK; } //------------------------------------------------------------------------------------------- //修正删除rb_tree某个节点带来的可能违反红黑树性质的行为 template<class T> void Red_Black_Tree<T>::rb_delete_fixup(Red_Black_Tree_Node<T> *x) { Red_Black_Tree_Node<T> *w; //如果这个额外的黑色在一个根结点或一个红结点上,结点会吸收额外的黑色,成为一个黑色的结点 while (x != root&&x->color == BLACK) { //若x是其父的左结点(右结点的情况相对应) if (x == x->p->left) { //令w为x的兄弟,根据w的不同,分为三种情况来处理 //执行删除操作前x肯定是没有兄弟的,执行删除操作后x肯定是有兄弟的 w = x->p->right; if (w->color == RED)// case 1 w为红色 { w->color = BLACK; x->p->color = RED; left_rotate(x->p); w = x->p->right;//由这种情形可以进入2 3 4任何一种情形 } if (w->left->color == BLACK && w->right->color == BLACK)//case 2:w为黑色,w的两个孩子也都是黑色 { w->color = RED; x = x->p; } else //case 3 w是黑色的,w->left是红色的,w->right是黑色的 { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; right_rotate(w); w = x->p->right; } //case 4:w是黑色的,w->left可以是红色也是可以是黑色,w->right 是红色 //修改 w 和 x.p的颜色 w->color = x->p->color; x->p->color = BLACK; w->right->color = BLACK; left_rotate(x->p); x = root; } } else if (x == x->p->right)//x为其父节点的右孩子 { w = x->p->left; if (w->color == RED)//case1,w.color为红色 { w->color = BLACK; x->p->color = RED; right_rotate(x->p); w = x->p->left;//令w为x的兄弟,转为2.3.4三种情况之一 } if (w->right->color == BLACK && w->left->color == BLACK)//case2:w为黑色,w的两个孩子也都是黑色 { w->color = RED; x = x->p; } else //case3:w是黑色的,w->left黑色,w->right是红色(与上面的相反:w->left是红色的,w->right是黑色的) { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; left_rotate(w); w = x->p->left;////令w为x的新兄弟,进入case4 } //case4:w是黑色的, w->left是红色 , w->right是可以是红色也可以是黑色. //修改w和p[x]的颜色 w->color = x->p->color; x->p->color = BLACK; w->left->color = BLACK; right_rotate(x->p); //此时调整已经结束,将x置为根结点是为了结束循环 x = root; } } } x->color = BLACK;//while循环结束的时候x的的颜色为红色,用来吸收黑色. } //--------------------------------------------------------------------------------------------- //插入操作:rb_insert template<class T> void Red_Black_Tree<T>::rb_insert(Red_Black_Tree_Node<T>* z) { Red_Black_Tree_Node<T>* y = NIL; Red_Black_Tree_Node<T>* x = root; while (x != NIL)//找到插入的位置 { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->p = y; if (y == NIL) root = z; else if (z->key < y->key) y->left = z; else y->right = z; z->left = NIL; z->right = NIL; z->color = RED; rb_insert_fixup(z); } //------------------------------------------------------------------------------- //节点删除操作:rb_delete template<class T> void Red_Black_Tree<T>::rb_delete(Red_Black_Tree_Node<T>* z) { Red_Black_Tree_Node<T>* y; Red_Black_Tree_Node<T>* x; if (z->left == NIL || z->right == NIL) y = z; else y = tree_successor(z); if (y->left != NIL) x = y->left; else x = y->right; x->p = y->p; if (y->p == NIL) root = x; else if (y == y->p->left) y->p->left = x; else y->p->right = x; if (y != z) z->key = y->key; //如果被删除的结点是黑色的,则需要调整 if (y->color == BLACK) rb_delete_fixup(x); } //----------------------------------------------------------------------------------------- //中序遍历红黑树,利用stack的功能从小到大输出红黑树 template <class T> void Red_Black_Tree<T>::inorder_tree_walk() const { if (NULL != root) { stack<Red_Black_Tree_Node<T>* > s; Red_Black_Tree_Node<T> *p; p = root; while (NIL != p || !s.empty()) { if (NIL != p) { s.push(p); p = p->left; } else { p = s.top(); s.pop(); cout << p->key << ":"; if (p->color == BLACK) cout << "Black" << endl; else cout << "Red" << endl; p = p->right; } } } } int main() { Red_Black_Tree<int> tree ; int s[6] = { 41, 38, 31, 12, 19, 8 }; int i; for (i = 0; i< 6; i++) { Red_Black_Tree_Node<int> *z = new Red_Black_Tree_Node<int>(s[i]); tree.rb_insert(z); } cout << "根节点是:" << tree.get_root()->key << endl; tree.inorder_tree_walk(); int s2[10] = { 8, 12, 20, 38, 39, 48,666,999,1,100 }; for (i = 0; i< 6; i++) { Red_Black_Tree_Node<int> *z = tree.search_tree_node(s2[i]); if (z != tree.NIL ) tree.rb_delete(z); } cout << "删除操作后的红黑树根节点是:"<<tree.get_root()->key << endl; tree.inorder_tree_walk(); return 0; }
最后要感谢两位大牛:
http://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html
http://blog.csdn.net/mishifangxiangdefeng/article/details/7718917
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。