C++ 红黑树原理与实现详解

节点结构定义

红黑树的基本节点结构包括键值对、左右子树指针、父节点指针以及颜色属性。

enum Colour { RED, BLACK };

template<class K, class V>
struct RBTreeNode {
    pair<K, V> _kv;           // 存储键值对
    RBTreeNode<K, V>* _left;  // 左子树
    RBTreeNode<K, V>* _right; // 右子树
    RBTreeNode<K, V>* _parent;// 父节点
    Colour _col;              // 颜色属性

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

每个节点不仅包含数据，还通过 _parent 指针方便向上回溯调整颜色，这是实现旋转和修复的关键。

插入操作实现

插入操作分为两步：首先按二叉搜索树规则找到位置插入新节点，然后将新节点设为红色并修复可能破坏的规则。

为什么新节点默认设为红色？因为如果设为黑色，会直接增加某条路径的黑色节点数，违反规则 4，修复成本更高；而设为红色只可能违反规则 3（连续红色），相对容易处理。

修复逻辑主要分两种情况：

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 (parent == grandfather->_left) {
            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;
}

这段代码展示了插入时的核心修复逻辑。关键点在于通过循环不断向上检查，一旦遇到红色父节点就尝试修复，直到根节点或不再违反规则为止。

查找操作

查找操作和普通二叉搜索树类似，利用红黑树的平衡性，时间复杂度稳定在 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;
}

删除操作说明

删除操作比插入更复杂。当删除的是黑色节点时，可能会破坏黑色高度平衡，需要执行复杂的旋转和变色来恢复。尽管删除操作逻辑繁琐，但其时间复杂度同样是 O(log N)。这里不再展开具体实现，建议查阅《算法导论》或《STL 源码剖析》获取完整推导。

验证函数

为了验证红黑树的正确性，我们需要递归检查是否满足四条基本规则。可以通过前序遍历每一条路径，检查节点颜色和黑色节点数量是否符合要求。

bool Check(Node* root, int blackNum, const int refNum) {
    if (root == nullptr) {
        if (refNum != blackNum) {
            cout << "存在黑色结点数量不相等的路径" << endl;
            return false;
        }
        return true;
    }
    if (root->_col == RED && root->_parent->_col == RED) {
        cout << root->_kv.first << "存在连续的红色结点" << endl;
        return false;
    }
    if (root->_col == BLACK) {
        blackNum++;
    }
    return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}

通过这个检查函数，我们能够验证树的结构是否符合红黑树的规则。

总结

红黑树通过简单的颜色规则和旋转操作保证了树的平衡性，确保了查找、插入和删除操作的时间复杂度始终为 O(log N)。虽然插入和删除的实现细节较多，但它的高效性和稳定性使其成为许多应用中不可或缺的数据结构。掌握红黑树的插入逻辑，对于理解底层容器如 std::map 的工作原理非常有帮助。