【數據結構】紅黑樹（C++）

一、紅黑樹的概念

二、紅黑樹的性質

三、紅黑樹結點定義

四、紅黑樹的操作

1. 插入操作

1.1?插入過程

1.2?調整過程

1.2.1?叔叔節點存在且為紅色

1.2.2?叔叔節點存在且為黑色

1.2.3?叔叔節點不存在

2. 查找操作

2.1 查找邏輯

2.2 算法流程圖?

2.3 使用示例?

五、驗證紅黑樹

1. 中序遍歷驗證

2. 紅黑樹性質驗證

3.?驗證邏輯流程圖?

4. 使用示例

六、紅黑樹 vs AVL樹

1. 核心區別

2. 詳細對比分析

2.1?平衡機制

2.2?時間復雜度

2.3?內存占用

2.4?典型應用場景

3. 選擇建議

4. 性能實測對比

總結

一、紅黑樹的概念

????????紅黑樹?是一種自平衡的二叉搜索樹，它在每個節點上增加了一個存儲位來表示節點的顏色，顏色可以是紅色（Red）或黑色（Black）。

????????通過對任何一條從根到葉子的路徑上各個節點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出兩倍，因而是接近平衡的。

二、紅黑樹的性質

節點顏色 ：每個節點必為紅色或黑色。
根節點顏色 ：根節點始終為黑色。
紅色節點的子節點 ：紅色節點的子節點必為黑色，禁止出現連續紅色節點。
黑色節點數一致性 ：從任一節點到其所有后代葉節點的簡單路徑上，黑色節點數目相同。
葉節點顏色 ：葉節點（空節點）均為黑色。

思考：為什么滿足上面的性質，紅黑樹就能保證其最長路徑中節點個數不會超過最短路徑節點個數的兩倍？

原因：?

????????從性質4可知，紅黑樹中所有從某個節點到其所有后代葉節點的簡單路徑上黑色節點的數目相同。設這個數目為 N，那么最短路徑一定是由 N 個黑色節點構成的路徑，其節點個數為 N。

????????性質3規定，紅色節點的子節點必須是黑色，因此最長路徑只能是由黑色和紅色節點交替出現構成的路徑。在這種情況下，黑色節點和紅色節點的個數相等，最長路徑的節點個數為 2N。

????????因此，紅黑樹的最長路徑的節點個數（2N）不會超過最短路徑節點個數（N）的兩倍。

三、紅黑樹結點定義

// 紅黑樹節點顏色枚舉
enum Colour 
{RED,    // 紅色節點（新增節點默認為紅，減少平衡調整次數）BLACK   // 黑色節點（根節點和葉子節點必須為黑）
};/*** @class RBTreeNode - 紅黑樹節點模板類* @tparam K - 鍵(key)類型，用于節點比較和排序* @tparam V - 值(value)類型，與鍵關聯的存儲數據** @note 每個節點包含父指針、左右子指針、鍵值對數據和顏色標記*/
template<class K, class V>
struct RBTreeNode
{// 節點關系指針RBTreeNode<K, V>* _left;   // 左子節點指針（比當前節點小的子樹）RBTreeNode<K, V>* _right;  // 右子節點指針（比當前節點大的子樹）RBTreeNode<K, V>* _parent; // 父節點指針（用于向上回溯調整）// 節點存儲數據std::pair<K, V> _kv;       // 鍵值對數據（K決定節點位置，V存儲關聯值）Colour _col;               // 節點顏色（維護紅黑樹平衡的關鍵屬性）RBTreeNode(const std::pair<K, V>& kv): _left(nullptr)    // 初始無左子, _right(nullptr)   // 初始無右子, _parent(nullptr)  // 初始無父節點, _kv(kv)          // 存儲鍵值對, _col(RED)        // 默認紅色（后續可能調整）{}
};

思考：在節點的定義中，為什么要將節點的默認顏色給成紅色的？?

原因：?

1. 保持黑高度不變

