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

红黑树通过颜色约束间接实现平衡。在极端情况下，最短路径全为黑色，最长路径一黑一红交替，长度比为 2:1。这使得其性能稳定，且在实际工程中表现优异。

3. 红黑树的实现

3.1 结构定义

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

enum Color { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    pair<K, V> _kv;
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    Color _col;

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

3.2 搜索

红黑树搜索与普通二叉搜索树一致，无需考虑颜色信息，时间复杂度为 O(log 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 插入逻辑

插入新节点时遵循 BST 规则，默认标记为红色。若父节点为黑色，则无需调整；若父节点为红色，则违反性质，需修复。

修复策略主要分两种情况：

1. 叔叔节点存在且为红色：变色处理（父、叔变黑，祖父变红），然后继续向上检查祖父节点。
2. 叔叔节点不存在或为黑色：旋转 + 变色处理。根据当前节点与父节点的位置关系，分为左单旋、右单旋或左右/右左双旋。

3.4 插入代码实现

以下是完整的插入与修复逻辑，包含旋转函数。

bool Insert(const 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) {
                // 情况 1: 变色
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况 2: 旋转 + 变色
                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;
}

// 右旋辅助函数
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 IsBalance() {
    if (!_root) return true;
    if (_root->_col == RED) return false;
    int blackRef = 0;
    Node* leftMost = _root;
    while (leftMost) {
        if (leftMost->_col == BLACK) ++blackRef;
        leftMost = leftMost->_left;
    }
    return Check(_root, 0, blackRef);
}

bool Check(Node* cur, int blackNum, const int blackNumRef) {
    if (!cur) {
        if (blackNum != blackNumRef) return false;
        return true;
    }
    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);
}

4. 相关算法题实践

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

动态规划思路，计算以当前节点为最高点的路径和。

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

通过上述内容，我们完成了对伸展树和红黑树的理论梳理与代码落地。实际开发中，建议优先使用标准库提供的容器，但理解其底层原理对于解决复杂数据结构和性能调优问题至关重要。