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

• 最短路径：全为黑色节点，长度为黑高度 bh。
• 最长路径：红黑相间，长度为 2 * bh。
• 由于不存在连续红节点，任何路径长度都在 [bh, 2*bh] 之间。

2.4 红黑树的效率

相比 AVL 树，红黑树对平衡的控制较宽松，插入时的旋转次数更少，更适合写多读少的场景。AVL 树在纯搜索场景下略优，但两者整体效率处于同一档次。

3. 红黑树的实现

3.1 红黑树的结构

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

#pragma once
#include <utility>

enum Color { RED, BLACK };

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

    RBTreeNode(const std::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 红黑树的插入

插入分为两步：按 BST 规则找到位置并插入，然后修复红黑树性质。

1. 空树：新节点设为黑色作为根。
2. 非空树：新节点设为红色。若父节点为黑色，无需调整；若父节点为红色，则违反性质，需根据叔叔节点颜色进行调整。

调整策略：

• 变色：叔叔节点存在且为红色 -> 父、叔变黑，祖父变红 -> 继续向上处理。
• 旋转：叔叔节点不存在或为黑色 -> 根据相对位置进行单旋或双旋，并配合变色。

3.4 红黑树的插入代码实现

以下是核心的插入与修复逻辑，包含了旋转函数和颜色调整。

// 右旋
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;
    }
}

bool Insert(const std::pair<K, V>& kv) {
    if (_root == nullptr) {
        _root = new RBTreeNode<K, V>(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 RBTreeNode<K, V>(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) {
                // 情况 1: 变色
                parent->_col = BLACK;
                uncle->_col = BLACK;
                grandfather->_col = RED;
                cur = grandfather;
                parent = cur->_parent;
            } else {
                // 情况 2/3: 旋转 + 变色
                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 红黑树的验证

验证需要检查三条性质：根为黑、无连续红、黑高度一致。

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

bool IsBalance() {
    if (_root == nullptr) return true;
    if (_root->_col == RED) return false;
    
    int refNum = 0;
    Node* leftMost = _root;
    while (leftMost) {
        if (leftMost->_col == BLACK) ++refNum;
        leftMost = leftMost->_left;
    }
    return Check(_root, 0, refNum);
}

3.6 红黑树的删除

删除逻辑较为复杂，涉及双重黑色的处理。若删除的是红色节点，直接移除即可；若删除的是黑色节点，会导致黑高度减少，需引入'额外黑色'概念并通过旋转和变色消除。

具体包括：

• 兄弟节点为红色：交换颜色并旋转。
• 兄弟节点为黑色：根据侄子节点颜色进行变色或旋转，将双重黑色向上传递或消除。

(注：删除实现篇幅较长，核心思路与插入类似，重点在于维护黑高度平衡)

4. 相关算法题实战

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

1. 二叉搜索树中的插入操作：考察基本的 BST 插入逻辑。
2. 将二叉搜索树变平衡：考察如何构建平衡树，通常使用中序遍历转数组再递归构建。
3. 判断是否为平衡二叉树：考察树的高度计算与平衡因子判断。
4. 二叉搜索树迭代器：考察中序遍历的非递归实现。
5. 二叉树中的最大路径和：考察树形 DP 与递归回溯。

这些题目涵盖了从基础插入到复杂平衡调整的各个层面，建议结合手写代码加深理解。