🌳 1、簡述

紅黑樹是一種自平衡二叉查找樹（Self-Balancing Binary Search Tree），被廣泛應用于操作系統調度、Java集合、數據庫索引等核心模塊中。本文將從 基本原理 入手，結合 實際應用場景與代碼實例，帶你全面理解紅黑樹的精髓。

代碼樣例：https://gitee.com/lhdxhl/algorithm-example.git

---

📘 2、什么是紅黑樹？

紅黑樹是一種特殊的二叉查找樹（BST），其核心目的是通過維護“顏色約束”來實現平衡，從而提高插入、查找和刪除操作的效率。

紅黑樹的每個節點除了值和左右指針外，還會包含一個顏色字段（紅或黑）。

🎯 紅黑樹的五大性質

1. 每個節點不是紅色就是黑色。
2. 根節點是黑色。
3. 所有葉子節點（NIL）都是黑色的（虛擬葉子節點）。
4. 若一個節點是紅色，則其子節點必須是黑色（紅色節點不能相鄰）。
5. 從任一節點到其葉子節點的所有路徑上，黑色節點數量相同。

? 這些性質共同確保了樹的“近似平衡”，從而使紅黑樹操作的時間復雜度保持在：

• 查找：O(log n)
• 插入：O(log n)
• 刪除：O(log n)

---

🔧 3、紅黑樹的操作（核心邏輯）

📥 插入操作流程

• 插入節點為紅色，作為 BST 插入。
• 若父節點為黑色，插入完成。
• 若父節點為紅色，需通過旋轉（左旋/右旋）+變色保持平衡。
• 最終保持根節點為黑色。

📤 刪除操作流程

刪除較復雜，需要考慮：

• 替代節點顏色是否影響黑平衡；
• 是否需要旋轉或變色修復結構；
• 若刪除的是黑節點，需額外修復。

---

🧪 3、實踐樣例

用 Java 手寫簡化版紅黑樹：

public class RedBlackTree<K extends Comparable<K>, V> {private static final boolean RED = true;private static final boolean BLACK = false;private class Node {K key;V value;Node left, right;boolean color;Node(K key, V value, boolean color) {this.key = key;this.value = value;this.color = color;}}private Node root;// 判斷節點是否為紅色private boolean isRed(Node node) {return node != null && node.color == RED;}// 左旋private Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;return x;}// 右旋private Node rotateRight(Node h) {Node x = h.left;h.left = x.right;x.right = h;x.color = h.color;h.color = RED;return x;}// 顏色翻轉private void flipColors(Node h) {h.color = RED;h.left.color = BLACK;h.right.color = BLACK;}// 插入public void put(K key, V value) {root = put(root, key, value);root.color = BLACK;}private Node put(Node h, K key, V value) {if (h == null) return new Node(key, value, RED);int cmp = key.compareTo(h.key);if (cmp < 0) h.left = put(h.left, key, value);else if (cmp > 0) h.right = put(h.right, key, value);else h.value = value;if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);if (isRed(h.left) && isRed(h.right)) flipColors(h);return h;}public V get(K key) {Node x = root;while (x != null) {int cmp = key.compareTo(x.key);if (cmp < 0) x = x.left;else if (cmp > 0) x = x.right;else return x.value;}return null;}
}

下面是基于上面實現的 RedBlackTree 類的使用樣例，幫助你理解紅黑樹在 Java 中的基本操作與實際應用場景：

public class RedBlackTreeExample {public static void main(String[] args) {RedBlackTree<Integer, String> tree = new RedBlackTree<>();// 插入元素tree.put(10, "十");tree.put(5, "五");tree.put(15, "十五");tree.put(1, "一");tree.put(7, "七");// 查詢元素System.out.println("key=7 -> " + tree.get(7)); // 輸出: 七System.out.println("key=10 -> " + tree.get(10)); // 輸出: 十System.out.println("key=20 -> " + tree.get(20)); // 輸出: null（不存在）}
}

---

💡 4、應用場景

應用場景	使用說明
🔠 Java 的 TreeMap / TreeSet	使用紅黑樹實現有序鍵值對集合
🧠 Linux CFS（完全公平調度器）	使用紅黑樹調度任務時間片
🗂 數據庫索引（如 PostgreSQL）	作為內存結構實現 B-Tree 之前的數據排序
🧬 內核內存管理	設備地址映射、區域管理等

🔍 紅黑樹 vs 其它平衡樹對比

數據結構	插入復雜度	是否自平衡	應用代表
AVL樹	O(log n)	是	少見、用于內存索引
紅黑樹	O(log n)	是（弱平衡）	TreeMap、Linux
B+ 樹	O(log n)	是	數據庫索引
跳表（SkipList）	O(log n)	是（概率）	Redis

---

🧭 5、總結

紅黑樹的最大優點就是在保持結構平衡的同時，又能保證高效的增刪查性能，是大規模數據結構的核心基石。

? 學完你可以掌握：

• 紅黑樹的原理與五大性質
• 插入操作過程中的旋轉與變色
• 實際代碼實現簡化版紅黑樹
• 常見業務中紅黑樹的落地應用

📂 附：可選擴展方向

• 實現紅黑樹刪除操作
• 結合 java.util.TreeMap 調試源碼
• 使用紅黑樹管理區間（如IP段、時間段）

---

如果你對紅黑樹的圖解可視化、動畫講解或 C++ 實現也感興趣，我可以為你定制進一步內容！

是否需要將該博客生成 PDF、Markdown 或部署在 Hugo/Hexo 博客模板中？我可以幫你一鍵生成。