第8章 平衡树与搜索树
8.1 引言
第7章讨论的二叉树仅关注节点的层级关系，未对节点值的有序性做约束，导致数据搜索需遍历所有节点（时间复杂度O(n)）。在实际工程中，“高效搜索”是核心需求之一——例如，通讯录需快速查找联系人，数据库需快速定位记录。搜索树（Search Tree） 通过定义节点值的大小关系，将搜索操作优化至O(log n)；而平衡树（Balanced Tree） 则解决搜索树在频繁插入/删除后可能出现的“失衡退化”问题，确保长期高效运行。
二叉搜索树（Binary Search Tree, BST） 是最基础的搜索树，其核心特性为：左子树所有节点值 < 根节点值 < 右子树所有节点值。这一特性使其中序遍历序列为升序，支持“二分查找”式的高效操作。但BST的性能依赖树的平衡性：若插入序列有序（如1,2,3,4），BST会退化为斜树（类似链表），此时查找、插入、删除操作的时间复杂度均退化为O(n)。
为解决BST的失衡问题，平衡二叉树应运而生。AVL树通过严格控制“任意节点左右子树高度差≤1”维持平衡，查找效率极高但旋转操作频繁；红黑树则通过“颜色规则”和“局部旋转”实现近似平衡，插入删除效率更优，是工业界的主流选择（如Java TreeMap、Linux内核调度）。
本章将从“搜索需求”出发，先详解BST的原理与实现，再分析其失衡痛点，进而引出AVL树和红黑树的平衡策略，最终通过对比各类树的特性，帮助读者掌握“基于场景选择搜索树”的工程思维。
8.2 二叉搜索树（BST）
8.2.1 定义与核心特性
定义8.1 二叉搜索树（BST）：一棵二叉树，若不为空，则满足：
1.左子树中所有节点的值 < 根节点的值；
2.右子树中所有节点的值 > 根节点的值；
3.左、右子树本身也都是二叉搜索树（递归定义）。
核心特性：
中序遍历序列为升序：这是BST区别于普通二叉树的关键，也是实现高效搜索的基础。
搜索路径唯一：对给定值，从根节点出发，通过与当前节点值的比较（小于则向左，大于则向右），可唯一确定搜索路径。
示例BST结构：

	6 
	/  
	3 8 
	/  /  
	2 4 7 9 
	/  
	1 5

其中序遍历序列为：1,2,3,4,5,6,7,8,9（严格升序）。
8.2.2 基本操作实现

1. 查找操作
   目标：在BST中查找值为target的节点，返回节点引用或None。
   原理：利用BST的有序性，从根节点开始递归或迭代比较：
   若target == 当前节点值：找到目标节点；
   若target < 当前节点值：递归查找左子树；
   若target > 当前节点值：递归查找右子树；
   若子树为空：未找到。
   Python实现（迭代版）：
   python

	class BSTNode: 
	"""BST节点类""" 
	def __init__(self, data): 
	self.data = data 
	self.left = None # 左子节点 
	self.right = None # 右子节点 
	
	def bst_search(root: BSTNode, target: int) -> BSTNode: 
	"""BST查找操作（迭代实现）""" 
	current = root 
	while current: 
	if target == current.data: 
	return current # 找到目标节点 
	elif target < current.data: 
	current = current.left # 向左子树查找 
	else: 
	current = current.right # 向右子树查找 
	return None # 未找到

示例：在上述BST中查找5：路径为6→3→4→5，返回值为5的节点；查找10：路径为6→8→9→None，返回None。
时间复杂度：
理想情况（平衡BST）：O(log n)，树高h=log n；
最坏情况（斜树）：O(n)，树高h=n（如插入序列1,2,3,4,5形成的左斜树）。
2. 插入操作
目标：在BST中插入值为data的新节点，维持BST的有序性。
原理：
若树为空：直接创建新节点作为根；
否则从根节点开始比较：
o若data < 当前节点值：向左子树插入（若左子树为空，新节点作为左子节点）；
o若data > 当前节点值：向右子树插入（若右子树为空，新节点作为右子节点）；
o注意：BST通常不允许重复值（若需支持重复值，可在节点中增加计数属性）。
Python实现（递归版）：
python

	def bst_insert(root: BSTNode, data: int) -> BSTNode: 
	"""BST插入操作（递归实现，返回插入后新根节点）""" 
	if root is None: 
	return BSTNode(data) # 树空，创建新节点 
	if data < root.data: 
	root.left = bst_insert(root.left, data) # 插入左子树 
	elif data > root.data: 
	root.right = bst_insert(root.right, data) # 插入右子树 
	else: 
	# 重复值处理（此处选择忽略） 
	pass 
	return root

