在 C++ 算法的神秘森林里，紅黑樹是一棵充滿智慧的 “魔法樹”。它既不像普通二叉搜索樹那樣容易失衡，也不像 AVL 樹對平衡要求那么苛刻。作為 C++ 算法小白，今天就和大家一起深入探索紅黑樹的奧秘，看看它是如何成為數據世界的平衡守護者的！?

紅黑樹是什么？?

紅黑樹是一種自平衡的二叉搜索樹，它在每個節點上增加了一個存儲位來表示節點的顏色，可以是紅色或黑色。通過對樹的節點顏色進行約束，紅黑樹確保了樹在最壞情況下，依然能保持相對平衡，從而讓搜索、插入和刪除操作的時間復雜度穩定在 ?

O(logn)

。?

紅黑樹的規則?

1. 節點顏色：每個節點要么是紅色，要么是黑色。?

1. 根節點：根節點是黑色。?

1. 葉子節點：每個葉子節點（NIL 節點，空節點）是黑色。?

1. 紅色節點：如果一個節點是紅色的，那么它的兩個子節點都是黑色的。?

1. 路徑黑色節點數：從任一節點到其每個葉子節點的所有路徑都包含相同數目的黑色節點。?

這五條規則就像是紅黑樹的 “生存法則”，讓它始終保持著良好的平衡狀態。可以把紅黑樹想象成一個嚴格遵守交通規則的城市，不同顏色的節點如同不同類型的車輛，在規則的約束下有序行駛，確保城市不會陷入混亂。?

紅黑樹的實現?

在 C++ 中，我們可以通過定義節點結構和相關操作來實現紅黑樹。以下是一個簡化版的紅黑樹實現代碼，并對關鍵部分進行詳細解釋。?

節點結構定義?

#include <iostream>// 定義紅黑樹節點結構
struct RBNode {int key;bool color;  // true 表示紅色，false 表示黑色RBNode* left;RBNode* right;RBNode* parent;RBNode(int k) : key(k), color(true), left(nullptr), right(nullptr), parent(nullptr) {}
};

每個節點包含鍵值 key 、顏色 color 、左右子節點指針 left 和 right ，以及父節點指針 parent 。節點默認顏色為紅色，因為新插入節點為紅色，在大多數情況下能減少調整操作。?

紅黑樹類定義與基本操作?

class RedBlackTree {
private:RBNode* root;// 左旋操作void leftRotate(RBNode* x) {RBNode* y = x->right;x->right = y->left;if (y->left != nullptr) {y->left->parent = x;}y->parent = x->parent;if (x->parent == nullptr) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}y->left = x;x->parent = y;}// 右旋操作void rightRotate(RBNode* x) {RBNode* y = x->left;x->left = y->right;if (y->right != nullptr) {y->right->parent = x;}y->parent = x->parent;if (x->parent == nullptr) {root = y;} else if (x == x->parent->right) {x->parent->right = y;} else {x->parent->left = y;}y->right = x;x->parent = y;}// 插入節點后的修復操作void insertFixup(RBNode* z) {while (z != root && z->parent->color == true) {if (z->parent == z->parent->parent->left) {RBNode* y = z->parent->parent->right;if (y != nullptr && y->color == true) {z->parent->color = false;y->color = false;z->parent->parent->color = true;z = z->parent->parent;} else {if (z == z->parent->right) {z = z->parent;leftRotate(z);}z->parent->color = false;z->parent->parent->color = true;rightRotate(z->parent->parent);}} else {RBNode* y = z->parent->parent->left;if (y != nullptr && y->color == true) {z->parent->color = false;y->color = false;z->parent->parent->color = true;z = z->parent->parent;} else {if (z == z->parent->left) {z = z->parent;rightRotate(z);}z->parent->color = false;z->parent->parent->color = true;leftRotate(z->parent->parent);}}}root->color = false;}public:RedBlackTree() : root(nullptr) {}// 插入節點void insert(int key) {RBNode* z = new RBNode(key);RBNode* y = nullptr;RBNode* x = root;while (x != nullptr) {y = x;if (z->key < x->key) {x = x->left;} else {x = x->right;}}z->parent = y;if (y == nullptr) {root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}insertFixup(z);}// 中序遍歷void inorderTraversal(RBNode* node) {if (node != nullptr) {inorderTraversal(node->left);std::cout << node->key << " ";inorderTraversal(node->right);}}void inorderTraversal() {inorderTraversal(root);std::cout << std::endl;}
};

1. 旋轉操作：左旋 leftRotate 和右旋 rightRotate 是紅黑樹保持平衡的重要手段。左旋以某個節點 x 為中心，將其右子節點 y 提升，x 變為 y 的左子節點；右旋則相反。就像在玩積木時，通過旋轉積木塊來調整結構，讓樹重新達到平衡。?

1. 插入修復操作：insertFixup 函數在插入新節點后，根據紅黑樹規則進行調整。如果新插入節點的父節點是紅色，就可能違反規則，需要通過變色和旋轉操作來修復，確保樹滿足所有紅黑樹規則。?

1. 插入節點：insert 函數先按照普通二叉搜索樹的方式找到插入位置，插入新節點后調用 insertFixup 進行修復，維持紅黑樹的平衡。?

1. 中序遍歷：inorderTraversal 函數用于遍歷紅黑樹，按順序輸出節點的鍵值，方便查看樹的結構和內容。?

例題講解：使用紅黑樹實現動態數據集合管理?

問題描述?

假設我們需要管理一個動態的整數集合，要求能夠快速插入新元素，并按順序輸出集合中的所有元素。使用紅黑樹來實現這個功能。?

代碼示例?

int main() {RedBlackTree rbt;rbt.insert(5);rbt.insert(3);rbt.insert(7);rbt.insert(2);rbt.insert(4);rbt.insert(6);rbt.insert(8);std::cout << "Inorder traversal of the Red-Black Tree: ";rbt.inorderTraversal();return 0;
}

代碼解釋?

在 main 函數中，創建了一個紅黑樹對象 rbt ，然后依次插入多個整數。插入過程中，紅黑樹會自動調整結構，保持平衡。最后通過中序遍歷，按順序輸出紅黑樹中的所有節點鍵值，得到有序的整數集合。?

紅黑樹在很多場景都有重要應用，比如 C++ 標準庫中的 map 和 set ，底層實現就用到了紅黑樹。它憑借高效的平衡維護和穩定的時間復雜度，成為了數據管理的得力助手。作為 C++ 算法小白，掌握紅黑樹的原理和應用，能讓我們在算法學習和編程實踐中更上一層樓！