手写红黑树

红黑树是一种自平衡的二叉搜索树，它的平衡保证了在最坏情况下的查找、插入和删除操作的时间复杂度均为 O(log n)。红黑树的每个节点都有一个颜色属性，可以是红色或黑色。在插入和删除节点时，需要通过变换节点的颜色和旋转子树来保证树的平衡。

下面是一个简单的红黑树的实现，包含节点的插入、删除和查找操作：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.color = "RED"

class RedBlackTree:
    def __init__(self):
        self.root = None
    
    def insert(self, key, value):
        node = Node(key, value)
        if self.root is None:
            node.color = "BLACK"
            self.root = node
        else:
            parent = None
            current = self.root
            while current is not None:
                parent = current
                if key < current.key:
                    current = current.left
                elif key > current.key:
                    current = current.right
                else:
                    current.value = value
                    return
            if key < parent.key:
                parent.left = node
            elif key > parent.key:
                parent.right = node
            node.parent = parent
            self.balance(node)
    
    def delete(self, key):
        node = self.find(key)
        if node is None:
            return
        if node.left is not None and node.right is not None:
            successor = node.right
            while successor.left is not None:
                successor = successor.left
            node.key = successor.key
            node.value = successor.value
            node = successor
        if node.left is None and node.right is None:
            if node.color == "RED":
                if node.parent.left == node:
                    node.parent.left = None
                else:
                    node.parent.right = None
            else:
                self.balance_delete(node)
                if node.parent is None:
                    self.root = None
                else:
                    if node.parent.left == node:
                        node.parent.left = None
                    else:
                        node.parent.right = None
        elif node.left is not None:
            node.left.parent = node.parent
            if node.color == "RED":
                if node.parent.left == node:
                    node.parent.left = node.left
                else:
                    node.parent.right = node.left
            else:
                self.balance_delete(node.left)
                if node.parent is None:
                    self.root = node.left
                else:
                    if node.parent.left == node:
                        node.parent.left = node.left
                    else:
                        node.parent.right = node.left
        else:
            node.right.parent = node.parent
            if node.color == "RED":
                if node.parent.left == node:
                    node.parent.left = node.right
                else:
                    node.parent.right = node.right
            else:
                self.balance_delete(node.right)
                if node.parent is None:
                    self.root = node.right
                else:
                    if node.parent.left == node:
                        node.parent.left = node.right
                    else:
                        node.parent.right = node.right
    
    def find(self, key):
        current = self.root
        while current is not None:
            if key < current.key:
                current = current.left
            elif key > current.key:
                current = current.right
            else:
                return current
        return None
    
    def balance(self, node):
        while node.parent is not None and node.parent.color == "RED":
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                if uncle is not None 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 is not None 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 balance_delete(self, node):
        while node is not self.root and node.color == "BLACK":
            if node == node.parent.left:
                sibling = node.parent.right
                if sibling.color == "RED":
                    sibling.color = "BLACK"
                    node.parent.color = "RED"
                    self.rotate_left(node.parent)
                    sibling = node.parent.right
                if sibling.left.color == "BLACK" and sibling.right.color == "BLACK":
                    sibling.color = "RED"
                    node = node.parent
                else:
                    if sibling.right.color == "BLACK":
                        sibling.left.color = "BLACK"
                        sibling.color = "RED"
                        self.rotate_right(sibling)
                        sibling = node.parent.right
                    sibling.color = node.parent.color
                    node.parent.color = "BLACK"
                    sibling.right.color = "BLACK"
                    self.rotate_left(node.parent)
                    node = self.root
            else:
                sibling = node.parent.left
                if sibling.color == "RED":
                    sibling.color = "BLACK"
                    node.parent.color = "RED"
                    self.rotate_right(node.parent)
                    sibling = node.parent.left
                if sibling.right.color == "BLACK" and sibling.left.color == "BLACK":
                    sibling.color = "RED"
                    node = node.parent
                else:
                    if sibling.left.color == "BLACK":
                        sibling.right.color = "BLACK"
                        sibling.color = "RED"
                        self.rotate_left(sibling)
                        sibling = node.parent.left
                    sibling.color = node.parent.color
                    node.parent.color = "BLACK"
                    sibling.left.color = "BLACK"
                    self.rotate_right(node.parent)
                    node = self.root
        node.color = "BLACK"
    
    def rotate_left(self, node):
        right = node.right
        node.right = right.left
        if right.left is not None:
            right.left.parent = node
        right.parent = node.parent
        if node.parent is None:
            self.root = right
        else:
            if node == node.parent.left:
                node.parent.left = right
            else:
                node.parent.right = right
        right.left = node
        node.parent = right
    
    def rotate_right(self, node):
        left = node.left
        node.left = left.right
        if left.right is not None:
            left.right.parent = node
        left.parent = node.parent
        if node.parent is None:
            self.root = left
        else:
            if node == node.parent.right:
                node.parent.right = left
            else:
                node.parent.left = left
        left.right = node
        node.parent = left

这里需要注意的是，红黑树的插入和删除操作都需要进行一定的平衡调整，以保证树的平衡性。在代码实现中，我们使用了 `balance` 方法来进行插入节点后的平衡调整，使用了 `balance_delete` 方法来进行删除节点后的平衡调整。同时，为了保证红黑树的性质，我们需要通过颜色变换和旋转子树来进行平衡调整，具体实现可以参考代码中的 `rotate_left` 和 `rotate_right` 方法。