用copilot生成的红黑树

red_black_tree.cpp

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

struct Node
{
    int data;
    Node *left;
    Node *right;
    Node *parent;
    int color;
};

struct RBTree
{
    Node *root;
    Node *nil;

    RBTree()
    {
        nil = new Node;
        nil->color = 0;
        nil->left = nil;
        nil->right = nil;
        nil->parent = nil;
        root = nil;
    }

    void left_rotate(Node *x)
    {
        Node *y = x->right;
        x->right = y->left;
        if (y->left != nil)
            y->left->parent = x;
        y->parent = x->parent;
        if (x->parent == nil)
            root = y;
        else if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
        y->left = x;
        x->parent = y;
    }

    void right_rotate(Node *y)
    {
        Node *x = y->left;
        y->left = x->right;
        if (x->right != nil)
            x->right->parent = y;
        x->parent = y->parent;
        if (y->parent == nil)
            root = x;
        else if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
        x->right = y;
        y->parent = x;
    }

    void insert_fixup(Node *z)
    {
        Node *y;
        while (z->parent->color == 1)
        {
            if (z->parent == z->parent->parent->left)
            {
                y = z->parent->parent->right;
                if (y->color == 1)
                {
                    z->parent->color = 0;
                    y->color = 0;
                    z->parent->parent->color = 1;
                    z = z->parent->parent;
                }
                else
                {
                    if (z == z->parent->right)
                    {
                        z = z->parent;
                        left_rotate(z);
                    }
                    z->parent->color = 0;
                    z->parent->parent->color = 1;
                    right_rotate(z->parent->parent);
                }
            }
            else
            {
                y = z->parent->parent->left;
                if (y->color == 1)
                {
                    z->parent->color = 0;
                    y->color = 0;
                    z->parent->parent->color = 1;
                    z = z->parent->parent;
                }
                else
                {
                    if (z == z->parent->left)
                    {
                        z = z->parent;
                        right_rotate(z);
                    }
                    z->parent->color = 0;
                    z->parent->parent->color = 1;
                    left_rotate(z->parent->parent);
                }
            }
        }
        root->color = 0;
    }

    void insert(int data)
    {
        Node *z = new Node;
        z->data = data;
        z->left = nil;
        z->right = nil;
        z->parent = nil;
        z->color = 1;
        Node *y = nil;
        Node *x = root;
        while (x != nil)
        {
            y = x;
            if (z->data < x->data)
                x = x->left;
            else
                x = x->right;
        }
        z->parent = y;
        if (y == nil)
            root = z;
        else if (z->data < y->data)
            y->left = z;
        else
            y->right = z;
        insert_fixup(z);
    }

    void transplant(Node *u, Node *v)
    {
        if (u->parent == nil)
            root = v;
        else if (u == u->parent->left)
            u->parent->left = v;
        else
            u->parent->right = v;
        v->parent = u->parent;
    }

    void delete_fixup(Node *x)
    {
        Node *w;
        while (x != root && x->color == 0)
        {
            if (x == x->parent->left)
            {
                w = x->parent->right;
                if (w->color == 1)
                {
                    w->color = 0;
                    x->parent->color = 1;
                    left_rotate(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == 0 && w->right->color == 0)
                {
                    w->color = 1;
                    x = x->parent;
                }
                else
                {
                    if (w->right->color == 0)
                    {
                        w->left->color = 0;
                        w->color = 1;
                        right_rotate(w);
                        w = x->parent->right;
                    }
                    w->color = x->parent->color;
                    x->parent->color = 0;
                    w->right->color = 0;
                    left_rotate(x->parent);
                    x = root;
                }
            }
            else
            {
                w = x->parent->left;
                if (w->color == 1)
                {
                    w->color = 0;
                    x->parent->color = 1;
                    right_rotate(x->parent);
                    w = x->parent->left;
                }
                if (w->right->color == 0 && w->left->color == 0)
                {
                    w->color = 1;
                    x = x->parent;
                }
                else
                {
                    if (w->left->color == 0)
                    {
                        w->right->color = 0;
                        w->color = 1;
                        left_rotate(w);
                        w = x->parent->left;
                    }
                    w->color = x->parent->color;
                    x->parent->color = 0;
                    w->left->color = 0;
                    right_rotate(x->parent);
                    x = root;
                }
            }
        }
        x->color = 0;
    }

    Node* tree_minimum(Node *x)
    {
        while (x->left != nil)
            x = x->left;
        return x;
    }

    void _delete(Node *z)
    {
        Node *y = z;
        int y_original_color = y->color;
        Node *x;
        if (z->left == nil)
        {
            x = z->right;
            transplant(z, z->right);
        }
        else if (z->right == nil)
        {
            x = z->left;
            transplant(z, z->left);
        }
        else
        {
            y = tree_minimum(z->right);
            y_original_color = y->color;
            x = y->right;
            if (y->parent == z)
                x->parent = y;
            else
            {
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        if (y_original_color == 0)
            delete_fixup(x);
    }

    void inorder(Node *x)
    {
        if (x != nil)
        {
            inorder(x->left);
            cout << x->data << " ";
            inorder(x->right);
        }
    }

    void preorder(Node *x)
    {
        if (x != nil)
        {
            cout << x->data << " ";
            preorder(x->left);
            preorder(x->right);
        }
    }

    void postorder(Node *x)
    {
        if (x != nil)
        {
            postorder(x->left);
            postorder(x->right);
            cout << x->data << " ";
        }
    }

    void levelorder(Node *x)
    {
        queue<Node *> q;
        q.push(x);
        while (!q.empty())
        {
            x = q.front();
            q.pop();
            cout << x->data << " ";
            if (x->left != nil)
                q.push(x->left);
            if (x->right != nil)
                q.push(x->right);
        }
    }

    void print_tree()
    {
        cout << "Inorder Traversal: ";
        inorder(root);
        cout << endl;
        cout << "Preorder Traversal: ";
        preorder(root);
        cout << endl;
        cout << "Postorder Traversal: ";
        postorder(root);
        cout << endl;
        cout << "Levelorder Traversal: ";
        levelorder(root);
        cout << endl;
    }
};

int main() {
    RBTree rbt;
    rbt.insert(1);
    rbt.insert(7);
    rbt.insert(2);
    rbt.insert(5);
    rbt.insert(10);
    rbt.insert(3);
    rbt.print_tree();
}