c++

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

小樊
82
2024-04-26 19:07:59
栏目: 编程语言

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

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

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

#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

0
看了该问题的人还看了