通过C++实践深入探讨红黑树的性质

红黑树是一种自平衡二叉搜索树，它在插入和删除元素时能够保持树的平衡，从而保证了树的查找、插入和删除操作的时间复杂度都是O(logn)。红黑树有以下几个性质：

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

下面是一个简单的C++实现红黑树的例子：

#include 
#include 

enum Color { RED, BLACK };

template 
struct Node {
    T data;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

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

template 
class RedBlackTree {
public:
    RedBlackTree() : root(nullptr) {}

    void insert(T data) {
        Node* node = new Node(data);
        insertNode(node);
        fixInsert(node);
    }

    void printInorder() {
        printInorderHelper(root);
        std::cout << std::endl;
    }

private:
    Node* root;

    void insertNode(Node* node) {
        Node* temp = nullptr;
        Node* current = root;

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

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

    void fixInsert(Node* node) {
        while (node != root && node->parent->color == RED) {
            if (node->parent == node->parent->parent->left) {
                Node* uncle = node->parent->parent->right;
                if (uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->right) {
                        node = node->parent;
                        leftRotate(node);
                    }
                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    rightRotate(node->parent->parent);
                }
            } else {
                Node* uncle = node->parent->parent->left;
                if (uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->left) {
                        node = node->parent;
                        rightRotate(node);
                    }
                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    leftRotate(node->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

    void leftRotate(Node* node) {
        Node* temp = node->right;
        node->right = temp->left;
        if (temp->left != nullptr) {
            temp->left->parent = node;
        }
        temp->parent = node->parent;
        if (node->parent == nullptr) {
            root = temp;
        } else if (node == node->parent->left) {
            node->parent->left = temp;
        } else {
            node->parent->right = temp;
        }
        temp->left = node;
        node->parent = temp;
    }

    void rightRotate(Node* node) {
        Node* temp = node->left;
        node->left = temp->right;
        if (temp->right != nullptr) {
            temp->right->parent = node;
        }
        temp->parent = node->parent;
        if (node->parent == nullptr) {
            root = temp;
        } else if (node == node->parent->right) {
            node->parent->right