帮我写个红黑树底层

红黑树是一种自平衡的二叉查找树，它具有以下特点：

1.每个节点要么是红色，要么是黑色。 2.根节点是黑色的。 3.每个叶子节点都是黑色的空节点（NIL节点）。 4.如果一个节点是红色的，则它的子节点必须是黑色的。 5.从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

下面是红黑树的实现代码：

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
    bool is_red;
};

class RedBlackTree {
public:
    RedBlackTree() {
        nil = new Node();
        nil->is_red = false;
        root = nil;
    }

    void insert(int val) {
        Node* node = new Node();
        node->val = val;
        node->left = nil;
        node->right = nil;
        node->parent = nil;
        node->is_red = true;

        Node* y = nil;
        Node* x = root;
        while (x != nil) {
            y = x;
            if (val < x->val) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        node->parent = y;
        if (y == nil) {
            root = node;
        } else if (val < y->val) {
            y->left = node;
        } else {
            y->right = node;
        }

        insert_fixup(node);
    }

    void remove(int val) {
        Node* z = find(val);
        if (z == nil) {
            return;
        }

        Node* y = nil;
        if (z->left == nil || z->right == nil) {
            y = z;
        } else {
            y = successor(z);
        }

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

        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;
        }

        if (y != z) {
            z->val = y->val;
        }

        if (!y->is_red) {
            remove_fixup(x);
        }

        delete y;
    }

private:
    Node* root;
    Node* nil;

    Node* find(int val) {
        Node* cur = root;
        while (cur != nil) {
            if (val == cur->val) {
                return cur;
            } else if (val < cur->val) {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }
        return nil;
    }

    Node* minimum(Node* node) {
        while (node->left != nil) {
            node = node->left;
        }
        return node;
    }

    Node* maximum(Node* node) {
        while (node->right != nil) {
            node = node->right;
        }
        return node;
    }

    Node* successor(Node* node) {
        if (node->right != nil) {
            return minimum(node->right);
        }

        Node* parent = node->parent;
        while (parent != nil && node == parent->right) {
            node = parent;
            parent = parent->parent;
        }

        return parent;
    }

    Node* predecessor(Node* node) {
        if (node->left != nil) {
            return maximum(node->left);
        }

        Node* parent = node->parent;
        while (parent != nil && node == parent->left) {
            node = parent;
            parent = parent->parent;
        }

        return parent;
    }

    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* x) {
        Node* y = x->left;
        x->left = y->right;
        if (y->right != nil) {
            y->right->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->right = x;
        x->parent = y;
    }

    void insert_fixup(Node* z) {
        while (z->parent->is_red) {
            if (z->parent == z->parent->parent->left) {
                Node* y = z->parent->parent->right;
                if (y->is_red) {
                    z->parent->is_red = false;
                    y->is_red = false;
                    z->parent->parent->is_red = true;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        left_rotate(z);
                    }
                    z->parent->is_red = false;
                    z->parent->parent->is_red = true;
                    right_rotate(z->parent->parent);
                }
            } else {
                Node* y = z->parent->parent->left;
                if (y->is_red) {
                    z->parent->is_red = false;
                    y->is_red = false;
                    z->parent->parent->is_red = true;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        right_rotate(z);
                    }
                    z->parent->is_red = false;
                    z->parent->parent->is_red = true;
                    left_rotate(z->parent->parent);
                }
            }
        }
        root->is_red = false;
    }

    void remove_fixup(Node* x) {
        while (x != root && !x->is_red) {
            if (x == x->parent->left) {
                Node* w = x->parent->right;
                if (w->is_red) {
                    w->is_red = false;
                    x->parent->is_red = true;
                    left_rotate(x->parent);
                    w = x->parent->right;
                }
                if (!w->left->is_red && !w->right->is_red) {
                    w->is_red = true;
                    x = x->parent;
                } else {
                    if (!w->right->is_red) {
                        w->left->is_red = false;
                        w->is_red = true;
                        right_rotate(w);
                        w = x->parent->right;
                    }
                    w->is_red = x->parent->is_red;
                    x->parent->is_red = false;
                    w->right->is_red = false;
                    left_rotate(x->parent);
                    x = root;
                }
            } else {
                Node* w = x->parent->left;
                if (w->is_red) {
                    w->is_red = false;
                    x->parent->is_red = true;
                    right_rotate(x->parent);
                    w = x->parent->left;
                }
                if (!w->right->is_red && !w->left->is_red) {
                    w->is_red = true;
                    x = x->parent;
                } else {
                    if (!w->left->is_red) {
                        w->right->is_red = false;
                        w->is_red = true;
                        left_rotate(w);
                        w = x->parent->left;
                    }
                    w->is_red = x->parent->is_red;
                    x->parent->is_red = false;
                    w->left->is_red = false;
                    right_rotate(x->parent);
                    x = root;
                }
            }
        }
        x->is_red = false;
    }
};