写一个黑红薯代码
时间: 2024-02-09 10:08:21 浏览: 22
以下是一个简单的黑红树的 Python 代码:
```python
RED = True
BLACK = False
class Node:
def __init__(self, key, value, color=RED):
self.key = key
self.value = value
self.left = None
self.right = None
self.color = color
class RedBlackTree:
def __init__(self):
self.root = None
def is_red(self, node):
if node is None:
return False
return node.color == RED
def rotate_left(self, node):
x = node.right
node.right = x.left
x.left = node
x.color = node.color
node.color = RED
return x
def rotate_right(self, node):
x = node.left
node.left = x.right
x.right = node
x.color = node.color
node.color = RED
return x
def flip_colors(self, node):
node.color = RED
node.left.color = BLACK
node.right.color = BLACK
def put(self, key, value):
self.root = self._put(self.root, key, value)
self.root.color = BLACK
def _put(self, node, key, value):
if node is None:
return Node(key, value)
if key < node.key:
node.left = self._put(node.left, key, value)
elif key > node.key:
node.right = self._put(node.right, key, value)
else:
node.value = value
if self.is_red(node.right) and not self.is_red(node.left):
node = self.rotate_left(node)
if self.is_red(node.left) and self.is_red(node.left.left):
node = self.rotate_right(node)
if self.is_red(node.left) and self.is_red(node.right):
self.flip_colors(node)
return node
def get(self, key):
node = self.root
while node is not None:
if key < node.key:
node = node.left
elif key > node.key:
node = node.right
else:
return node.value
return None
```
这是一个简单的实现,您可以根据需要进行修改和扩展。