Python实现红黑树：从理论到实践的记录日志
原创
Python实现红黑树：从理论到实践的记录日志
原创
鼓掌MVP
发布于 2025-09-21 21:59:48
发布于 2025-09-21 21:59:48
前言：
在计算机科学领域，数据结构的选择往往决定了程序的效率上限。当我开始深入学习高级数据结构时，红黑树这个名字总是频繁出现——它被广泛应用于Linux内核进程调度、Java的TreeMap、C++的STL以及数据库系统的索引实现中。这种看似神秘的数据结构究竟有何魔力？
我决定亲手用Python实现一遍，记录下这个充满挑战与收获的过程。
第一步：理解红黑树的核心原理
红黑树的五大特性
红黑树是一种自平衡的二叉查找树，它通过以下规则维持平衡：
- 每个节点要么是红色，要么是黑色
- 根节点永远是黑色
- 所有叶子节点（NIL节点）都是黑色
- 红色节点的子节点必须是黑色（不能有连续的红色节点）
- 从任意节点到其每个叶子节点的路径包含相同数量的黑色节点
这些规则确保了红黑树的关键特性：从根到叶子的最长路径不会超过最短路径的两倍，从而保证了O(log n)的时间复杂度。
红黑树的五大规则出发，想要搞清楚每个规则背后的数学原理肯定需要费一番功夫，比如黑高度如何保证平衡，以及旋转操作如何维持性质。还要对比AVL树，突出红黑树在实践中的优势，比如减少旋转次数，适合频繁插入删除的场景。
红黑树通过以下数学性质保证其平衡性：对于含有n个内部节点的红黑树，其高度h满足：
h ≤ 2 log₂(n + 1)理解如下：
- 定义黑高度bh(x)：从节点x到任意后代叶节点的路径上的黑色节点数量（不包括x自身）
- 通过归纳法可以证明，以x为根的子树至少包含2^{bh(x)} - 1个内部节点
- 根据红黑树性质4（红色节点的子节点必须为黑色），从根到叶子的路径上至少有一半的节点是黑色
- 因此，根节点的黑高度至少为h/2，即bh(root) ≥ h/2
- 结合第2点：n ≥ 2^{h/2} - 1 → h ≤ 2 log₂(n + 1)
这一数学保证确保了红黑树的最坏情况性能为O(log n)，这是其能够广泛应用于系统编程的根本原因。
与AVL树的比较
在开始实现前，我研究了红黑树与AVL树的区别：
- AVL树提供更严格的平衡，查询效率略高
- 红黑树提供近似平衡，插入和删除效率更高
- 红黑树需要更少的旋转操作，适合频繁修改的场景
这正是为什么大多数系统选择红黑树作为底层实现的原因。
第二步：设计基础结构
节点类的实现
我首先设计了节点类，使用__slots__优化内存使用：
class RBNode:
__slots__ = ('key', 'value', 'parent', 'left', 'right', 'color')
def __init__(self, key, value=None, parent=None,
left=None, right=None, color='RED'):
self.key = key
self.value = value # 支持键值对存储
self.parent = parent
self.left = left
self.right = right
self.color = color # 新节点默认红色
def __repr__(self):
return f"{self.key}({self.color[0]})"
@property
def grandparent(self):
"""获取祖父节点"""
if self.parent is not None:
return self.parent.parent
return None
@property
def uncle(self):
"""获取叔节点"""
gp = self.grandparent
if gp is None:
return None
if self.parent == gp.left:
return gp.right
else:
return gp.left
def is_leaf(self):
"""判断是否为叶子节点"""
return self.left is None and self.right is None红黑树框架搭建
接着我创建了红黑树的主体结构：
class RedBlackTree:
def __init__(self):
self.NIL_LEAF = RBNode(None, color='BLACK') # 统一的NIL节点
self.root = self.NIL_LEAF
self._size = 0 # 记录节点数量
def __len__(self):
return self._size
def __contains__(self, key):
return self.search(key) is not None
def is_empty(self):
return self.root == self.NIL_LEAF第三步：实现插入操作
普通BST插入
我首先实现了普通的二叉搜索树插入逻辑：
def insert(self, key, value=None):
new_node = RBNode(key, value, left=self.NIL_LEAF, right=self.NIL_LEAF)
# 空树情况
if self.is_empty():
new_node.color = 'BLACK' # 根节点必须为黑
self.root = new_node
self._size += 1
return new_node
# 寻找插入位置
parent = self._find_parent(key)
new_node.parent = parent
if key < parent.key:
parent.left = new_node
else:
parent.right = new_node
self._size += 1
self._fix_insert(new_node) # 修复红黑树性质
return new_node
def _find_parent(self, key):
"""寻找合适父节点的辅助方法"""
current = self.root
parent = None
while current != self.NIL_LEAF:
parent = current
if key < current.key:
current = current.left
elif key > current.key:
current = current.right
else:
# 键已存在，更新值
current.value = value
return None # 表示不需要插入新节点
return parent插入修复逻辑
这是最具挑战性的部分，我花了大量时间调试：
def _fix_insert(self, node):
"""修复插入后可能违反的红黑树性质"""
while node != self.root and node.parent.color == 'RED':
# 父节点是祖父节点的左子节点
if node.parent == node.grandparent.left:
uncle = node.grandparent.right
# 情况1：叔节点是红色
if uncle.color == 'RED':
node.parent.color = 'BLACK'
uncle.color = 'BLACK'
node.grandparent.color = 'RED'
node = node.grandparent # 将问题上移
else:
# 情况2：节点是父节点的右子节点（LR情况）
if node == node.parent.right:
node = node.parent
self._left_rotate(node)
# 情况3：节点是父节点的左子节点（LL情况）
node.parent.color = 'BLACK'
node.grandparent.color = 'RED'
self._right_rotate(node.grandparent)
else: # 对称情况：父节点是祖父节点的右子节点
uncle = node.grandparent.left
if uncle.color == 'RED':
node.parent.color = 'BLACK'
uncle.color = 'BLACK'
node.grandparent.color = 'RED'
node = node.grandparent
else:
if node == node.parent.left:
node = node.parent
self._right_rotate(node)
node.parent.color = 'BLACK'
node.grandparent.color = 'RED'
self._left_rotate(node.grandparent)
# 确保根节点为黑色
self.root.color = 'BLACK'旋转操作实现
旋转是红黑树平衡的核心操作：
def _left_rotate(self, x):
"""以x为支点进行左旋"""
y = x.right
x.right = y.left
if y.left != self.NIL_LEAF:
y.left.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def _right_rotate(self, y):
"""以y为支点进行右旋"""
x = y.left
y.left = x.right
if x.right != self.NIL_LEAF:
x.right.parent = y
x.parent = y.parent
if y.parent is None:
self.root = x
elif y == y.parent.right:
y.parent.right = x
else:
y.parent.left = x
x.right = y
y.parent = x第四步：实现删除操作
删除基础逻辑
删除操作比插入更加复杂，我参考了《算法导论》中的描述：
def delete(self, key):
"""删除指定键的节点"""
node = self._search(key)
if node == self.NIL_LEAF:
return False # 节点不存在
# 记录原始颜色和被移动的节点
original_color = node.color
if node.left == self.NIL_LEAF:
x = node.right
self._transplant(node, node.right)
elif node.right == self.NIL_LEAF:
x = node.left
self._transplant(node, node.left)
else:
# 有两个子节点，找后继节点
successor = self._minimum(node.right)
original_color = successor.color
x = successor.right
if successor.parent == node:
x.parent = successor
else:
self._transplant(successor, successor.right)
successor.right = node.right
successor.right.parent = successor
self._transplant(node, successor)
successor.left = node.left
successor.left.parent = successor
successor.color = node.color
# 如果删除的是黑色节点，需要修复
if original_color == 'BLACK':
self._fix_delete(x)
self._size -= 1
return True
def _transplant(self, u, v):
"""用v子树替换u子树"""
if u.parent is None:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent删除修复逻辑
这是最复杂的部分，我花了整整一天调试：
def _fix_delete(self, x):
"""修复删除后可能违反的红黑树性质"""
while x != self.root and x.color == 'BLACK':
if x == x.parent.left:
sibling = x.parent.right
# 情况1：兄弟节点为红色
if sibling.color == 'RED':
sibling.color = 'BLACK'
x.parent.color = 'RED'
self._left_rotate(x.parent)
sibling = x.parent.right
# 情况2：兄弟节点的两个子节点都是黑色
if sibling.left.color == 'BLACK' and sibling.right.color == 'BLACK':
sibling.color = 'RED'
x = x.parent
else:
# 情况3：兄弟节点的右子节点为黑色，左子节点为红色
if sibling.right.color == 'BLACK':
sibling.left.color = 'BLACK'
sibling.color = 'RED'
self._right_rotate(sibling)
sibling = x.parent.right
# 情况4：兄弟节点的右子节点为红色
sibling.color = x.parent.color
x.parent.color = 'BLACK'
sibling.right.color = 'BLACK'
self._left_rotate(x.parent)
x = self.root # 终止循环
else:
# 对称情况：x是右子节点
sibling = x.parent.left
if sibling.color == 'RED':
sibling.color = 'BLACK'
x.parent.color = 'RED'
self._right_rotate(x.parent)
sibling = x.parent.left
if sibling.left.color == 'BLACK' and sibling.right.color == 'BLACK':
sibling.color = 'RED'
x = x.parent
else:
if sibling.left.color == 'BLACK':
sibling.right.color = 'BLACK'
sibling.color = 'RED'
self._left_rotate(sibling)
sibling = x.parent.left
sibling.color = x.parent.color
x.parent.color = 'BLACK'
sibling.left.color = 'BLACK'
self._right_rotate(x.parent)
x = self.root
x.color = 'BLACK'第五步：辅助方法与遍历操作
查找与极值方法
def search(self, key):
"""查找指定键的节点"""
current = self.root
while current != self.NIL_LEAF:
if key == current.key:
return current
elif key < current.key:
current = current.left
else:
current = current.right
return None
def _minimum(self, node):
"""查找子树中的最小节点"""
while node.left != self.NIL_LEAF:
node = node.left
return node
def _maximum(self, node):
"""查找子树中的最大节点"""
while node.right != self.NIL_LEAF:
node = node.right
return node
def get_min(self):
"""获取树中的最小键"""
if self.is_empty():
return None
return self._minimum(self.root).key
def get_max(self):
"""获取树中的最大键"""
if self.is_empty():
return None
return self._maximum(self.root).key遍历方法
def inorder_traversal(self):
"""中序遍历生成器"""
stack = []
current = self.root
while stack or current != self.NIL_LEAF:
if current != self.NIL_LEAF:
stack.append(current)
current = current.left
else:
current = stack.pop()
yield (current.key, current.value)
current = current.right
def preorder_traversal(self):
"""前序遍历生成器"""
if self.is_empty():
return
stack = [self.root]
while stack:
node = stack.pop()
if node != self.NIL_LEAF:
yield (node.key, node.value)
stack.append(node.right)
stack.append(node.left)
def level_order_traversal(self):
"""层次遍历生成器"""
if self.is_empty():
return
queue = collections.deque([self.root])
while queue:
node = queue.popleft()
if node != self.NIL_LEAF:
yield (node.key, node.value)
queue.append(node.left)
queue.append(node.right)总结与反思
通过这一周的实现过程，我深刻理解了红黑树的内部机制和设计哲学。以下是一些关键收获：
- 红黑树的平衡是概率性的：它不追求绝对平衡，而是通过近似平衡保证操作效率，这种设计哲学在实际工程中很有价值。
- 删除比插入更复杂：删除操作需要考虑更多情况，调试难度也更大。我通过画图和分析案例来理解各种情况。
- 测试至关重要：没有全面的测试，几乎不可能正确实现红黑树。我编写的测试用例帮助发现了多个隐蔽的错误。
- 性能优势明显：与普通BST相比，红黑树在大数据量下表现稳定，不会退化为链表。
- 理论与实践结合：只有亲手实现，才能真正理解算法导论中那些抽象的描述。
这个实现还有改进空间，比如支持并发访问、优化内存布局、提供持久化支持等。但核心功能已经完备，可以作为学习红黑树的良好参考。
红黑树的实现过程让我体会到，优秀的数据结构设计需要在理论完美性和工程实用性之间找到平衡点。这种平衡思维不仅适用于数据结构设计，也是解决复杂工程问题的重要方法论。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
