用python写生成红黑树的代码

以下是用Python写的红黑树代码：

class Node:
    def __init__(self, val, color="black"):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
        self.color = color

class RedBlackTree:
    def __init__(self):
        self.nil = Node(None)
        self.root = self.nil

    def left_rotate(self, x):
        y = x.right
        x.right = y.left

        if y.left != self.nil:
            y.left.parent = x

        y.parent = x.parent

        if x.parent == self.nil:
            self.root = y

        elif x == x.parent.left:
            x.parent.left = y

        else:
            x.parent.right = y

        y.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right

        if y.right != self.nil:
            y.right.parent = x

        y.parent = x.parent

        if x.parent == self.nil:
            self.root = y

        elif x == x.parent.right:
            x.parent.right = y

        else:
            x.parent.left = y

        y.right = x
        x.parent = y

    def insert(self, val):
        new_node = Node(val, color="red")

        x = self.root
        y = self.nil

        while x != self.nil:
            y = x

            if new_node.val < x.val:
                x = x.left

            else:
                x = x.right

        new_node.parent = y

        if y == self.nil:
            self.root = new_node

        elif new_node.val < y.val:
            y.left = new_node

        else:
            y.right = new_node

        self.insert_fixup(new_node)

    def insert_fixup(self, x):
        while x.parent.color == "red":
            if x.parent == x.parent.parent.left:
                y = x.parent.parent.right

                if y.color == "red":
                    x.parent.color = "black"
                    y.color = "black"
                    x.parent.parent.color = "red"
                    x = x.parent.parent

                else:
                    if x == x.parent.right:
                        x = x.parent
                        self.left_rotate(x)

                    x.parent.color = "black"
                    x.parent.parent.color = "red"
                    self.right_rotate(x.parent.parent)

            else:
                y = x.parent.parent.left

                if y.color == "red":
                    x.parent.color = "black"
                    y.color = "black"
                    x.parent.parent.color = "red"
                    x = x.parent.parent

                else:
                    if x == x.parent.left:
                        x = x.parent
                        self.right_rotate(x)

                    x.parent.color = "black"
                    x.parent.parent.color = "red"
                    self.left_rotate(x.parent.parent)

        self.root.color = "black"

希望对您有所帮助！