紅黑樹的黑高度是指從根節點到每個葉子節點路徑上黑色節點的數量，它是一個重要的平衡因子。如果新插入的節點默認是黑色，那么這條路徑的黑高度會增加 1，這會導致樹的平衡被打破，需要進行復雜的調整操作，如重新著色和旋轉等。
而將新節點設置為紅色，不會改變黑高度，因為紅節點的插入不會影響路徑上的黑節點數量，從而減少了調整的復雜度。

2. 避免違反紅黑樹的性質

紅黑樹的一個關鍵性質是不能有兩個連續的紅色節點（即紅 - 紅父 - 子關系）。如果新節點默認是紅色，其父節點可能也是紅色，這會導致違反這一性質，但這種情況相對容易通過一系列旋轉和顏色調整操作來修復。

3. 簡化插入操作的邏輯

在紅黑樹的插入操作中，當新節點是紅色時，主要的處理邏輯集中在處理連續紅色節點的情況，這可以通過較為固定的幾種情況進行調整，如左旋、右旋、顏色交換等。
而如果新節點是黑色，由于黑高度的改變，需要考慮更多復雜的場景和調整策略，使得插入操作的邏輯更加復雜。

????????綜上所述，將新節點的默認顏色設置為紅色，可以更好地保持紅黑樹的黑高度，減少對紅黑樹性質的破壞，同時簡化插入操作的邏輯。

四、紅黑樹的操作

1. 插入操作

????????紅黑樹的插入過程可以分為三個主要步驟：首先，按照二叉搜索樹的規則找到插入位置；其次，將新節點插入樹中；最后，如果插入節點的父節點為紅色，則需要對紅黑樹進行調整，以恢復其性質。

1.1?插入過程

找到插入位置：按照二叉搜索樹的規則，比較新節點的鍵值與當前節點的鍵值，確定新節點插入的位置。
插入新節點：將新節點插入到樹中，并將其顏色默認設置為紅色。
判斷是否需要調整：如果新節點的父節點是黑色，則紅黑樹的性質未被破壞，無需進行調整。如果新節點的父節點是紅色，則可能需要進行調整，因為此時出現了連續的紅色節點，違反了紅黑樹的性質。

1.2?調整過程

1.2.1?叔叔節點存在且為紅色

????????當我們向紅黑樹中插入一個新節點，并且新節點的父節點和叔叔節點都是紅色時，我們可以這樣做來避免出現連續的紅色節點：

1. 改變顏色：

把父節點和叔叔節點都變成黑色。這樣可以消除連續的紅色節點問題。
但是，這樣做會使得父節點和叔叔節點所在的路徑上的黑色節點數量減少一個。
所以，再把祖父節點變成紅色。這樣可以保持每條路徑上黑色節點數量的一致性。

2. 處理祖父節點變紅后的問題：

如果祖父節點是根節點，直接把它變回黑色。這樣，所有路徑的黑色節點數量都增加了一個，紅黑樹的性質得以維持。
如果祖父節點不是根節點，那它現在變成了紅色，可能會和它的父節點（新的祖父節點）形成連續紅色節點的問題。此時，我們需要把原來的祖父節點當作新插入的節點，再次檢查它的父節點顏色。如果父節點還是紅色，根據它新的“叔叔節點”（即祖父節點的兄弟節點）的情況，重復上述的顏色改變和可能的旋轉操作，直到整個樹恢復平衡。

這個過程雖然聽著有點繞，但其實就是通過顏色調整和可能的旋轉，逐步恢復紅黑樹的平衡。

1.2.2?叔叔節點存在且為黑色

????????當我們向紅黑樹中插入一個新節點，并且插入節點的叔叔節點存在且為黑色時，這通常發生在我們已經對情況一進行調整之后。具體來說，這種情況下的當前節點并不是新插入的節點，而是上一次情況一調整過程中涉及的祖父節點。在插入節點之前，紅黑樹的平衡已經被打破，因為叔叔節點的存在且為黑色，導致不同路徑上的黑色節點數目不一致。