示例：向空树插入序列[6,3,8,2,4,7,9,1,5]，得到上述示例BST结构。
3. 删除操作
目标：删除BST中值为data的节点，维持BST的有序性。
难点：删除节点后需填补其位置，且保证“左<根<右”的关系。根据节点的度（子节点数量）分三种情况处理：
情况1：删除叶子节点（度为0）
操作：直接将其父节点的对应子节点引用设为None。
示例：删除上述BST中的1（叶子节点）：其父节点2的左子节点设为None，树结构变为：

	6 
	/  
	3 8 
	/  /  
	2 4 7 9 
	 
	5

情况2：删除度为1的节点
操作：将其父节点的对应子节点引用指向被删节点的唯一子节点。
示例：删除上述BST中的2（度为1，右子节点为None，左子节点为None？不，原BST中2的左子节点是1，删除1后2成为叶子节点（度0）。若删除7（度为0，叶子节点），其父节点8的左子节点设为None。
情况3：删除度为2的节点
操作：需找到中序前驱（左子树中最大节点，即左子树最右节点）或中序后继（右子树中最小节点，即右子树最左节点）替换被删节点，再删除前驱/后继节点（前驱/后继的度必为0或1，转化为情况1或2）。
示例：删除上述BST中的根节点6（度为2）：
中序遍历序列为1,2,3,4,5,6,7,8,9，中序前驱为5（左子树最大节点），中序后继为7（右子树最小节点）；
选择后继7替换6，删除原7节点（叶子节点），新树结构为：

	7 
	/  
	3 8 
	/   
	2 4 9 
	/  
	1 5

Python实现（基于中序后继）：
python

	def bst_delete(root: BSTNode, data: int) -> BSTNode: 
	"""BST删除操作（递归实现，返回删除后新根节点）""" 
	if root is None: 
	return None # 未找到节点 
	# 步骤1：查找待删除节点 
	if data < root.data: 
	root.left = bst_delete(root.left, data) 
	return root 
	elif data > root.data: 
	root.right = bst_delete(root.right, data) 
	return root 
	# 步骤2：删除当前节点（已找到） 
	# 情况1/2：度为0或1（左子树空或右子树空） 
	if root.left is None: 
	return root.right # 返回右子树（若右子树空则返回None） 
	elif root.right is None: 
	return root.left # 返回左子树 
	# 情况3：度为2，找中序后继（右子树最小节点） 
	successor_parent = root 
	successor = root.right 
	while successor.left: # 遍历到右子树最左节点（最小节点） 
	successor_parent = successor 
	successor = successor.left 
	# 替换当前节点值为后继值 
	root.data = successor.data 
	# 删除后继节点（后继度为0或1） 
	if successor_parent == root: 
	successor_parent.right = successor.right # 后继是右子树直接节点 
	else: 
	successor_parent.left = successor.right # 后继是右子树的左子节点 
	return root

8.2.3 BST的局限性
BST的高效操作依赖于树的平衡性，但实际应用中，插入/删除序列的有序性会导致BST失衡：
示例：插入序列[1,2,3,4,5]，BST退化为右斜树：

	1 
	 
	2 
	 
	3 
	 
	4 
	 
	5

此时查找、插入、删除操作的时间复杂度均退化为O(n)，与链表无异。
解决方案：引入平衡树，通过主动调整树结构，保证树高始终为O(log n)，从而维持O(log n)的操作复杂度。
8.3 AVL树：严格平衡的BST
8.3.1 定义与平衡因子
定义8.2 AVL树：一种自平衡的二叉搜索树，满足：
1.本身是一棵BST；
2.任意节点的平衡因子（Balance Factor, BF） 的绝对值 ≤ 1。
平衡因子（BF）：节点左子树高度与右子树高度的差，即
BF(node)=height(node.left)−height(node.right) ext{BF}(node) = ext{height}(node.left) - ext{height}(node.right) BF(node)=height(node.left)−height(node.right)
若BF=2：左子树过高，需右旋；
若BF=-2：右子树过高，需左旋；
节点高度定义：height(node) = 1 + max(height(node.left), height(node.right))（空节点高度为-1）。
8.3.2 旋转操作：平衡调整的核心
当插入/删除导致节点BF绝对值>1时，AVL树通过旋转操作调整结构，恢复平衡。旋转分为四种类型，本质是通过改变节点间的父子关系，降低树高。

