名词：
节点的度： 一个节点含有的 子节点的个数
树的度：一棵树中，最大的节点的度为树的度
叶节点或终端节点： 度数为0的节点
孩子节点或子节点： 一个节点含有 子树的根节点
兄弟节点： 具有相同父节点的节点 互称为兄弟节点
节点的层次：从根开始定义起，根为第一层，根的子节点为第二层，.....
树的高度或深度：树中节点最大的层次
堂兄弟节点：父节点在同一层的节点
节点的祖先：从根到该节点所经分支上的所有节点
子孙：以某节点为根的字数中任意节点都成为该节点的子孙
森林：由m(m>=0)棵互不相交的树的集合称为森林
树的储存结构
可以使用list来存 (内存地址连续)
可以使用Listnode来存(其有left right 与 node)节点
树的遍历方式
先从 最小的数开始遍历
先序遍历： 根 左 右
中序遍历：左 根 右
后序遍历： 左右根
树的种类
满二叉树与完全二叉树
平衡二叉树与失衡二叉树
镜像二叉树与对称二叉树
宇宙无敌树 "红黑树"
历史演变
1962年: AVL 树 (Adelson-Velsky, Landis)
为极致查询速度而生，通过严格平衡避免普通二叉树退化，但维护成本高。
1972年: 对称二叉B树 (Rudolf Bayer)
将B树思想引入二叉树，以近似平衡换取更低的更新开销。
1978年: 红黑树 (Guibas, Sedgewick)
通过最终确立现代命名与颜色规则，红黑树塑造了一个在增、删、查操作上综合性能最优的平衡结构。它完美权衡了查询速度与更新成本，使其成为构建大型、动态数据系统的理想基础，最终在实践应用中取代了AVL树的主流地位。
什么是红黑树？
其作用:
普通的二叉查找树在极端情况下会退化成链表。例如，你依次插入 1, 2, 3, 4, 5，那么这棵树会变成一个长长的右子树，查找效率改变“O(n)”
红黑树通过设定约束条件，确保没有一条路径会比其他路径长出两倍以上，从而维持了“大致平衡”，保证高效性。
红黑树的五大规则（必须）
颜色属性
每个节点非红即黑。
根节点
根节点必须是黑色。
叶子节点
所有叶子节点（NIL/null）视为黑色。
红色节点限制
红色节点的两个子节点必须都是黑色。（即：不能有两个连续的红色节点）
路径规则
从任一节点到其每个后代叶子节点的所有简单路径上，均包含相同数量的黑色节点。（这个数量称为“黑高”）
这就是红黑树代码示例(自认为没人会用！)
名词解释
左旋
把左旋想象成「跷跷板」游戏
想象一个简单的跷跷板：
父节点 (x)
/ \
A 子节点 (y)
/ \
B C
左旋就是：把右边的重孩子(y)抬上来，把自己(x)压下去！左旋后的结果：
子节点 (y)
/ \
父节点(x) C
/ \
A B以下代码为python3.12版本的
主要实现
- 完整的红黑树操作：插入、删除、搜索
- 旋转操作：左旋和右旋
- 修复操作：插入后修复和删除后修复
- 遍历功能：中序遍历返回排序结果
- Pythonic接口：支持
len()和in操作
from typing import Any, Optional
class Node:
"""红黑树节点类"""
__slots__ = ('key', 'value', 'left', 'right', 'parent', 'color')
def __init__(self, key: Any, value: Any, color: str = 'RED'):
self.key = key # 节点键
self.value = value # 节点值
self.left = None # 左子节点
self.right = None # 右子节点
self.parent = None # 父节点
self.color = color # 节点颜色 ('RED' 或 'BLACK')
def __repr__(self) -> str:
return f"Node({self.key}: {self.value}, {self.color})"
class RedBlackTree:
"""红黑树实现"""
def __init__(self):
# 创建NIL节点（叶子节点，黑色）
self.NIL = Node(None, None, 'BLACK')
self.root = self.NIL # 根节点初始化为NIL
self.size = 0 # 树中元素个数
def _left_rotate(self, x: Node) -> None:
"""左旋转操作"""
y = x.right # 设置y为x的右子节点
x.right = y.left # 将y的左子树变为x的右子树
if y.left != self.NIL:
y.left.parent = x # 如果y的左子节点存在，设置其父节点为x
y.parent = x.parent # 将x的父节点赋给y
# 更新父节点的子节点引用
if x.parent == self.NIL:
self.root = y # 如果x是根节点，则y成为新的根节点
elif x == x.parent.left:
x.parent.left = y # 如果x是左子节点，则y成为新的左子节点
else:
x.parent.right = y # 如果x是右子节点，则y成为新的右子节点
y.left = x # 将x放在y的左边
x.parent = y # 将x的父节点设置为y
def _right_rotate(self, y: Node) -> None:
"""右旋转操作"""
x = y.left # 设置x为y的左子节点
y.left = x.right # 将x的右子树变为y的左子树
if x.right != self.NIL:
x.right.parent = y # 如果x的右子节点存在，设置其父节点为y
x.parent = y.parent # 将y的父节点赋给x
# 更新父节点的子节点引用
if y.parent == self.NIL:
self.root = x # 如果y是根节点，则x成为新的根节点
elif y == y.parent.right:
y.parent.right = x # 如果y是右子节点，则x成为新的右子节点
else:
y.parent.left = x # 如果y是左子节点，则x成为新的左子节点
x.right = y # 将y放在x的右边
y.parent = x # 将y的父节点设置为x
def insert(self, key: Any, value: Any) -> None:
"""插入键值对"""
new_node = Node(key, value)
new_node.left = self.NIL
new_node.right = self.NIL
# 查找插入位置
parent = self.NIL
current = self.root
while current != self.NIL:
parent = current
if new_node.key < current.key:
current = current.left
elif new_node.key > current.key:
current = current.right
else:
# 键已存在，更新值
current.value = value
return
# 设置新节点的父节点
new_node.parent = parent
# 更新父节点的子节点引用
if parent == self.NIL:
self.root = new_node # 树为空，新节点成为根节点
elif new_node.key < parent.key:
parent.left = new_node
else:
parent.right = new_node
self.size += 1
self._insert_fixup(new_node) # 修复红黑树性质
def _insert_fixup(self, node: Node) -> None:
"""插入后修复红黑树性质"""
while node.parent.color == 'RED':
# 父节点是祖父节点的左子节点
if node.parent == node.parent.parent.left:
uncle = node.parent.parent.right # 叔节点
# 情况1：叔节点是红色
if uncle.color == 'RED':
node.parent.color = 'BLACK'
uncle.color = 'BLACK'
node.parent.parent.color = 'RED'
node = node.parent.parent
else:
# 情况2：节点是父节点的右子节点
if node == node.parent.right:
node = node.parent
self._left_rotate(node)
# 情况3：节点是父节点的左子节点
node.parent.color = 'BLACK'
node.parent.parent.color = 'RED'
self._right_rotate(node.parent.parent)
else:
# 对称情况：父节点是祖父节点的右子节点
uncle = node.parent.parent.left # 叔节点
# 情况1：叔节点是红色
if uncle.color == 'RED':
node.parent.color = 'BLACK'
uncle.color = 'BLACK'
node.parent.parent.color = 'RED'
node = node.parent.parent
else:
# 情况2：节点是父节点的左子节点
if node == node.parent.left:
node = node.parent
self._right_rotate(node)
# 情况3：节点是父节点的右子节点
node.parent.color = 'BLACK'
node.parent.parent.color = 'RED'
self._left_rotate(node.parent.parent)
# 确保根节点为黑色
self.root.color = 'BLACK'
def search(self, key: Any) -> Optional[Any]:
"""查找键对应的值"""
node = self._search_node(key)
return node.value if node != self.NIL else None
def _search_node(self, key: Any) -> Node:
"""查找指定键的节点"""
current = self.root
while current != self.NIL and key != current.key:
if key < current.key:
current = current.left
else:
current = current.right
return current
def delete(self, key: Any) -> bool:
"""删除指定键的节点"""
node = self._search_node(key)
if node == self.NIL:
return False # 节点不存在
self._delete_node(node)
self.size -= 1
return True
def _delete_node(self, node: Node) -> None:
"""删除节点核心逻辑"""
original_color = node.color
x = self.NIL
if node.left == self.NIL:
x = node.right
self._transplant(node, node.right)
elif node.right == self.NIL:
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._delete_fixup(x)
def _transplant(self, u: Node, v: Node) -> None:
"""用节点v替换节点u"""
if u.parent == self.NIL:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
def _minimum(self, node: Node) -> Node:
"""找到子树中的最小节点"""
while node.left != self.NIL:
node = node.left
return node
def _delete_fixup(self, node: Node) -> None:
"""删除后修复红黑树性质"""
while node != self.root and node.color == 'BLACK':
if node == node.parent.left:
sibling = node.parent.right
# 情况1：兄弟节点是红色
if sibling.color == 'RED':
sibling.color = 'BLACK'
node.parent.color = 'RED'
self._left_rotate(node.parent)
sibling = node.parent.right
# 情况2：兄弟节点的两个子节点都是黑色
if sibling.left.color == 'BLACK' and sibling.right.color == 'BLACK':
sibling.color = 'RED'
node = node.parent
else:
# 情况3：兄弟节点的右子节点是黑色
if sibling.right.color == 'BLACK':
sibling.left.color = 'BLACK'
sibling.color = 'RED'
self._right_rotate(sibling)
sibling = node.parent.right
# 情况4：兄弟节点的右子节点是红色
sibling.color = node.parent.color
node.parent.color = 'BLACK'
sibling.right.color = 'BLACK'
self._left_rotate(node.parent)
node = self.root
else:
# 对称情况
sibling = node.parent.left
if sibling.color == 'RED':
sibling.color = 'BLACK'
node.parent.color = 'RED'
self._right_rotate(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._left_rotate(sibling)
sibling = node.parent.left
sibling.color = node.parent.color
node.parent.color = 'BLACK'
sibling.left.color = 'BLACK'
self._right_rotate(node.parent)
node = self.root
node.color = 'BLACK'
def inorder_traversal(self) -> list:
"""中序遍历返回排序后的键值对列表"""
result = []
self._inorder(self.root, result)
return result
def _inorder(self, node: Node, result: list) -> None:
"""中序遍历辅助函数"""
if node != self.NIL:
self._inorder(node.left, result)
result.append((node.key, node.value, node.color))
self._inorder(node.right, result)
def __len__(self) -> int:
"""返回树中元素个数"""
return self.size
def __contains__(self, key: Any) -> bool:
"""检查键是否在树中"""
return self.search(key) is not None
# 测试代码
if __name__ == "__main__":
rbt = RedBlackTree()
# 插入测试
test_data = [(5, "five"), (3, "three"), (7, "seven"),
(2, "two"), (4, "four"), (6, "six"), (8, "eight")]
print("插入数据:", test_data)
for key, value in test_data:
rbt.insert(key, value)
# 遍历测试
print("\n中序遍历结果:")
for item in rbt.inorder_traversal():
print(f"Key: {item[0]}, Value: {item[1]}, Color: {item[2]}")
# 搜索测试
print(f"\n搜索测试:")
print(f"search(4) = {rbt.search(4)}")
print(f"search(10) = {rbt.search(10)}")
print(f"5 in tree: {5 in rbt}")
# 删除测试
print(f"\n删除测试:")
print(f"删除键4: {rbt.delete(4)}")
print(f"删除后搜索4: {rbt.search(4)}")
print(f"树的大小: {len(rbt)}")
print("\n删除后的中序遍历:")
for item in rbt.inorder_traversal():
print(f"Key: {item[0]}, Value: {item[1]}, Color: {item[2]}")
Comments NOTHING