平衡二叉搜索树之 红黑 树的模拟实现【C++】

当然可以！下面是一个红黑树（Red-Black Tree）的C++模拟实现教程，包括红黑树的基本概念、节点结构、插入操作、颜色修复，以及完整代码。代码风格清晰，方便你学习和后续扩展。

🧠 一、红黑树基本概念

红黑树是一种自平衡的二叉搜索树，相比 AVL 树，它更适合用于插入频繁的场景，如 C++ STL 中的 std::map、std::set 就是基于红黑树实现的。

✅ 红黑树的性质：

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（空节点）是黑色（我们用 nullptr 表示）。
4. 红色节点不能连续（即红色节点不能有红色子节点）。
5. 从任意节点到其所有后代叶节点的路径上，黑色节点数量相同（黑高一致）。

🧱 二、节点结构设计

enum Color { RED, BLACK };

template <typename T>
struct RBNode {
    T data;
    Color color;
    RBNode* left;
    RBNode* right;
    RBNode* parent;

    RBNode(T val)
        : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

⚙️ 三、核心类定义

template <typename T>
class RBTree {
private:
    RBNode<T>* root;

    void rotateLeft(RBNode<T>*&);
    void rotateRight(RBNode<T>*&);
    void fixViolation(RBNode<T>*&);

public:
    RBTree() : root(nullptr) {}

    void insert(const T& data);
    void inorder(); // 可视化用
    void inorderHelper(RBNode<T>* node);
};

🔁 四、插入与自平衡修复

✅ 插入操作（BST插入 + fixViolation）

template <typename T>
void RBTree<T>::insert(const T& data) {
    RBNode<T>* node = new RBNode<T>(data);
    RBNode<T>* y = nullptr;
    RBNode<T>* x = root;

    while (x != nullptr) {
        y = x;
        if (node->data < x->data)
            x = x->left;
        else
            x = x->right;
    }

    node->parent = y;
    if (y == nullptr)
        root = node;
    else if (node->data < y->data)
        y->left = node;
    else
        y->right = node;

    fixViolation(node);
}

✅ 左旋 & 右旋

template <typename T>
void RBTree<T>::rotateLeft(RBNode<T>*& x) {
    RBNode<T>* y = x->right;
    x->right = y->left;

    if (y->left != nullptr)
        y->left->parent = x;

    y->parent = x->parent;

    if (x->parent == nullptr)
        root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x;
    x->parent = y;
}

template <typename T>
void RBTree<T>::rotateRight(RBNode<T>*& x) {
    RBNode<T>* y = x->left;
    x->left = y->right;

    if (y->right != nullptr)
        y->right->parent = x;

    y->parent = x->parent;

    if (x->parent == nullptr)
        root = y;
    else if (x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;

    y->right = x;
    x->parent = y;
}

✅ 颜色修复逻辑（fixViolation）

template <typename T>
void RBTree<T>::fixViolation(RBNode<T>*& z) {
    while (z->parent != nullptr && z->parent->color == RED) {
        RBNode<T>* gp = z->parent->parent;

        if (z->parent == gp->left) {
            RBNode<T>* uncle = gp->right;
            if (uncle && uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                gp->color = RED;
                z = gp;
            } else {
                if (z == z->parent->right) {
                    z = z->parent;
                    rotateLeft(z);
                }
                z->parent->color = BLACK;
                gp->color = RED;
                rotateRight(gp);
            }
        } else {
            RBNode<T>* uncle = gp->left;
            if (uncle && uncle->color == RED) {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                gp->color = RED;
                z = gp;
            } else {
                if (z == z->parent->left) {
                    z = z->parent;
                    rotateRight(z);
                }
                z->parent->color = BLACK;
                gp->color = RED;
                rotateLeft(gp);
            }
        }
    }
    root->color = BLACK;
}

🧪 五、测试示例

int main() {
    RBTree<int> tree;

    tree.insert(10);
    tree.insert(18);
    tree.insert(7);
    tree.insert(15);
    tree.insert(16);

    std::cout << "中序遍历：" << std::endl;
    tree.inorder();
    return 0;
}

✅ 中序遍历（可选实现）

template <typename T>
void RBTree<T>::inorder() {
    inorderHelper(root);
    std::cout << std::endl;
}

template <typename T>
void RBTree<T>::inorderHelper(RBNode<T>* node) {
    if (!node) return;
    inorderHelper(node->left);
    std::cout << node->data << (node->color == RED ? "(R) " : "(B) ");
    inorderHelper(node->right);
}

📦 六、扩展方向

✅ 七、小结

如果你需要我提供完整可运行项目结构，或者想要一个可视化演示红黑树结构的图形界面（基于 Qt 或 SFML），欢迎告诉我，我可以帮你补充上！是否也要我做成一个 GitHub 项目模板？