通過C++實(shí)踐深入探討紅黑樹的性質(zhì)

紅黑樹是一種自平衡二叉搜索樹，它在插入和刪除元素時(shí)能夠保持樹的平衡，從而保證了樹的查找、插入和刪除操作的時(shí)間復(fù)雜度都是O(logn)。紅黑樹有以下幾個(gè)性質(zhì)：

1. 每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。
2. 根節(jié)點(diǎn)是黑色。
3. 每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色。
4. 如果一個(gè)節(jié)點(diǎn)是紅色，則它的子節(jié)點(diǎn)都是黑色。
5. 對(duì)于每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代葉子節(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)量的黑色節(jié)點(diǎn)。

下面是一個(gè)簡(jiǎn)單的C++實(shí)現(xiàn)紅黑樹的例子：

#include <iostream>
#include <vector>

enum Color { RED, BLACK };

template <typename T>
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 <typename T>
class RedBlackTree {
public:
    RedBlackTree() : root(nullptr) {}

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

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

private:
    Node<T>* root;

    void insertNode(Node<T>* node) {
        Node<T>* temp = nullptr;
        Node<T>* 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<T>* node) {
        while (node != root && node->parent->color == RED) {
            if (node->parent == node->parent->parent->left) {
                Node<T>* 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<T>* 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<T>* node) {
        Node<T>* 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<T>* node) {
        Node<T>* 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