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

2.1 红黑树的性质

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 所有叶子节点（NIL 节点）都是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的（即不存在连续的两个红色节点）。
5. 对每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（黑高度）。

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

• 最短路径：全由黑色节点组成，长度为黑高度 bh。
• 最长路径：红黑交替出现，由于不能有两个连续红节点，最长路径长度最多为 2 * bh。
• 结论：任意路径长度 h 满足 bh <= h <= 2 * bh。因此，红黑树的高度 h <= 2 log₂(n+1)，保证了增删查改的时间复杂度为 O(log n)。

2.3 红黑树的效率

相比 AVL 树，红黑树对平衡的控制较宽松，插入时的旋转次数更少，更适合写多读少的场景。AVL 树虽然查找更快，但维护平衡的开销较大。两者在最坏情况下的查找性能均为 O(log n)。

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 搜索操作

红黑树的搜索与普通二叉搜索树完全一致，无需考虑颜色信息。

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 插入逻辑

插入新节点时，默认将其设为红色。如果父节点是黑色，则无需调整；如果父节点是红色，则违反性质，需进行修复。

3.3.1 变色处理

若叔叔节点存在且为红色，则将父节点和叔叔节点变黑，祖父节点变红，并将祖父节点作为当前节点继续向上检查。

3.3.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;
            // 情况 1：叔叔存在且为红 -> 变色
            if (uncle && uncle->_col == RED) {
                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;
}

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

3.6 删除操作

删除操作较为复杂。如果被删节点是红色，直接删除即可。如果是黑色，删除后会导致黑高度减少，需要通过旋转和变色恢复平衡。常见的处理思路是将被删节点替换为双重黑色节点，然后通过多种情况（兄弟节点颜色、兄弟子节点颜色）进行旋转消除双重黑色。

4. 相关练习

为了巩固理解，可以参考以下经典题目：

1. 二叉搜索树中的插入操作：练习 BST 的基本插入逻辑。
2. 判断是否为平衡二叉树：验证树的高度差是否符合 AVL 标准。
3. 二叉搜索树迭代器：实现中序遍历的迭代器。
4. 二叉树中的最大路径和：考察递归与动态规划思想。

这些题目有助于深入理解树结构的遍历、平衡性以及路径计算。