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

这意味着红黑树的增删查改最坏时间复杂度均为 O(log n)。相比 AVL 树，红黑树对平衡的控制较宽松，插入时的旋转次数更少，更适合写多读少的场景。

3. 红黑树的实现

3.1 结构与搜索

红黑树继承自二叉搜索树，搜索逻辑完全一致，无需关心颜色信息。

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.2 插入与修复

插入新节点默认设为红色。若父节点为黑色，则无冲突；若父节点为红色，则违反性质，需进行变色或旋转修复。

修复逻辑：

1. 叔叔节点为红：父、叔变黑，祖父变红，继续向上检查。
2. 叔叔节点为黑：根据当前节点位置进行单旋或双旋，并调整颜色。

bool Insert(const pair<K, V>& kv) {
    if (!_root) {
        _root = new Node(kv); _root->_col = BLACK; return true;
    }
    // ... 标准 BST 插入逻辑 ...
    cur->_col = RED;
    
    // 修复红黑树性质
    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 {
            // 对称逻辑...
        }
    }
    _root->_col = BLACK;
    return true;
}

3.3 验证与删除

验证时需检查根节点颜色、无连续红节点、以及任意路径黑节点数量是否一致。删除操作比插入更复杂，涉及双重黑色节点的消除，通常通过旋转和颜色交换将'额外黑色'向上传递或吸收。

4. 相关 OJ 实战

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

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 判断是否为平衡二叉树

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 二叉树中的最大路径和

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