C++ 伸展树与红黑树详解及核心实现

2.3 为什么最长路径不超过最短路径的 2 倍？

• 最短路径：全由黑色节点组成，长度为黑高度 bh。
• 最长路径：红黑交替出现，长度最多为 2 * bh。
• 结论：任意路径长度 x 满足 $bh \leqslant h \leqslant 2*bh$，保证了整体平衡性。

2.4 红黑树的效率

红黑树通过颜色约束间接控制平衡，相比 AVL 树，其插入时的旋转次数更少，维护成本更低，适合写操作频繁的场景。尽管最坏高度略高于 AVL 树，但性能差异在实际工程中通常可忽略。

3. 红黑树的实现

3.1 红黑树结构

我们需要定义节点结构，包含键值对、左右指针、父指针以及颜色属性。

#pragma once
#include <utility>

template<class K, class V>
struct RBTreeNode {
    std::pair<K, V> _kv;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    enum Color { RED, BLACK } _col;

    RBTreeNode(const std::pair<K, V>& kv)
        : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};

3.2 红黑树的搜索

搜索逻辑与普通二叉搜索树一致，无需关心颜色信息。由于树高限制在 $2\log_2 n$，搜索效率稳定。

Node* Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < key) cur = cur->_right;
        else if (cur->_kv.first > key) cur = cur->_left;
        else return cur;
    }
    return nullptr;
}

3.3 红黑树的插入

插入流程分为两步：

1. 按 BST 规则插入：新节点默认为红色。
2. 修复红黑性质：若父节点为红色，则违反性质，需通过变色或旋转修复。

插入修复策略

假设当前节点为 c，父节点为 p，祖父节点为 g，叔叔节点为 u。

• 情况 1：叔叔存在且为红

  • 处理：p 和 u 变黑，g 变红，c 更新为 g，继续向上检查。
  • 分析：保持黑高度不变，解决连续红节点问题。

• 情况 2：叔叔不存在或为黑

  • 左左/右右（单旋）：以 g 为轴旋转，p 变黑，g 变红。
  • 左右/右左（双旋）：先以 p 为轴旋转，再以 g 为轴旋转，c 变黑，g 变红。

bool Insert(const std::pair<K, V>& kv) {
    if (!_root) {
        _root = new Node(kv);
        _root->_col = BLACK;
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_kv.first < kv.first) {
            parent = cur; cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
            parent = cur; cur = cur->_left;
        } else return false; // 已存在
    }

    cur = new Node(kv);
    cur->_col = RED;
    cur->_parent = parent;
    if (parent->_kv.first < kv.first) parent->_right = cur;
    else parent->_left = cur;

    while (parent && parent->_col == RED) {
        Node* grandfather = parent->_parent;
        if (grandfather->_left == parent) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                // 变色
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 旋转 + 变色
                if (cur == parent->_left) {
                    RotateR(grandfather);
                    parent->_col = BLACK; grandfather->_col = RED;
                } else {
                    RotateL(parent); RotateR(grandfather);
                    cur->_col = BLACK; grandfather->_col = RED;
                }
                break;
            }
        } else {
            Node* uncle = grandfather->_left;
            if (uncle && uncle->_col == RED) {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                if (cur == parent->_right) {
                    RotateL(grandfather);
                    parent->_col = BLACK; grandfather->_col = RED;
                } else {
                    RotateR(parent); RotateL(grandfather);
                    cur->_col = BLACK; grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

3.4 旋转辅助函数

旋转逻辑与 AVL 树类似，需注意更新父指针和根节点引用。

void RotateR(Node* parent) {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR) subLR->_parent = parent;
    
    Node* parentParent = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;

    if (parent == _root) {
        _root = subL; subL->_parent = nullptr;
    } else {
        if (parentParent->_left == parent) parentParent->_left = subL;
        else parentParent->_right = subL;
        subL->_parent = parentParent;
    }
}

void RotateL(Node* parent) {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL) subRL->_parent = parent;

    Node* parentParent = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;

    if (parent == _root) {
        _root = subR; subR->_parent = nullptr;
    } else {
        if (parentParent->_left == parent) parentParent->_left = subR;
        else parentParent->_right = subR;
        subR->_parent = parentParent;
    }
}

3.5 红黑树的验证

验证需检查三个核心性质：根为黑、无连续红节点、黑高度一致。

bool Check(Node* cur, int blackNum, const int blackNumRef) {
    if (!cur) {
        return blackNum == blackNumRef;
    }
    if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) {
        return false;
    }
    if (cur->_col == BLACK) ++blackNum;
    return Check(cur->_left, blackNum, blackNumRef) && 
           Check(cur->_right, blackNum, blackNumRef);
}

bool IsBalance() {
    if (!_root) return true;
    if (_root->_col == RED) return false;
    int refNum = 0;
    Node* leftMost = _root;
    while (leftMost) {
        if (leftMost->_col == BLACK) ++refNum;
        leftMost = leftMost->_left;
    }
    return Check(_root, 0, refNum);
}

3.6 完整模拟实现示例

以下是一个基于哨兵节点（Sentinel Node）的更稳健实现，简化了边界处理。

#include <iostream>
#include <algorithm>
using namespace std;

template<typename K, typename V>
class RBTree {
private:
    struct Node {
        K key;
        V value;
        enum Color { RED, BLACK } color;
        Node* parent;
        Node* left;
        Node* right;
        Node(const K& k, const V& v, Color c = RED)
            : key(k), value(v), color(c), parent(nullptr), left(nullptr), right(nullptr) {}
    };

