今天呆在宿舍看了一天的紅黑樹，算是基本了解了一點關于紅黑樹的基礎知識，寫這篇博客意在整理今天所學的內容，先把紅黑樹的基礎知識貼上來。結合之前寫過的關于二叉排序樹的基礎，嘗試整理的資料如下：

紅黑樹是一種二叉排序樹，先來回憶一下二叉排序樹的基本性質：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分別為二叉排序樹

紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求: 性質1. 節點是紅色或黑色。 性質2. ?根節點是黑色。 性質3 ?每個葉節點（NIL節點，空節點）是黑色的。 性質4 ?每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點) 性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。 性質4導致了路徑不能有兩個毗連的紅色節點。所以最短的可能路徑都是黑色節點。最長的可能路徑有交替的紅色和黑色節點。因為根據性質5所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。 下圖，就是一個紅黑樹的例子： 容易看到紅黑樹的葉子節點都帶了1-2個NIL結點，這些結點其實就是實際上的NULL結點，但是我們為了編程需要，增加NIL結點，并對它進行了染（黑）色。 下面再來回顧一下關于二叉排序樹的旋轉知識： 圖片轉自http://blog.csdn.net/v_JULY_v/article/details/6109153
如上圖所示，左旋右旋我找來找去就這張圖最容易理解，但是我們再結合偽代碼來看一下具體實現。 LEFT-ROTATE(T, x) y = x.right x.right = y.left //把y的左結點接到x的右結點上 if y.left != T.nil then y.left.p = x //如果y的左結點非空，即不是NIL結點，則把該結點的父指針接到x上 y.p = x.p //把x的父指針賦給y if x.p == T.nil then T.root = y //如果剛剛好X是根節點，則把y結點賦給該樹的root值（根節點標記） else if x == x.p.left then x.p.left = y else x.parent.right = y //將y接到對應的x的父指針上 y.left = x //接上x結點 x.p = y //把x結點的父指針接到y上
明明用vc編出來是很規則的程序，碼上來就變成了這樣。 明天在貼紅黑樹的旋轉以及著色的偽代碼跟分析，費了我一天的時間去了解，不過總算搞了七七八八。歡迎指正。
本文關鍵字：二叉樹 紅黑樹 二叉樹旋轉
本文原創：Cout_Sev ? ? ?? 轉載注明出處 ??紅黑樹入門知識 謝謝!

總結

以上是生活随笔為你收集整理的【数据结构】红黑树入门知识的全部內容，希望文章能夠幫你解決所遇到的問題。

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