STL源碼剖析之紅黑樹【2013.12.05】
歡迎加入我們的QQ群，無論你是否工作，學生，隻要有c / vc / c++ 程式設計經驗，就來吧！158427611
【紅黑樹】
紅黑樹是一種受限制的搜尋樹，其限制如下：
.
【紅黑樹的節點插入】
為了友善解說，閑定義幾個數值：
【X】插入節點，插入點必為紅色，保持限制4
【P】X的父節點
【G】P的父節點
【GG】G的父節點
【S】P的兄弟節點
根據紅黑樹節點的插入，可以分為幾種情況：
【一】
此情況：
隻需要進行一次旋轉就可以保持紅黑樹特性；
【二】
此情況，需要兩次旋轉才能保持紅黑樹的特性
【三】
此情況，也隻需要一次旋轉就可以完成
【四】
此情況也隻需要一次旋轉就能完成。
這種情況，需要向上遞歸尋找父節點，判斷父節點的紅黑情況，在樹比較小的時候雖然可以接受，但是當樹比較大的時候就是一種比較大的效率開銷了。
怎麼辦呢？
辦法當然被牛人們想到啦，對紅黑樹做一個自頂向下的周遊。當然是沿着插入點路徑了。
當遇到路徑上某個節點【M】的兩個子節點都為紅色的時候：将【M】點變成紅色，兩個子節點變成黑色。（參考限制4），如圖所示：
另外要注意的一點，雖然紅黑樹是一種搜尋樹，是平衡二叉樹
但是其實紅黑樹對平衡的要求不是那麼嚴謹的，有時候可能不會做到平衡，但是仍保持搜尋樹的其他特性。
STL中，紅黑樹的節點代碼設計比較特别的一點是：
ROOT根節點之上 還有個 Header節點。
他們不但互相為父子節點，而且Header節點的Left指向紅黑樹中最小節點，Right指向最大節點。
當然初始狀态的時候，隻有Header點，這時候，left和right都是指向自己，parent則是指向0（NULL）
當插入第一個節點的時候，即為根節點的時候，就看作最大最小值都是ROOT節點，Header和ROOT的關系就不但互相指向父子節點，而且left和right都指向Root。如圖所示：
為什麼這樣做呢？
【原因1】：這樣可以快速找到紅黑樹的最小最大值。
【原因2】：STL中紅黑樹是有++ 和 -- 兩種操作符的，說明紅黑樹是可以遞增遞減周遊的，這樣的設計就可以讓疊代器快速找到begin和end啦。對效率來說是一種很巧妙的設計！
【注意】
紅黑樹的構造，主要功效就是做搜尋，這也是紅黑樹的最大生命意義了，呵呵！
至于STL中紅黑樹的搜尋，就不多說了。
比較節點，節點值比搜尋值大的往左走，小的往右走。
歡迎加入我們的QQ群，無論你是否工作，學生，隻要有c / vc / c++ 程式設計經驗，就來吧！158427611