织梦网站密码忘记了,盱眙网站建设,安徽先锋网站两学一做,连锁店销售管理系统红黑树的c完整实现源码 作者#xff1a;July、saturnman。时间#xff1a;二零一一年三月二十九日。出处#xff1a;http://blog.csdn.net/v_JULY_v。声明#xff1a;版权所有#xff0c;侵权必究。------------------------------------------- 前言#xff1a; 本人…红黑树的c完整实现源码 作者July、saturnman。时间二零一一年三月二十九日。出处http://blog.csdn.net/v_JULY_v。声明版权所有侵权必究。------------------------------------------- 前言 本人的原创作品红黑树系列文章至此已经写到第5篇了。虽然第三篇文章红黑树的c源码实现与剖析用c语言完整实现过红黑树但个人感觉代码还是不够清晰。特此再奉献出一份c的完整实现源码以飨读者。 此份c实现源码代码紧凑了许多也清晰了不少同时采取c类实现的方式代码也更容易维护以及重用。ok有任何问题欢迎指正。 版权声明 本BLOG内的此红黑树系列总计六篇文章是整个国内有史以来有关红黑树的最具代表性最具完整性最具参考价值的资料。且本人对此红黑树系列全部文章享有版权任何人任何组织任何出版社不得侵犯本人版权相关利益违者追究法律责任。谢谢。 红黑树的c完整实现源码 本文包含红黑树c实现的完整源码所有的解释都含在注释中所有的有关红黑树的原理及各种插入、删除操作的情况都已在本人的红黑树系列的前4篇文章中一一阐述。且在此红黑树系列第五篇文章中红黑树从头至尾插入和删除结点的全程演示图把所有的插入、删除情况都一一展示尽了。 因此有关红黑树的全部原理请参考其它文章重点可参考此文红黑树算法的实现与剖析。因此相关原理本文不再赘述。 ok以下即是红黑树c实现的全部源码先是RBTree.h然后是RBTree.cpp。 RBTree.h//file RBTree.h //written by saturnman20101008。 //updated by July20110329。 /*----------------------------------------------- 版权声明 July和saturnman对此份红黑树的c实现代码享有全部的版权 谢绝转载侵权必究。 ------------------------------------------------*/ #ifndef _RB_TREE_H_ #define _RB_TREE_H_ #includeiostream #includestring #includesstream #includefstream using namespace std; templateclass KEY,class U class RB_Tree { private: RB_Tree(const RB_Tree input){} const RB_Tree operator(const RB_Tree input){} private: enum COLOR{RED,BLACK}; class RB_Node { public: RB_Node() { //RB_COLOR BLACK; right NULL; left NULL; parent NULL; } COLOR RB_COLOR; RB_Node* right; RB_Node* left; RB_Node* parent; KEY key; U data; }; public: RB_Tree() { this-m_nullNode new RB_Node(); this-m_root m_nullNode; this-m_nullNode-right this-m_root; this-m_nullNode-left this-m_root; this-m_nullNode-parent this-m_root; this-m_nullNode-RB_COLOR BLACK; } bool Empty() { if(this-m_root this-m_nullNode) { return true; } else { return false; } } //查找key RB_Node* find(KEY key) { RB_Node* index m_root; while(index ! m_nullNode) { if(keyindex-key) { index index-left; //比当前的小往左 } else if(keyindex-key) { index index-right; //比当前的大往右 } else { break; } } return index; } //--------------------------插入结点总操作---------------------------------- //全部的工作都在下述伪代码中 /*RB-INSERT(T, z) 1 y ← nil[T] // y 始终指向 x 的父结点。 2 x ← root[T] // x 指向当前树的根结点 3 while x ≠ nil[T] 4 do y ← x 5 if key[z] key[x] //向左向右.. 6 then x ← left[x] 7 else x ← right[x] //为了找到合适的插入点x探路跟踪路径直到x成为NIL 为止。 8 p[z] ← y //y置为 插入结点z 的父结点。 9 if y nil[T] 10 then root[T] ← z 11 else if key[z] key[y] 12 then left[y] ← z 13 else right[y] ← z //此 8-13行置z 相关的指针。 14 left[z] ← nil[T] 15 right[z] ← nil[T] //设为空 16 color[z] ← RED //将新插入的结点z作为红色 17 RB-INSERT-FIXUP(T, z) */ //因为将z着为红色可能会违反某一红黑性质 //所以需要调用下面的RB-INSERT-FIXUP(T, z)来保持红黑性质。 bool Insert(KEY key,U data) { RB_Node* insert_point m_nullNode; RB_Node* index m_root; while(index!m_nullNode) { insert_point index; if(keyindex-key) { index index-left; } else if(keyindex-key) { index index-right; } else { return false; } } RB_Node* insert_node new RB_Node(); insert_node-key key; insert_node-data data; insert_node-RB_COLOR RED; insert_node-right m_nullNode; insert_node-left m_nullNode; if(insert_pointm_nullNode) //如果插入的是一颗空树 { m_root insert_node; m_root-parent m_nullNode; m_nullNode-left m_root; m_nullNode-right m_root; m_nullNode-parent m_root; } else { if(keyinsert_point-key) { insert_point-left insert_node; } else { insert_point-right insert_node; } insert_node-parent insert_point; } InsertFixUp(insert_node); //调用InsertFixUp修复红黑树性质。 } //---------------------插入结点性质修复-------------------------------- //3种插入情况都在下面的伪代码中(未涉及到所有全部的插入情况)。 /* RB-INSERT-FIXUP(T, z) 1 while color[p[z]] RED 2 do if p[z] left[p[p[z]]] 3 then y ← right[p[p[z]]] 4 if color[y] RED 5 then color[p[z]] ← BLACK ? Case 1 6 color[y] ← BLACK ? Case 1 7 color[p[p[z]]] ← RED ? Case 1 8 z ← p[p[z]] ? Case 1 9 else if z right[p[z]] 10 then z ← p[z] ? Case 2 11 LEFT-ROTATE(T, z) ? Case 2 12 color[p[z]] ← BLACK ? Case 3 13 color[p[p[z]]] ← RED ? Case 3 14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3 15 else (same as then clause with right and left exchanged) 16 color[root[T]] ← BLACK */ //然后的工作就非常简单了即把上述伪代码改写为下述的c代码 void InsertFixUp(RB_Node* node) { while(node-parent-RB_COLORRED) { if(node-parentnode-parent-parent-left) // { RB_Node* uncle node-parent-parent-right; if(uncle-RB_COLOR RED) //插入情况1z的叔叔y是红色的。 { node-parent-RB_COLOR BLACK; uncle-RB_COLOR BLACK; node-parent-parent-RB_COLOR RED; node node-parent-parent; } else if(uncle-RB_COLOR BLACK ) //插入情况2z的叔叔y是黑色的。 { if(node node-parent-right) //且z是右孩子 { node node-parent; RotateLeft(node); } else //插入情况3z的叔叔y是黑色的但z是左孩子。 { node-parent-RB_COLOR BLACK; node-parent-parent-RB_COLOR RED; RotateRight(node-parent-parent); } } } else //这部分是针对为插入情况1中z的父亲现在作为祖父的右孩子了的情况而写的。 //15 else (same as then clause with right and left exchanged) { RB_Node* uncle node-parent-parent-left; if(uncle-RB_COLOR RED) { node-parent-RB_COLOR BLACK; uncle-RB_COLOR BLACK; uncle-parent-RB_COLOR RED; node node-parent-parent; } else if(uncle-RB_COLOR BLACK) { if(node node-parent-left) { node node-parent; RotateRight(node); //与上述代码相比左旋改为右旋 } else { node-parent-RB_COLOR BLACK; node-parent-parent-RB_COLOR RED; RotateLeft(node-parent-parent); //右旋改为左旋即可。 } } } } m_root-RB_COLOR BLACK; } //左旋代码实现 bool RotateLeft(RB_Node* node) { if(nodem_nullNode || node-rightm_nullNode) { return false;//cant rotate } RB_Node* lower_right node-right; lower_right-parent node-parent; node-rightlower_right-left; if(lower_right-left!m_nullNode) { lower_right-left-parent node; } if(node-parentm_nullNode) //rotate node is root { m_root lower_right; m_nullNode-left m_root; m_nullNode-right m_root; //m_nullNode-parent m_root; } else { if(node node-parent-left) { node-parent-left lower_right; } else { node-parent-right lower_right; } } node-parent lower_right; lower_right-left node; } //右旋代码实现 bool RotateRight(RB_Node* node) { if(nodem_nullNode || node-leftm_nullNode) { return false;//cant rotate } RB_Node* lower_left node-left; node-left lower_left-right; lower_left-parent node-parent; if(lower_left-right!m_nullNode) { lower_left-right-parent node; } if(node-parent m_nullNode) //node is root { m_root lower_left; m_nullNode-left m_root; m_nullNode-right m_root; //m_nullNode-parent m_root; } else { if(nodenode-parent-right) { node-parent-right lower_left; } else { node-parent-left lower_left; } } node-parent lower_left; lower_left-right node; } //--------------------------删除结点总操作---------------------------------- //伪代码不再贴出详情请参考此红黑树系列第二篇文章 //经典算法研究系列五、红黑树算法的实现与剖析 //http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx。 bool Delete(KEY key) { RB_Node* delete_point find(key); if(delete_point m_nullNode) { return false; } if(delete_point-left!m_nullNode delete_point-right!m_nullNode) { RB_Node* successor InOrderSuccessor(delete_point); delete_point-data successor-data; delete_point-key successor-key; delete_point successor; } RB_Node* delete_point_child; if(delete_point-right!m_nullNode) { delete_point_child delete_point-right; } else if(delete_point-left!m_nullNode) { delete_point_child delete_point-left; } else { delete_point_child m_nullNode; } delete_point_child-parent delete_point-parent; if(delete_point-parentm_nullNode)//delete root node { m_root delete_point_child; m_nullNode-parent m_root; m_nullNode-left m_root; m_nullNode-right m_root; } else if(delete_point delete_point-parent-right) { delete_point-parent-right delete_point_child; } else { delete_point-parent-left delete_point_child; } if(delete_point-RB_COLORBLACK !(delete_point_childm_nullNode delete_point_child-parentm_nullNode)) { DeleteFixUp(delete_point_child); } delete delete_point; return true; } //---------------------删除结点性质修复----------------------------------- //所有的工作都在下述23行伪代码中 /* RB-DELETE-FIXUP(T, x) 1 while x ≠ root[T] and color[x] BLACK 2 do if x left[p[x]] 3 then w ← right[p[x]] 4 if color[w] RED 5 then color[w] ← BLACK ? Case 1 6 color[p[x]] ← RED ? Case 1 7 LEFT-ROTATE(T, p[x]) ? Case 1 8 w ← right[p[x]] ? Case 1 9 if color[left[w]] BLACK and color[right[w]] BLACK 10 then color[w] ← RED ? Case 2 11 x p[x] ? Case 2 12 else if color[right[w]] BLACK 13 then color[left[w]] ← BLACK ? Case 3 14 color[w] ← RED ? Case 3 15 RIGHT-ROTATE(T, w) ? Case 3 16 w ← right[p[x]] ? Case 3 17 color[w] ← color[p[x]] ? Case 4 18 color[p[x]] ← BLACK ? Case 4 19 color[right[w]] ← BLACK ? Case 4 20 LEFT-ROTATE(T, p[x]) ? Case 4 21 x ← root[T] ? Case 4 22 else (same as then clause with right and left exchanged) 23 color[x] ← BLACK */ //接下来的工作很简单即把上述伪代码改写成c代码即可。 void DeleteFixUp(RB_Node* node) { while(node!m_root node-RB_COLORBLACK) { if(node node-parent-left) { RB_Node* brother node-parent-right; if(brother-RB_COLORRED) //情况1x的兄弟w是红色的。 { brother-RB_COLOR BLACK; node-parent-RB_COLOR RED; RotateLeft(node-parent); } else //情况2x的兄弟w是黑色的 { if(brother-left-RB_COLOR BLACK brother-right-RB_COLOR BLACK) //且w的俩个孩子都是黑色的。 { brother-RB_COLOR RED; node node-parent; } else if(brother-right-RB_COLOR BLACK) //情况3x的兄弟w是黑色的w的右孩子是黑色w的左孩子是红色。 { brother-RB_COLOR RED; brother-left-RB_COLOR BLACK; RotateRight(brother); } else if(brother-right-RB_COLOR RED) //情况4x的兄弟w是黑色的且w的右孩子时红色的。 { brother-RB_COLOR node-parent-RB_COLOR; node-parent-RB_COLOR BLACK; brother-right-RB_COLOR BLACK; RotateLeft(node-parent); node m_root; } } } else //下述情况针对上面的情况1中node作为右孩子而阐述的。 //22 else (same as then clause with right and left exchanged) //同样原理一致只是遇到左旋改为右旋遇到右旋改为左旋即可。其它代码不变。 { RB_Node* brother node-parent-left; if(brother-RB_COLOR RED) { brother-RB_COLOR BLACK; node-parent-RB_COLOR RED; RotateRight(node-parent); } else { if(brother-left-RB_COLORBLACK brother-right-RB_COLOR BLACK) { brother-RB_COLOR RED; node node-parent; } else if(brother-left-RB_COLORBLACK) { brother-RB_COLOR RED; brother-right-RB_COLOR BLACK; RotateLeft(brother); } else if(brother-left-RB_COLORRED) { brother-RB_COLOR node-parent-RB_COLOR; node-parent-RB_COLOR BLACK; brother-left-RB_COLOR BLACK; RotateRight(node-parent); node m_root; } } } } m_nullNode-parent m_root; //最后将node置为根结点 node-RB_COLOR BLACK; //并改为黑色。 } // inline RB_Node* InOrderPredecessor(RB_Node* node) { if(nodem_nullNode) //null node has no predecessor { return m_nullNode; } RB_Node* result node-left; //get nodes left child while(result!m_nullNode) //try to find nodes left subtrees right most node { if(result-right!m_nullNode) { result result-right; } else { break; } } //after while loop resultnull or results right child is null if(resultm_nullNode) { RB_Node* index node-parent; result node; while(index!m_nullNode result index-left) { result index; index index-parent; } result index; // first right parent or null } return result; } // inline RB_Node* InOrderSuccessor(RB_Node* node) { if(nodem_nullNode) //null node has no successor { return m_nullNode; } RB_Node* result node-right; //get nodes right node while(result!m_nullNode) //try to find nodes right subtrees left most node { if(result-left!m_nullNode) { result result-left; } else { break; } } //after while loop resultnull or results left child is null if(result m_nullNode) { RB_Node* index node-parent; result node; while(index!m_nullNode result index-right) { result index; index index-parent; } result index; //first parents left or null } return result; } //debug void InOrderTraverse() { InOrderTraverse(m_root); } void CreateGraph(string filename) { //delete } void InOrderCreate(ofstream file,RB_Node* node) { //delete } void InOrderTraverse(RB_Node* node) { if(nodem_nullNode) { return; } else { InOrderTraverse(node-left); coutnode-keyendl; InOrderTraverse(node-right); } } ~RB_Tree() { clear(m_root); delete m_nullNode; } private: // utility function for destructor to destruct object; void clear(RB_Node* node) { if(nodem_nullNode) { return ; } else { clear(node-left); clear(node-right); delete node; } } private: RB_Node *m_nullNode; RB_Node *m_root; }; #endif /*_RB_TREE_H_*/ RBTree.cpp//file RBTree.cpp //written by saturnman20101008。 //updated by July20110329。 //此处省去了所有要包含的头文件 //主函数测试用例 int main() { RB_Treeint,int tree; vectorint v; for(int i0;i20;i) { v.push_back(i); } random_shuffle(v.begin(),v.end()); copy(v.begin(),v.end(),ostream_iteratorint(cout, )); coutendl; stringstream sstr; for(i0;iv.size();i) { tree.Insert(v[i],i); coutinsert:v[i]endl; //添加结点 } for(i0;iv.size();i) { coutDelete:v[i]endl; tree.Delete(v[i]); //删除结点 tree.InOrderTraverse(); } coutendl; tree.InOrderTraverse(); return 0; } 运行效果图先是一一插入各结点然后再删除所有的结点 参考文献本人的原创作品红黑树系列的前五篇文章 4、一步一图一代码R-B Tree1、教你透彻了解红黑树5、红黑树插入和删除结点的全程演示3、红黑树的c源码实现与剖析2、红黑树算法的实现与剖析6、致谢http://saturnman.blog.163.com/。 完。 版权所有。谢绝转载杜绝一切的侵犯版权的任何举动。违者必定追究法律责任。谢谢各位。转载于:https://www.cnblogs.com/v-July-v/archive/2011/03/29/2002183.html
