紅 - 黑樹是一種平衡二叉樹被廣泛用于，但對于很多人誰是新算法，紅黑樹實在是太復雜，看之前July博文，覺得自己的寫作非常具體的。不過還是有點亂。不能急。要每天看一點點，所以我把插入和刪除分開來寫，僅僅要看懂并記住插入后是如何操作的，那么刪除也就easy了。

紅黑樹的規則：

性質1. 節點是紅色或黑色。

性質2. 根是黑色。

性質3. 全部葉子都是黑色（葉子是NIL節點）。

性質4. 每一個紅色節點的兩個子節點都是黑色。(從每一個葉子到根的全部路徑上不能有兩個連續的紅色節點)

性質5. 從任一節點到其每一個葉子的全部簡單路徑都包括同樣數目的黑色節點。

最基本的兩條是4和5。一旦插入一個新的節點，那么4和5的性質就有可能破壞。從5中我們能夠推出新增節點必須設為紅色，而再依據4。新增節點的父節點必須是黑色。

我們推出的這最后一條很重要。由于一旦發現插入節點要插在一個紅色節點下，就要開始折騰了！

紅黑樹的最基本操作是旋轉（左旋和右旋）。因為對稱性，將一個即可。

下圖介紹右旋的一個樣例（本文圖皆來自《STL源代碼剖析》）

我們從圖中發現，右旋事實上就是改變了k1,k2的父子關系，那么其它節點怎么變呢?

能夠這樣理解。父親要和兒子換位置，父親好悲劇，那父親的還有一個兒子和他的父子關系不能變（再變就太慘了），兒子長輩分了，那么兒子就把他的兒子交給原來的父親當兒子吧，而操作是右旋，那就移動兒子的右孩子。

簡記：右旋：孩子的右孩子給父親當左孩子。

? ? ? ? ? ? 左旋：孩子的左孩子給父親當右孩子。

默念三遍。就會發現旋轉的思路就是這么簡單！

代碼例如以下(STL源代碼。大師作品)：

inline void _rb_rotate_right(_rb_tree_node_base* x,_rb_tree_node_base*& root)\\x為k2。root為根節點_rb_tree_node_base* y=x->left; \\y為左孩子。也就是k1x->left=y->right; \\孩子的左孩子成為父親的右孩子 B接k2if(y->right!=0)y->right->parent=x; \\ 回馬槍設定父節點y->parent=x->parent; \\k1開始跑到k2的位置if(x==root)root=y;else if(x==x->parent->right) x->parent->right=y; \\y代替x的地位，但要和x的原父親的關系還原elsex->parent->left=y;y->right=x; x->parent=y; \\最后，父親變成孩子，悲劇。 }

代碼思路：1先把孩子的左孩子接到這個節點的右孩子上（2句） ?2這個右孩子的父親是這個節點（1句） 3、節點的左孩子代替節點的位置（1句） ?4、和原節點父親節點的關系保留（3種推斷） ?5、節點成為孩子節點的孩子（2句）

以下進入正題：插入節點

插入節點可能會帶來3種不同情況的破壞，下圖給出的是4種情況：（4僅僅是3的更復雜一點的情況）

我們細致觀察這三種不同情況，同樣的是插入節點的父親都是紅的。不同點有2:1是父親的兄弟節點（叔節點）是什么顏色的？2新增節點是作為左孩子還是右孩子？

第一種情況：

叔黑+左孩子（黑左bl）

解決方法：右旋。

例如以下圖:

說是右旋，旋哪個呢？新增節點肯定不動，以新節點的父親P，爺爺為軸右旋G。旋轉后這兩個節點顏色都變（新增點肯定是紅的）。

簡記：黑左（bl）=右旋PG

助記：bl=r+pg（Boys’ Love RPG）

另外一種情況：

叔黑+右孩子（br）

解決方法:左旋+右旋

例如以下圖:

我們從圖中能夠看出，先左旋X和P，再右旋X和G（變化X和G）。細致想想，第一次左旋似乎就是構造出第一種情況（圖2先把8和10的顏色變化了，應是8紅，10黑，那就和第一種情況一樣）。

