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

3.2 搜索

与普通二叉搜索树相同，无需使用颜色信息，时间复杂度 O(log n)。

3.3 插入逻辑

1. 按 BST 规则插入新结点，默认标记为红色。
2. 若父结点为黑色，无需调整。
3. 若父结点为红色，需修复违反的性质（无连续红结点）：
   • 变色：叔叔结点存在且为红色，父叔变黑，祖父变红，继续向上处理。
   • 旋转 + 变色：叔叔不存在或为黑色，根据左右情况执行单旋或双旋。

3.4 插入代码实现

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.5 查找

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.6 验证

检查根是否为黑、无连续红结点、每条路径黑结点数量相等。

3.7 删除

删除黑色结点可能破坏黑高度平衡，需引入双重黑色结点并通过旋转和变色消除。具体逻辑较复杂，涉及兄弟结点颜色判断及多种旋转组合。

3.8 模拟实现

完整类实现包含左旋、右旋、插入修复、中序遍历等功能，确保红黑树性质维持。

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 将二叉搜索树变平衡

通过中序遍历转为有序数组，再递归构建平衡树。

4.3 判断是否为平衡二叉树

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

4.4 二叉搜索树迭代器

使用中序遍历结果数组模拟迭代器行为。

4.5 二叉树中的最大路径和

DFS 回溯，计算当前节点作为最高点的路径和，更新全局最大值。