????????為了恢復紅黑樹的平衡，我們需要進行旋轉操作。如果當前節點與父節點和祖父節點形成直線關系（即它們在一條直線上），我們需要進行單旋操作。例如，如果父節點是祖父節點的左孩子，而當前節點又是父節點的左孩子，那么我們進行右單旋操作。旋轉后，我們還需要調整顏色，以確保被旋轉子樹的根節點變為黑色，從而恢復紅黑樹的性質。

????????如果當前節點與父節點和祖父節點形成折線關系（即它們不在一條直線上），我們需要進行雙旋操作。例如，如果父節點是祖父節點的左孩子，而當前節點是父節點的右孩子，那么我們進行左右雙旋操作。雙旋操作后，同樣需要調整顏色，使得被旋轉子樹的根節點變為黑色，從而恢復紅黑樹的平衡。

????????這個過程的關鍵在于通過旋轉和顏色調整，重新分配黑色節點，使得每條路徑上的黑色節點數目一致，從而恢復紅黑樹的平衡。旋轉操作后，通常不需要繼續向上調整，因為調整后的子樹已經恢復了平衡。

1.2.3?叔叔節點不存在

????????當我們向紅黑樹中插入一個新節點，并且插入節點的叔叔節點不存在時，這說明當前節點一定是新插入的節點。叔叔節點不存在意味著父節點下面不能再掛黑色節點，否則會導致不同路徑上的黑色節點數目不一致。因此，在這種情況下，我們需要通過旋轉和顏色調整來恢復紅黑樹的平衡。

????????如果當前節點、父節點和祖父節點形成直線關系（即它們在一條直線上），我們需要進行單旋操作。例如，如果父節點是祖父節點的左孩子，而當前節點又是父節點的左孩子，那么我們進行右單旋操作。旋轉后，調整顏色，使得被旋轉子樹的根節點變為黑色，從而恢復紅黑樹的性質。

????????如果當前節點、父節點和祖父節點形成折線關系（即它們不在一條直線上），我們需要進行雙旋操作。例如，如果父節點是祖父節點的左孩子，而當前節點是父節點的右孩子，那么我們進行右左雙旋操作。雙旋操作后，同樣需要調整顏色，使得被旋轉子樹的根節點變為黑色，從而恢復紅黑樹的平衡。

代碼如下：

