20140801_红黑树_学习总结

《20140801_红黑树_学习总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.定义红黑树是一种近AVL树。具有以下性质：1）结点非红即黑；2）根节点必须为黑色；3）任意从根到叶子的路径不包含连续的红色节点；4）从任意结点到其所有叶子结点的路径中，包含相同的黑色结点个数。举个例子：如图1所示，为一颗合法的红黑树，可以发现红黑树在维持二叉搜索树的基本性质的前提下，并满足了红黑树的颜色条件，整体上保持了二叉搜索树的平衡性图一2.和平衡二叉树（AVL）的区别红黑树AVL（平衡）使用颜色的概念维持树的平衡，使二叉搜索树的左右子树的高度差保持在固定的范围通过维持任何节点的左右子树的高度差不大于

2、1保持树的平衡O(log n)时间内做查找，在插入和删除的调整上操作少（即统计性能优）O(log n)时间内做查找，但统计性能差任何不平衡都会在三次旋转之内解决，其中插入两次旋转就可以解决3.数据结构//红黑树节点颜色enumrb_tree_node_color{red=false,black=true};//红黑树节点templateclassrb_tree_node{typedefrb_tree_node_colornode_color;typedefrb_tree_nodenode

3、_type;public:node_colorcolor;//颜色node_type*parent;//父节点node_type*left;//左子节点node_type*right;//右子节点Tvalue;//值rb_tree_node(T&v);//构造函数inlinenode_type*brother();//获取兄弟节点inlineboolon_left();//自身是左子节点inlineboolon_right();//自身是右子节点inlinevoidset_left(node_type*nod

4、e);//设置左子节点inlinevoidset_right(node_type*node);//设置左子节点};//红黑树templateclassrb_tree{public:typedefrb_tree_nodenode_type;rb_tree();~rb_tree();voidinsert(Tv);//添加节点boolinsert_unique(Tv);//添加唯一节点node_type*find(Tv);//查询节点boolremove(Tv);//删除节点private:n

5、ode_type*root;//树根unsignednode_count;//节点数void__insert(node_type*&sub_root,node_type*parent,node_type*node);//内部节点插入函数node_type*__find(node_type*sub_root,Tv);//查询void__rebalance(node_type*node);//新插入节点调整平衡void__fix(node_type*node,node_type*parent,booldirect

6、);//删除节点调整平衡void__rotate(node_type*node);//自动判断类型旋转void__rotate_left(node_type*node);//左旋转void__rotate_right(node_type*node);//右旋转bool__validate(node_type*&sub_root,int&count);//验证红黑树的合法性};1.插入操作1)将插入的点用n表示，p表示其父节点，b表示其兄弟节点，g表示其爷爷节点，u表示其叔叔节点，cl表示其左孩子节点，cr表示

7、其右孩子节点；如图2所示。图21)n颜色确定a)iftreeisnull,theninsertnastheroot,andturntheredtoblack;b)elseifnisblack:then破坏根路径上的黑色节点总数，修改难度大。elsethen有可能会出现连续红色节点的情况。相对而言，红色插入点好处理。故默认插入的节点颜色是红色。Gotob);c)ifpisblack:balanceelse:g,bmustbeblack;gotoc);之所以优先按照p进行分，是因为p和n的关系最密切d)ifuis

8、black:gotod);else：gotoi);之所以优先按照u划分，是因为u是2种情况。如果按照n，p的位置关系划分，则是8中情况。e)i.ifnistheleftchildofp&&pisleftchildofg:gotoe;ii.ifnistherightchildofp&&pisrightchildofg:gotof;iii.ifnistheleftchildofp&&pisrightch