生成一段python 红黑树代码
时间: 2023-10-12 07:09:19 浏览: 44
以下是一段Python实现的红黑树代码:
```python
class Node:
def __init__(self, val, color='red', left=None, right=None):
self.val = val
self.color = color
self.left = left
self.right = right
class RedBlackTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = Node(val, 'black')
else:
node = self._insert(val, self.root)
if node:
self._fix_tree(node)
def _insert(self, val, node):
if val < node.val:
if node.left:
return self._insert(val, node.left)
else:
node.left = Node(val)
return node.left
elif val > node.val:
if node.right:
return self._insert(val, node.right)
else:
node.right = Node(val)
return node.right
def _fix_tree(self, node):
while node != self.root and node.color != 'black' 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._left_rotate(node)
node.parent.color = 'black'
node.parent.parent.color = 'red'
self._right_rotate(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._right_rotate(node)
node.parent.color = 'black'
node.parent.parent.color = 'red'
self._left_rotate(node.parent.parent)
self.root.color = 'black'
def _left_rotate(self, node):
temp = node.right
node.right = temp.left
if temp.left:
temp.left.parent = node
temp.parent = node.parent
if not node.parent:
self.root = temp
elif node == node.parent.left:
node.parent.left = temp
else:
node.parent.right = temp
temp.left = node
node.parent = temp
def _right_rotate(self, node):
temp = node.left
node.left = temp.right
if temp.right:
temp.right.parent = node
temp.parent = node.parent
if not node.parent:
self.root = temp
elif node == node.parent.right:
node.parent.right = temp
else:
node.parent.left = temp
temp.right = node
node.parent = temp
def in_order_traversal(self, node):
if not node:
return
self.in_order_traversal(node.left)
print(node.val, end=' ')
self.in_order_traversal(node.right)
tree = RedBlackTree()
tree.insert(10)
tree.insert(20)
tree.insert(30)
tree.insert(100)
tree.insert(90)
tree.insert(70)
tree.insert(40)
tree.in_order_traversal(tree.root)
```
这段代码实现了红黑树的插入和左右旋转操作,并且在插入节点后通过_fix_tree()方法来保持红黑树的平衡。其中,节点颜色为红色或黑色,红色节点的父节点必须为黑色,而红色节点的子节点必须为黑色或空节点。这个平衡性质使得红黑树的查找、插入和删除操作的时间复杂度均为O(log n)。