template<class K, class V>
class RBTree 
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv) {// 空樹情況處理if (_root == nullptr) {_root = new Node(kv);_root->_col = BLACK;  // 根節點必須為黑（紅黑樹性質2）return true;}// ----------------- 標準BST插入邏輯 -----------------Node* parent = nullptr;Node* cur = _root;while (cur) {  // 尋找插入位置parent = cur;if (cur->_kv.first < kv.first) {cur = cur->_right;}else if (cur->_kv.first > kv.first) {cur = cur->_left;}else {return false;  // 鍵已存在，插入失敗}}// 創建新節點（默認顏色為紅色）cur = new Node(kv);cur->_col = RED;     // 新節點初始化為紅色（減少破壞黑高概率）// 鏈接到父節點if (parent->_kv.first < kv.first) {parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;// ---------------- 紅黑樹平衡調整 ----------------// 只有當父節點是紅色時才需要調整（避免連續紅節點）while (parent && parent->_col == RED) {Node* grandfather = parent->_parent;  // 祖父節點必然存在（因父為紅不可能是根）// 父節點是祖父的左孩子if (parent == grandfather->_left) {Node* uncle = grandfather->_right;  // 叔叔節點// Case 1: 叔叔存在且為紅if (uncle && uncle->_col == RED) {/* 顏色翻轉策略（向上傳遞調整）：1. 父和叔變黑2. 祖父變紅3. 將祖父作為新cur繼續向上調整 */parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;          // 向上回溯parent = cur->_parent;      // 更新父節點為祖父的父節點}// Case 2/3: 叔叔不存在或為黑else {// Case 2: cur是父的右孩子（LR型）if (cur == parent->_right) {RotateL(parent);      // 左旋父節點轉為LL型RotateR(grandfather); // 右旋祖父節點cur->_col = BLACK;     // cur設為黑}// Case 3: cur是父的左孩子（LL型）else {RotateR(grandfather); // 右旋祖父parent->_col = BLACK;  // 父變黑}grandfather->_col = RED;  // 祖父變紅（平衡顏色）break;  // 旋轉后子樹平衡，退出循環}}// 父節點是祖父的右孩子（鏡像對稱處理）else {Node* uncle = grandfather->_left;// Case 1: 叔叔存在且為紅（顏色翻轉）if (uncle && uncle->_col == RED) {parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}// Case 2/3: 叔叔不存在或為黑else {// Case 2: cur是父的左孩子（RL型）if (cur == parent->_left) {RotateR(parent);      // 右旋父節點轉為RR型RotateL(grandfather); // 左旋祖父cur->_col = BLACK;     // cur設為黑}// Case 3: cur是父的右孩子（RR型）else {RotateL(grandfather); // 左旋祖父parent->_col = BLACK;  // 父變黑}grandfather->_col = RED;  // 祖父變紅break;}}}_root->_col = BLACK;  // 確保根節點始終為黑（可能因向上調整改變根）return true;}/*** @brief 右旋操作（以parent為旋轉中心）* @param parent 旋轉的中心節點（旋轉后將成為子節點）** 右旋示意圖：*       parent              subL*      /      \            /    \*     subL     C   -->    A   parent*    /   \                     /   \*   A   subLR               subLR   C*/void RotateR(Node* parent) {Node* subL = parent->_left;    // 獲取左子節點subLNode* subLR = subL->_right;    // 獲取subL的右子節點subLR// Step 1: 將subLR掛接到parent的左側parent->_left = subLR;if (subLR) {subLR->_parent = parent;   // 更新subLR的父指針}// Step 2: 將parent變為subL的右子節點subL->_right = parent;Node* ppNode = parent->_parent;  // 記錄原parent的父節點（祖父節點）// Step 3: 更新parent的父指針指向subLparent->_parent = subL;// Step 4: 處理祖父節點的鏈接if (parent == _root) {         // 若parent是根節點_root = subL;              // 更新根為subL_root->_parent = nullptr;  // 根節點的父指針置空}else {                       // 若parent不是根節點if (ppNode->_left == parent) {  // 判斷原parent在祖父的位置ppNode->_left = subL;       // 祖父左指針指向subL}else {ppNode->_right = subL;      // 祖父右指針指向subL}subL->_parent = ppNode;    // 更新subL的父指針}}/*** @brief 左旋操作（以parent為旋轉中心）* @param parent 旋轉的中心節點（旋轉后將成為子節點）** 左旋示意圖：*     parent                subR*    /     \              /     \*   A      subR   -->  parent    C*         /   \         /   \*     subRL    C       A   subRL*/void RotateL(Node* parent) {Node* subR = parent->_right;   // 獲取右子節點subRNode* subRL = subR->_left;     // 獲取subR的左子節點subRL// Step 1: 將subRL掛接到parent的右側parent->_right = subRL;if (subRL) {subRL->_parent = parent;  // 更新subRL的父指針}// Step 2: 將parent變為subR的左子節點subR->_left = parent;Node* ppNode = parent->_parent;  // 記錄原parent的父節點（祖父節點）// Step 3: 更新parent的父指針指向subRparent->_parent = subR;// Step 4: 處理祖父節點的鏈接if (parent == _root) {         // 若parent是根節點_root = subR;              // 更新根為subR_root->_parent = nullptr;  // 根節點的父指針置空}else {                       // 若parent不是根節點if (ppNode->_left == parent) {  // 判斷原parent在祖父的位置ppNode->_left = subR;       // 祖父左指針指向subR}else {ppNode->_right = subR;      // 祖父右指針指向subR}subR->_parent = ppNode;    // 更新subR的父指針}}
private:Node* _root = nullptr;
};