红黑树详解：核心规则与 C++ 实战实现

• 若 cur 是 parent 的右孩子，但 parent 是 grandfather 的左孩子（左右），先对 parent 左旋，再对 grandfather 右旋。
• 反之亦然（右左）。
• 旋转完成后，将原 cur 位置设为黑色，grandfather 设为红色。

C++ 代码实现

下面是一个精简的红黑树模板实现，包含了节点定义、插入逻辑及旋转函数。

#include <iostream>
#include <vector>
using namespace std;

enum Colour { RED, BLACK };

template<class T>
struct RBTreeNode {
    T _data;
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;

    RBTreeNode(const T& data) : _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};

template<class K, class T, class KeyOfT>
class RBTree {
    typedef RBTreeNode<T> Node;
public:
    bool Insert(const T& data) {
        if (_root == nullptr) {
            _root = new Node(data);
            _root->_col = BLACK;
            return true;
        }

        KeyOfT kot;
        Node* parent = nullptr;
        Node* cur = _root;

        // 1. 找到插入位置
        while (cur) {
            if (kot(cur->_data) < kot(data)) {
                parent = cur;
                cur = cur->_right;
            } else if (kot(cur->_data) > kot(data)) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false; // 已存在
            }
        }

        // 2. 插入新节点（默认为红色）
        cur = new Node(data);
        cur->_col = RED;
        if (kot(parent->_data) < kot(data)) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        cur->_parent = parent;

        // 3. 修复红黑树性质
        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;
    }

    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

    int Height() {
        return _Height(_root);
    }

    int Size() {
        return _Size(_root);
    }

    Node* Find(const K& key) {
        KeyOfT kot;
        Node* cur = _root;
        while (cur) {
            if (kot(cur->_data) < key) {
                cur = cur->_right;
            } else if (kot(cur->_data) > key) {
                cur = cur->_left;
            } else {
                return cur;
            }
        }
        return nullptr;
    }

private:
    int _Size(Node* root) {
        return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
    }

    int _Height(Node* root) {
        if (root == nullptr) return 0;
        int leftHeight = _Height(root->_left);
        int rightHeight = _Height(root->_right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_data << " ";
        _InOrder(root->_right);
    }

    void RotateR(Node* parent) {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        
        Node* ppnode = parent->_parent;
        subL->_right = parent;
        parent->_parent = subL;

        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (ppnode->_left == parent) {
                ppnode->_left = subL;
            } else {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
    }

    void RotateL(Node* parent) {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;

        Node* ppnode = parent->_parent;
        subR->_left = parent;
        parent->_parent = subR;

        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (ppnode->_left == parent) {
                ppnode->_left = subR;
            } else {
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
    }

private:
    Node* _root = nullptr;
};

查找与检查

查找：遵循二叉搜索树的标准逻辑，从根节点开始比较，向左或向右移动，平均时间复杂度为 $O(\log N)$。

检查：验证红黑树是否合法，主要关注四条核心规则：根节点是否为黑、是否有连续红节点、每条路径的黑高是否一致。实际工程中通常配合单元测试确保插入删除后的平衡性。