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

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

1. 最短路径是全黑路径，长度为黑高度 bh。
2. 由于不能有两个连续红节点，最长路径由一黑一红交替组成，长度约为 2*bh。
3. 因此，任意路径长度 x 满足 bh ≤ h ≤ 2*bh。

2.4 红黑树的效率

相比 AVL 树，红黑树对平衡的控制没那么严格，插入相同数量的结点时，旋转次数通常更少。这使得它在需要频繁插入/删除且查询性能要求稳定的场景下表现优异，例如 C++ STL 中的 std::map 和 std::set。

3. 红黑树的实现

3.1 红黑树的结构

我们需要定义节点结构，包含键值对、左右指针、父指针以及颜色属性。为了简化边界处理，通常使用哨兵节点（Sentinel Node）代替 NULL。

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

enum Color { RED, BLACK };

template<typename K, typename V>
struct RBNode {
    K key;
    V value;
    Color color;
    RBNode* parent;
    RBNode* left;
    RBNode* right;

    RBNode(const K& k, const V& v, Color c = RED)
        : key(k), value(v), color(c), parent(nullptr), left(nullptr), right(nullptr) {}
};

template<typename K, typename V>
class RBTree {
private:
    using Node = RBNode<K, V>;
    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;
    }

    // 二叉搜索树插入逻辑
    Node* bst_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 curr;
            }
        }
        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;
        return new_node;
    }

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

    ~RBTree() {
        delete nil;
    }

    void insert(const K& key, const V& value) {
        Node* new_node = bst_insert(key, value);
        if (new_node->color == RED) {
            insert_fixup(new_node);
        }
    }

    Node* find(const K& key) const {
        Node* curr = root;
        while (curr != nil) {
            if (key < curr->key) curr = curr->left;
            else if (key > curr->key) curr = curr->right;
            else return curr;
        }
        return nullptr;
    }

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

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

3.2 红黑树的搜索

红黑树本质是二叉搜索树，搜索过程不需要颜色信息，直接沿路径向下查找即可。时间复杂度为 O(log n)。

3.3 红黑树的插入

插入新节点时，默认标记为红色。如果父节点是黑色，则无需调整；如果父节点是红色，则违反性质，需要通过变色或旋转来修复。主要分为三种情况：

1. 叔叔节点为红色：变色处理，将祖父节点变为红色，继续向上检查。
2. 叔叔节点为黑色（单旋）：根据节点位置进行单旋并变色。
3. 叔叔节点为黑色（双旋）：先旋转调整为单旋情况，再处理。

3.4 红黑树的验证

验证红黑树是否合法主要检查两点：

1. 根节点是否为黑色。
2. 任意路径上的黑色节点数量是否一致，且无连续红色节点。

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nil) {
        return blackNum == refNum;
    }
    if (root->color == RED && root->parent->color == RED) {
        return false;
    }
    if (root->color == BLACK) blackNum++;
    return Check(root->left, blackNum, refNum) && 
           Check(root->right, blackNum, refNum);
}

3.5 红黑树的删除

删除操作较为复杂。如果被删节点是红色，直接删除不影响黑高度；如果是黑色，则需要重新平衡。通常将删除后的空位视为'双重黑色'，通过旋转和变色消除双重黑色，恢复红黑树特性。

4. 相关 OJ 题解析

4.1 二叉搜索树中的插入操作

这是 BST 的基础操作，找到合适位置插入即可。

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;
    }
};

4.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);
    }
};

4.3 判断是否为平衡二叉树

递归计算高度，若子树不平衡则返回 -1。

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.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(); }
};

4.5 二叉树中的最大路径和

DFS 遍历，计算以当前节点为最高点的路径和，更新全局最大值。

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;
    }
};

通过以上实现与练习，我们可以更深入地理解平衡二叉搜索树的核心机制及其在实际开发中的应用。