用python写一段红黑树的代码

### 回答1：
好的，这是一段简单的红黑树代码：

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

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

    def insert(self, val):
        new_node = Node(val, 'red')
        if not self.root:
            self.root = new_node
            new_node.color = 'black'
            return
        curr = self.root
        while curr:
            if val < curr.val:
                if not curr.left:
                    curr.left = new_node
                    new_node.parent = curr
                    break
                else:
                    curr = curr.left
            else:
                if not curr.right:
                    curr.right = new_node
                    new_node.parent = curr
                    break
                else:
                    curr = curr.right
        self.fix_violations(new_node)

    def fix_violations(self, node):
        # Case 1
        if not node.parent:
            node.color = 'black'
            return
        # Case 2
        if node.parent.color == 'black':
            return
        # Case 3
        if self.get_uncle(node) and self.get_uncle(node).color == 'red':
            self.get_uncle(node).color = 'black'
            node.parent.color = 'black'
            self.get_grandparent(node).color = 'red'
            self.fix_violations(self.get_grandparent(node))
            return
        # Case 4
        if self.get_uncle(node) and self.get_uncle(node).color == 'black':
            grandparent = self.get_grandparent(node)
            if node == node.parent.right and node.parent == grandparent.left:
                self.rotate_left(node.parent)
                node = node.left
            elif node == node.parent.left and node.parent == grandparent.right:
                self.rotate_right(node.parent)
                node = node.right
            # Case 5
            node.parent.color = 'black'
            grandparent.color = 'red'
            if node == node.parent.left and node.parent == grandparent.left:
                self.rotate_right(grandparent)
            else:
                self.rotate_left(grandparent)

    def get_uncle(self, node):
        if not node or not node.parent or not node.parent.parent:
            return None
        if node.parent == node.parent.parent.left:
            return node.parent.parent.right
        else:
            return node.parent.parent.left

    def get_grandparent(self, node):
        if not node or not node.parent or not node.parent.parent:
            return None
         

### 回答2：
红黑树是一种自平衡的二叉搜索树，每个节点都有一位颜色属性，红色或黑色。下面是一个简单的用Python编写的红黑树代码示例：

class Node:
def __init__(self, key):
self.key = key
self.parent = None
self.left = None
self.right = None
self.color = 1

class RedBlackTree:
def __init__(self):
self.NIL = Node(0)
self.NIL.color = 0
self.root = self.NIL

# 插入节点后调整树的平衡
def insert(self, key):
node = Node(key)
node.parent = None
node.key = key
node.left = self.NIL
node.right = self.NIL
node.color = 1 # 新插入节点为红色
y = None
x = self.root

while x != self.NIL:
y = x
if node.key < x.key:
x = x.left
else:
x = x.right

node.parent = y
if y is None:
self.root = node
elif node.key < y.key:
y.left = node
else:
y.right = node

# 调整树的平衡
if node.parent is None:
node.color = 0
return

if node.parent.parent is None:
return

self._fix_insert(node)

# 调整插入操作导致的不平衡
def _fix_insert(self, node):
while node.parent.color == 1:
if node.parent == node.parent.parent.right:
u = node.parent.parent.left
if u.color == 1:
u.color = 0
node.parent.color = 0
node.parent.parent.color = 1
node = node.parent.parent
else:
if node == node.parent.left:
node = node.parent
self._right_rotate(node)
node.parent.color = 0
node.parent.parent.color = 1
self._left_rotate(node.parent.parent)
else:
u = node.parent.parent.right

if u.color == 1:
u.color = 0
node.parent.color = 0
node.parent.parent.color = 1
node = node.parent.parent
else:
if node == node.parent.right:
node = node.parent
self._left_rotate(node)
node.parent.color = 0
node.parent.parent.color = 1
self._right_rotate(node.parent.parent)
if node == self.root:
break
self.root.color = 0

# 左旋
def _left_rotate(self, node):
y = node.right
node.right = y.left
if y.left != self.NIL:
y.left.parent = node

y.parent = node.parent
if node.parent is None:
self.root = y
elif node == node.parent.left:
node.parent.left = y
else:
node.parent.right = y
y.left = node
node.parent = y

# 右旋
def _right_rotate(self, node):
y = node.left
node.left = y.right
if y.right != self.NIL:
y.right.parent = node

y.parent = node.parent
if node.parent is None:
self.root = y
elif node == node.parent.right:
node.parent.right = y
else:
node.parent.left = y
y.right = node
node.parent = y

# 打印树中的节点
def print_tree(self, node, level=0):
if node != self.NIL:
self.print_tree(node.right, level + 1)
print('\t' * level + str(node.key) + (' (R)' if node.color == 1 else ' (B)'))
self.print_tree(node.left, level + 1)

# 测试示例
rbt = RedBlackTree()

rbt.insert(10)
rbt.insert(20)
rbt.insert(30)
rbt.insert(100)
rbt.insert(40)
rbt.insert(50)
rbt.insert(60)

rbt.print_tree(rbt.root)

这段代码实现了插入操作和相关的旋转操作，以保持红黑树的平衡。在测试示例中，我们插入了一些节点，然后打印出树中的节点来验证树的结构和平衡性。