20140801_紅黑樹_學(xué)習(xí)總結(jié)

《20140801_紅黑樹_學(xué)習(xí)總結(jié)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1.定義紅黑樹是一種近AVL樹。具有以下性質(zhì)：1）結(jié)點(diǎn)非紅即黑；2）根節(jié)點(diǎn)必須為黑色；3）任意從根到葉子的路徑不包含連續(xù)的紅色節(jié)點(diǎn)；4）從任意結(jié)點(diǎn)到其所有葉子結(jié)點(diǎn)的路徑中，包含相同的黑色結(jié)點(diǎn)個(gè)數(shù)。舉個(gè)例子：如圖1所示，為一顆合法的紅黑樹，可以發(fā)現(xiàn)紅黑樹在維持二叉搜索樹的基本性質(zhì)的前提下，并滿足了紅黑樹的顏色條件，整體上保持了二叉搜索樹的平衡性圖一2.和平衡二叉樹（AVL）的區(qū)別紅黑樹AVL（平衡）使用顏色的概念維持樹的平衡，使二叉搜索樹的左右子樹的高度差保持在固定的范圍通過維持任何節(jié)點(diǎn)的左右子樹的高度差不大于

2、1保持樹的平衡O(log?n)時(shí)間內(nèi)做查找，在插入和刪除的調(diào)整上操作少（即統(tǒng)計(jì)性能優(yōu)）O(log?n)時(shí)間內(nèi)做查找，但統(tǒng)計(jì)性能差任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，其中插入兩次旋轉(zhuǎn)就可以解決3.數(shù)據(jù)結(jié)構(gòu)//紅黑樹節(jié)點(diǎn)顏色enumrb_tree_node_color{red=false,black=true};//紅黑樹節(jié)點(diǎn)templateclassrb_tree_node{typedefrb_tree_node_colornode_color;typedefrb_tree_nodenode

3、_type;public:node_colorcolor;//顏色node_type*parent;//父節(jié)點(diǎn)node_type*left;//左子節(jié)點(diǎn)node_type*right;//右子節(jié)點(diǎn)Tvalue;//值rb_tree_node(T&v);//構(gòu)造函數(shù)inlinenode_type*brother();//獲取兄弟節(jié)點(diǎn)inlineboolon_left();//自身是左子節(jié)點(diǎn)inlineboolon_right();//自身是右子節(jié)點(diǎn)inlinevoidset_left(node_type*nod

4、e);//設(shè)置左子節(jié)點(diǎn)inlinevoidset_right(node_type*node);//設(shè)置左子節(jié)點(diǎn)};//紅黑樹templateclassrb_tree{public:typedefrb_tree_nodenode_type;rb_tree();~rb_tree();voidinsert(Tv);//添加節(jié)點(diǎn)boolinsert_unique(Tv);//添加唯一節(jié)點(diǎn)node_type*find(Tv);//查詢節(jié)點(diǎn)boolremove(Tv);//刪除節(jié)點(diǎn)private:n

5、ode_type*root;//樹根unsignednode_count;//節(jié)點(diǎn)數(shù)void__insert(node_type*&sub_root,node_type*parent,node_type*node);//內(nèi)部節(jié)點(diǎn)插入函數(shù)node_type*__find(node_type*sub_root,Tv);//查詢void__rebalance(node_type*node);//新插入節(jié)點(diǎn)調(diào)整平衡void__fix(node_type*node,node_type*parent,booldirect

6、);//刪除節(jié)點(diǎn)調(diào)整平衡void__rotate(node_type*node);//自動(dòng)判斷類型旋轉(zhuǎn)void__rotate_left(node_type*node);//左旋轉(zhuǎn)void__rotate_right(node_type*node);//右旋轉(zhuǎn)bool__validate(node_type*&sub_root,int&count);//驗(yàn)證紅黑樹的合法性};1.插入操作1)將插入的點(diǎn)用n表示，p表示其父節(jié)點(diǎn)，b表示其兄弟節(jié)點(diǎn)，g表示其爺爺節(jié)點(diǎn)，u表示其叔叔節(jié)點(diǎn)，cl表示其左孩子節(jié)點(diǎn)，cr表示

7、其右孩子節(jié)點(diǎn)；如圖2所示。圖21)n顏色確定a)iftreeisnull,theninsertnastheroot,andturntheredtoblack;b)elseifnisblack:then破壞根路徑上的黑色節(jié)點(diǎn)總數(shù)，修改難度大。elsethen有可能會(huì)出現(xiàn)連續(xù)紅色節(jié)點(diǎn)的情況。相對(duì)而言，紅色插入點(diǎn)好處理。故默認(rèn)插入的節(jié)點(diǎn)顏色是紅色。Gotob);c)ifpisblack:balanceelse:g,bmustbeblack;gotoc);之所以優(yōu)先按照p進(jìn)行分，是因?yàn)閜和n的關(guān)系最密切d)ifuis

8、black:gotod);else：gotoi);之所以優(yōu)先按照u劃分，是因?yàn)閡是2種情況。如果按照n，p的位置關(guān)系劃分，則是8中情況。e)i.ifnistheleftchildofp&&pisleftchildofg:gotoe;ii.ifnistherightchildofp&&pisrightchildofg:gotof;iii.ifnistheleftchildofp&&pisrightch