文章目錄

• • 1.概念
  • 2.操作
  • • 2.1 左旋、右旋（圍繞某個節點的左/右旋）
    • 2.2 插入
    • 2.3 刪除
  • 3. 代碼

1.概念

• 二叉樹在頻繁動態增刪后，可能退化成鏈表，時間復雜度由 O(lgn) 變成 O(n)。（不平衡）
• 平衡二叉樹，樹中任意一個節點的左右子樹的高度相差 <= 1。完全二叉樹、滿二又樹其實都是平衡二叉樹，但是非完全二叉樹也有可能是平衡二叉樹。
  
• 平衡二叉查找樹中“平衡”的意思，就是讓整棵樹左右看起來比較“對稱"、比較“平衡”，不要出現左子樹很高、右子樹很矮的情況。這樣就能讓整棵樹的高度相對來說低一些，相應的插入、刪除、查找等操作的效率高一些。
• 紅黑樹，R-B Tree，是一種不嚴格的平衡二叉查找樹，樹種節點，一類標記為黑色，一類標記為紅色。還需滿足以下條件：
• 根節點 黑色
• 每個葉子節點都是黑色的空節點（NIL），也就是說，葉子節點不存儲數據
• 任何相鄰的節點都不能同時為紅色，也就是說，紅色節點是被黑色節點隔開的
• 每個節點，從該節點到達其可達葉子節點的所有路徑，都包含相同數目的黑色節點
  
• 紅黑樹用的更多，AVL樹是一種高度平衡的二叉樹，查找的效率非常高，但是，有利就有弊，AVL樹為了維持這種高度的平衡，就要付出更多的代價。每次插入、刪除都要做調整，就比較復雜、耗時。所以，對于有頻繁的插入、刪除操作的數據集合，使用AVL樹的代價就有點高。
  紅黑樹只是做到了近似平衡，并不是嚴格的平衡，所以在維護平衡的成本上，要比AVL樹要低。所以，紅黑樹的插入、刪除、查找各種操作性能都比較穩定。對于工程應用來說，要面對各種異常情況，為了支撐這種工業級的應用，我們更傾向于這種性能穩定的平衡二叉查找樹。

2.操作

2.1 左旋、右旋（圍繞某個節點的左/右旋）

看之前，可以先閱讀下紅黑樹的歷史由來

2.2 插入

• 紅黑樹規定，插入節點必須為紅，而且，二叉查找樹中新插入的節點都是放在葉子節點上。

如果插入節點的父節點是黑色的，那我們什么都不用做，它仍然滿足紅黑樹的定義。

如果插入的節點是根節點，那我們直接改變它的顏色，把它變成黑色就可以了。
除此之外，其他情況都會違背紅黑樹的定義，于是我們就需要進行調整，調整的過程包含兩種基礎的操作：左右旋轉和改變顏色。
紅黑樹的插入旋轉和變色，請看這篇

2.3 刪除

• 看著很暈，先不寫了

3. 代碼

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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