1. LL旋转（左左旋转）
   失衡场景：新节点插入到左子树的左子树，导致根节点BF=2，左子节点BF≥0。
   调整步骤（以节点A失衡为例）：

	A (BF=2) B 
	/  /  
	B C → D A 
	/  /  
	D E E C

节点B作为新根；
A的左子树更新为B的右子树（E）；
B的右子树更新为A。
Python实现：
python

	def avl_rotate_right(z: BSTNode) -> BSTNode: 
	"""右旋操作（LL旋转），返回旋转后新根节点""" 
	y = z.left # y是z的左子节点 
	t3 = y.right # t3是y的右子树 
	
	# 执行旋转 
	y.right = z # z成为y的右子节点 
	z.left = t3 # t3成为z的左子节点 
	
	# 更新高度（需为节点添加height属性，此处省略具体实现） 
	# z.height = 1 + max(height(z.left), height(z.right)) 
	# y.height = 1 + max(height(y.left), height(y.right)) 
	
	return y # y成为新根

2. RR旋转（右右旋转）
   失衡场景：新节点插入到右子树的右子树，导致根节点BF=-2，右子节点BF≤0。
   调整步骤（以节点A失衡为例）：

	A (BF=-2) B 
	/  /  
	B C → A C 
	/  /  
	D E D E

节点B作为新根；
A的右子树更新为B的左子树（D）；
B的左子树更新为A。
Python实现：
python

	def avl_rotate_left(z: BSTNode) -> BSTNode: 
	"""左旋操作（RR旋转），返回旋转后新根节点""" 
	y = z.right # y是z的右子节点 
	t2 = y.left # t2是y的左子树 
	
	# 执行旋转 
	y.left = z # z成为y的左子节点 
	z.right = t2 # t2成为z的右子节点 
	
	# 更新高度（省略） 
	# z.height = 1 + max(height(z.left), height(z.right)) 
	# y.height = 1 + max(height(y.left), height(y.right)) 
	
	return y # y成为新根

3. LR旋转（左右旋转）
   失衡场景：新节点插入到左子树的右子树，导致根节点BF=2，左子节点BF=-1。
   调整步骤：先对左子节点执行RR旋转（转为LL场景），再对根节点执行LL旋转：

	A (BF=2) A C 
	/  /  /  
	B C → C E → B A 
	/  /  /  /  
	D B' B F D F G E 
	/  /  
	F G D G

4. RL旋转（右左旋转）
   失衡场景：新节点插入到右子树的左子树，导致根节点BF=-2，右子节点BF=1。
   调整步骤：先对右子节点执行LL旋转（转为RR场景），再对根节点执行RR旋转。
   8.3.3 AVL树的插入操作
   AVL树的插入流程：
   1.按BST规则插入新节点；
   2.从新节点向上回溯，更新各祖先节点的高度；
   3.对每个节点计算BF，若|BF|>1，根据失衡类型执行旋转；
   4.旋转后树恢复平衡，停止回溯。
   示例：插入5到AVL树[3,1,4]：
   插入后树结构（节点高度标注在括号内）：

	3(2) 
	/  
	1(0) 4(1) 
	 
	5(0)

