python写一个红黑二叉树

下面是一个基本的红黑树实现，包括插入和删除节点的操作。

class Node:
    def __init__(self, val, color='red'):
        self.val = val
        self.left = None
        self.right = None
        self.color = color

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

    def insert(self, val):
        node = Node(val)
        if not self.root:
            self.root = node
            self.root.color = 'black'
        else:
            self._insert(node, self.root)

    def _insert(self, node, parent):
        if node.val < parent.val:
            if parent.left:
                self._insert(node, parent.left)
            else:
                parent.left = node
                node.parent = parent
                self._fix_violation(node)
        else:
            if parent.right:
                self._insert(node, parent.right)
            else:
                parent.right = node
                node.parent = parent
                self._fix_violation(node)

    def _fix_violation(self, node):
        while node.parent and node.parent.color == 'red':
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                if uncle and 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
                        self._rotate_left(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self._rotate_right(node.parent.parent)
            else:
                uncle = node.parent.parent.left
                if uncle and 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
                        self._rotate_right(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self._rotate_left(node.parent.parent)
        self.root.color = 'black'

    def _rotate_left(self, node):
        y = node.right
        node.right = y.left
        if y.left:
            y.left.parent = node
        y.parent = node.parent
        if not node.parent:
            self.root = y
        elif node == node.parent.left:
            node.parent.left = y
        else:
            node.parent.right = y
        y.left = node
        node.parent = y

    def _rotate_right(self, node):
        y = node.left
        node.left = y.right
        if y.right:
            y.right.parent = node
        y.parent = node.parent
        if not node.parent:
            self.root = y
        elif node == node.parent.right:
            node.parent.right = y
        else:
            node.parent.left = y
        y.right = node
        node.parent = y

    def delete(self, val):
        node = self._find_node(val)
        if not node:
            return
        if node.left and node.right:
            successor = node.right
            while successor.left:
                successor = successor.left
            node.val = successor.val
            node = successor
        if not node.left and not node.right:
            if node.parent:
                if node == node.parent.left:
                    node.parent.left = None
                else:
                    node.parent.right = None
            else:
                self.root = None
        elif node.left:
            child = node.left
            node.val = child.val
            node.left = child.left
            node.right = child.right
        else:
            child = node.right
            node.val = child.val
            node.left = child.left
            node.right = child.right
        if node.color == 'black':
            self._fix_double_black(child, node.parent)

    def _find_node(self, val):
        node = self.root
        while node:
            if val == node.val:
                return node
            elif val < node.val:
                node = node.left
            else:
                node = node.right
        return None

    def _fix_double_black(self, node, parent):
        if not parent:
            return
        sibling = parent.left if node == parent.right else parent.right
        if sibling.color == 'red':
            parent.color = 'red'
            sibling.color = 'black'
            if sibling == parent.left:
                self._rotate_left(parent)
            else:
                self._rotate_right(parent)
        elif (not sibling.left or sibling.left.color == 'black') and (not sibling.right or sibling.right.color == 'black'):
            sibling.color = 'red'
            if parent.color == 'black':
                self._fix_double_black(parent, parent.parent)
            else:
                parent.color = 'black'
        else:
            if sibling == parent.left and sibling.right and sibling.right.color == 'red':
                sibling.right.color = 'black'
                sibling.color = parent.color
                parent.color = 'black'
                self._rotate_left(parent)
            elif sibling == parent.right and sibling.left and sibling.left.color == 'red':
                sibling.left.color = 'black'
                sibling.color = parent.color
                parent.color = 'black'
                self._rotate_right(parent)
            else:
                if sibling == parent.left and sibling.left and sibling.left.color == 'red':
                    sibling.left.color = parent.color
                    parent.color = 'black'
                    self._rotate_right(sibling)
                elif sibling == parent.right and sibling.right and sibling.right.color == 'red':
                    sibling.right.color = parent.color
                    parent.color = 'black'
                    self._rotate_left(sibling)
                sibling.color = 'black'

要使用这个类，你可以像这样插入和删除值：

tree = RedBlackTree()
tree.insert(5)
tree.insert(10)
tree.insert(7)
tree.insert(1)
tree.delete(5)