C++ 伸展树与红黑树原理及代码实现

3. 红黑树的实现

3.1 结构定义

enum Color { RED, BLACK };

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

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

3.2 插入逻辑

插入新节点时默认为红色。若父节点为黑色，无需调整；若父节点为红色，则违反性质，需根据叔叔节点的颜色进行调整：

1. 变色：叔叔节点存在且为红色，父节点和叔叔变黑，祖父变红，继续向上处理。
2. 旋转 + 变色：叔叔节点不存在或为黑色，通过单旋或双旋调整结构并修正颜色。

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _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;
    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 (grandfather->_left == parent) {
            Node* uncle = grandfather->_right;
            if (uncle && uncle->_col == RED) {
                // 变色
                parent->_col = BLACK;
                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 = BLACK;
                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.3 查找与验证

查找与普通 BST 一致。验证时需检查根节点颜色、无连续红节点、以及任意路径黑节点数量是否一致。

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

4. 相关算法题实践

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