节点4的BF=-1（右高），节点3的BF=1-2=-1（平衡），无需旋转。
8.3.4 AVL树的特点
优点：严格平衡，树高h≈1.44log(n+2)-1.328，查找效率极高（O(log n)）。
缺点：插入/删除后可能需要多次旋转（最多O(log n)次），且需存储节点高度，适合读多写少场景。
8.4 红黑树：近似平衡的BST
AVL树虽平衡严格，但旋转开销大，在插入删除密集场景中性能不佳。红黑树（Red-Black Tree） 通过放松平衡要求，以“颜色规则”维持近似平衡，减少旋转次数，是工业界的主流选择。
8.4.1 红黑树的5条核心性质
红黑树是每个节点带有颜色（红/黑）的BST，满足以下性质：
1.根节点是黑色；
2.所有叶子节点（NIL节点，空节点）是黑色（实际实现中可用None表示，默认视为黑）；
3.若一个节点是红色，则其两个子节点必为黑色（父子节点不能同为红色）；
4.从任意节点到其所有叶子节点的路径中，黑色节点数量相同（称为“黑高”相等）；
5.新插入节点默认为红色（减少违反性质的可能性）。
平衡保障：性质3和4确保“最长路径长度 ≤ 2×最短路径长度”（最短路径全黑，最长路径红黑交替），树高h≤2log(n+1)，操作复杂度仍为O(log n)。
8.4.2 红黑树的插入与平衡调整
红黑树插入流程：
1.按BST规则插入新节点（默认为红色）；
2.检查是否违反红黑树性质，若违反则通过变色和旋转调整。
调整场景（设新节点为N，父节点为P，祖父为G，叔叔为U）：
场景1：P是黑色
不违反任何性质，无需调整。
场景2：P是红色，U是红色（“红红”且有红叔）
操作：P和U变为黑色，G变为红色（若G是根，需再变黑）。
原理：保持黑高不变，消除“父子同红”。
场景3：P是红色，U是黑色（“红红”且黑叔）
操作：根据N的位置执行旋转+变色：
oN是P的左子节点（LL型）：P变黑，G变红，对G右旋；
oN是P的右子节点（LR型）：N变黑，G变红，对P左旋后对G右旋；
o右子树对称情况（RR型、RL型）类似，左旋处理。
8.4.3 红黑树 vs AVL树

8.5 工程应用与场景选择

1. 数据库索引
   B+树（平衡树变种）：所有叶子节点连成链表，支持高效范围查询，是MySQL InnoDB的默认索引结构。
2. 集合类实现
   Java TreeMap、C++ std::map基于红黑树实现，支持O(log n)的插入、删除和有序遍历。
3. 缓存系统
   TreeCache（基于红黑树）支持按key有序淘汰，结合LRU策略实现高效缓存管理。
   8.6 本章总结
   BST通过“左<根<右”的有序性实现O(log n)搜索，但依赖平衡；
   AVL树以严格平衡因子（|BF|≤1）保证高效查找，适合读多写少场景；
   红黑树以颜色规则维持近似平衡，旋转开销低，适合写密集场景，是工业界首选。
   选择时需权衡“查找效率”与“插入删除开销”：读多写少用AVL树，写多读少用红黑树，范围查询用B+树。
   思考题
   1.设计函数判断一棵二叉树是否为BST（提示：中序遍历是否升序，或递归检查左子树最大值<根<右子树最小值）。
   2.实现AVL树的删除操作（提示：删除后需回溯更新高度，判断失衡类型并旋转）。
   3.红黑树中，新节点为何默认为红色？若设为黑色会违反哪条性质？
   4.对比BST、AVL树、红黑树在插入100万条随机数据后的树高和平均查找次数。
   5.为什么MySQL选择B+树而非红黑树作为索引？（提示：B+树叶子节点链表优化范围查询）。

8.5 工程应用与场景选择

1. 数据库索引
   B+树（平衡树变种）：所有叶子节点连成链表，支持高效范围查询，是MySQL InnoDB的默认索引结构。
2. 集合类实现
   Java TreeMap、C++ std::map基于红黑树实现，支持O(log n)的插入、删除和有序遍历。
3. 缓存系统
   TreeCache（基于红黑树）支持按key有序淘汰，结合LRU策略实现高效缓存管理。
   8.6 本章总结
   BST通过“左<根<右”的有序性实现O(log n)搜索，但依赖平衡；
   AVL树以严格平衡因子（|BF|≤1）保证高效查找，适合读多写少场景；
   红黑树以颜色规则维持近似平衡，旋转开销低，适合写密集场景，是工业界首选。
   选择时需权衡“查找效率”与“插入删除开销”：读多写少用AVL树，写多读少用红黑树，范围查询用B+树。
   思考题
   1.设计函数判断一棵二叉树是否为BST（提示：中序遍历是否升序，或递归检查左子树最大值<根<右子树最小值）。
   2.实现AVL树的删除操作（提示：删除后需回溯更新高度，判断失衡类型并旋转）。
   3.红黑树中，新节点为何默认为红色？若设为黑色会违反哪条性质？
   4.对比BST、AVL树、红黑树在插入100万条随机数据后的树高和平均查找次数。
   5.为什么MySQL选择B+树而非红黑树作为索引？（提示：B+树叶子节点链表优化范围查询）。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49294.html