簡記：黑右（br）=左旋XP。到達叔左。

助記：嘿喲，郎咸平（lXP）

第三種情況

叔紅

這樣的情況很easy。我們肯定叔節點不能有孩子了，有的話必須是黑色的，那叔節點那條分支的黑色就多了，所以我們能夠隨便改變叔節點的顏色（這是前提）。

例如以下圖（來自July）

4是新增節點，4和5都紅了。那就把5變黑，5黑后為了平衡的把8（叔節點）也變黑，都黑了后7這條分支比1分支多了一個黑色節點。所以7也要紅，這樣和2又都是紅色的了，還得往上遞歸。這時候7相當玉新插入節點。得三種情況推斷（圖中這個符合另外一種情況），一直遞歸到根節點。

簡記：變變變（PGU都變了），再推斷。

最后來看SLT里面大師是如何寫源碼的。

首先，他的思路有所變換，他感覺第三種情況一直往上遞歸太慢，所以他採用了先處理的方法，例如以下圖：

大致思路是：沿著插入節點往上看。假設有一個節點的兩個子節點都是紅色。那就把這個節點改成紅色，他的子節點都改成黑色。假設此時這個節點的父節點也是紅色（此時父節點的兄弟節點一定是黑的，請自己分析）就要像第一種或者第一種情況處理。

最后，插入節點的推斷就僅僅剩第1和第2兩種情況。

代碼例如以下：

// 這是一個全局函數 // 又一次令樹形平衡（改變顏色及旋轉樹形） inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root) //x新增節點，root為根節點 { x->color = _rb_tree_red; //新節點必為紅 while(x != root && x->parent->color == _rb_tree_red) // 假設父節點為紅 { if(x->parent == x->parent->parent->left) // 父節點為祖父節點之左子節點 { _rb_tree_node_base* y = x->parent->parent->right; // 令y為伯父節點 if(y && y->color == _rb_tree_red) // 伯父節點存在。且為紅（第三種情況） { x->parent->color = _rb_tree_black; // 更改父節點為黑色 y->color = _rb_tree_black; // 更改伯父節點為黑色 x->parent->parent->color = _rb_tree_red; // 更改祖父節點為紅色 x = x->parent->parent; //祖父節點變成新增結點了} else // 無伯父節點，或伯父節點為黑色 { if(x == x->parent->right) // 假設新節點為父節點之右子節點 （另外一種情況） { x = x->parent; _rb_tree_rotate_left(x , root); // 第一個參數為左旋點 } x->parent->color = _rb_tree_black; // 先改變顏色了 x->parent->parent->color = _rb_tree_red; _rb_tree_rotate_right(x->parent->parent , root); // （第一種情況）} } else // 父節點為祖父節點之右子節點（和上面對立） { _rb_tree_node_base* y = x->parent->parent->left; // 令y為伯父節點 if(y && y->color == _rb_tree_red) // 有伯父節點，且為紅 （第三種情況） { x->parent->color = _rb_tree_black; // 更改父節點為黑色 y->color = _rb_tree_black; // 更改伯父節點為黑色 x->parent->parent->color = _rb_tree_red; // 更改祖父節點為紅色 x = x->parent->parent; // 準備繼續往上層檢查 } else // 無伯父節點，或伯父節點為黑色 { if(x == x->parent->left) // 假設新節點為父節點之左子節點 （另外一種情況） { x = x->parent; _rb_tree_rotate_right(x , root); // 第一個參數為右旋點 （第一種情況）} x->parent->color = _rb_tree_black; // 先改變顏色 x->parent->parent->color = _rb_tree_red; _rb_tree_rotate_left(x->parent->parent , root); // 第一個參數為左旋點 } } }//while root->color = _rb_tree_black; // 根節點永遠為黑色 }

事實上，紅黑樹確實挺復雜的，變化太多，但僅僅要略微注意下幾種情況的相互關系，比方3->2->1，理解就簡單多了。

下一步學習刪除節點。

版權聲明：本文博客原創文章，博客，未經同意，不得轉載。

總結

以上是生活随笔為你收集整理的连贯的学习黑树（插入节点）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。