    Node* root;
    Node* nil; // 哨兵节点

    void left_rotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        if (y->left != nil) y->left->parent = x;
        y->parent = x->parent;
        if (x->parent == nil) root = y;
        else if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
        y->left = x; x->parent = y;
    }

    void right_rotate(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        if (x->right != nil) x->right->parent = y;
        x->parent = y->parent;
        if (y->parent == nil) root = x;
        else if (y == y->parent->left) y->parent->left = x;
        else y->parent->right = x;
        x->right = y; y->parent = x;
    }

    void insert_fixup(Node* z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                Node* uncle = z->parent->parent->right;
                if (uncle->color == RED) {
                    z->parent->color = BLACK;
                    uncle->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        left_rotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    right_rotate(z->parent->parent);
                }
            } else {
                Node* uncle = z->parent->parent->left;
                if (uncle->color == RED) {
                    z->parent->color = BLACK;
                    uncle->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        right_rotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    left_rotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

public:
    RBTree() {
        nil = new Node(K(), V(), BLACK);
        root = nil;
    }

    ~RBTree() {
        delete nil;
    }

    void insert(const K& key, const V& value) {
        Node* parent = nil;
        Node* curr = root;
        while (curr != nil) {
            parent = curr;
            if (key < curr->key) curr = curr->left;
            else if (key > curr->key) curr = curr->right;
            else { curr->value = value; return; }
        }
        Node* new_node = new Node(key, value, RED);
        new_node->parent = parent;
        new_node->left = nil;
        new_node->right = nil;
        if (parent == nil) root = new_node;
        else if (key < parent->key) parent->left = new_node;
        else parent->right = new_node;

        if (new_node->color == RED) insert_fixup(new_node);
    }

    void inorder() {
        inorder_traversal(root);
        cout << endl;
    }

private:
    void inorder_traversal(Node* node) {
        if (node == nil) return;
        inorder_traversal(node->left);
        cout << "[" << node->key << ":" << node->value << "," 
             << (node->color == RED ? "红" : "黑") << "] ";
        inorder_traversal(node->right);
    }
};

int main() {
    RBTree<int, string> rb_tree;
    rb_tree.insert(10, "A"); rb_tree.insert(20, "B");
    rb_tree.insert(30, "C"); rb_tree.insert(15, "D");
    rb_tree.inorder();
    return 0;
}

4. 相关 OJ 题实战

掌握理论后，建议通过 LeetCode 经典题目巩固理解：

1. 二叉搜索树中的插入操作

   class Solution {
   public:
       TreeNode* insertIntoBST(TreeNode* root, int val) {
           if (!root) return new TreeNode(val);
           TreeNode* cur = root;
           while (cur) {
               if (val < cur->val) {
                   if (!cur->left) { cur->left = new TreeNode(val); break; }
                   cur = cur->left;
               } else {
                   if (!cur->right) { cur->right = new TreeNode(val); break; }
                   cur = cur->right;
               }
           }
           return root;
       }
   };
   

2. 将二叉搜索树变平衡

   class Solution {
   private:
       void inorder(TreeNode* root, vector<int>& nums) {
           if (!root) return;
           inorder(root->left, nums); nums.push_back(root->val);
           inorder(root->right, nums);
       }
       TreeNode* build(const vector<int>& nums, int start, int end) {
           if (start > end) return nullptr;
           int mid = start + (end - start) / 2;
           TreeNode* node = new TreeNode(nums[mid]);
           node->left = build(nums, start, mid - 1);
           node->right = build(nums, mid + 1, end);
           return node;
       }
   public:
       TreeNode* balanceBST(TreeNode* root) {
           vector<int> nums; inorder(root, nums);
           return build(nums, 0, nums.size() - 1);
       }
   };
   

3. 判断是否为平衡二叉树

   class Solution {
   private:
       int getHeight(TreeNode* node) {
           if (!node) return 0;
           int leftHeight = getHeight(node->left);
           if (leftHeight == -1) return -1;
           int rightHeight = getHeight(node->right);
           if (rightHeight == -1) return -1;
           if (abs(leftHeight - rightHeight) > 1) return -1;
           return max(leftHeight, rightHeight) + 1;
       }
   public:
       bool isBalanced(TreeNode* root) {
           return getHeight(root) != -1;
       }
   };
   

4. 二叉搜索树迭代器

   class BSTIterator {
   private:
       vector<int> inorderList;
       int idx;
       void inorder(TreeNode* node) {
           if (!node) return;
           inorder(node->left); inorderList.push_back(node->val);
           inorder(node->right);
       }
   public:
       BSTIterator(TreeNode* root) {
           inorder(root); idx = 0;
       }
       int next() { return inorderList[idx++]; }
       bool hasNext() { return idx < inorderList.size(); }
   };
   

5. 二叉树中的最大路径和

   class Solution {
   private:
       int helper(TreeNode* node, int& maxSum) {
           if (!node) return 0;
           int leftContribution = max(helper(node->left, maxSum), 0);
           int rightContribution = max(helper(node->right, maxSum), 0);
           int currentPathSum = node->val + leftContribution + rightContribution;
           maxSum = max(maxSum, currentPathSum);
           return node->val + max(leftContribution, rightContribution);
       }
   public:
       int maxPathSum(TreeNode* root) {
           int maxSum = INT_MIN;
           helper(root, maxSum);
           return maxSum;
       }
   };
   

数据结构的学习永无止境，希望这些内容能为你的技术栈添砖加瓦。