第7章 二叉搜索树（BST）与平衡树
7.1 二叉搜索树（Binary Search Tree, BST）
7.1.1 定义与核心特性
二叉搜索树（BST） 是一种特殊的二叉树，其每个节点的值满足以下性质：
左子树中所有节点的值 小于 当前节点的值；
右子树中所有节点的值 大于 当前节点的值；
左右子树本身也为二叉搜索树（递归定义）。
核心特性：BST的中序遍历序列是严格递增的（假设节点值互不重复）。这一特性是BST查找、插入、删除操作的基础。
示例：图7-1为一棵BST，其中序遍历序列为[2,3,4,5,6,7,8]，符合递增特性。

	5 
	/ \ 
	3 7 
	/ \ / \ 
	2 4 6 8

图7-1 二叉搜索树示例
7.1.2 BST的节点结构
BST节点需存储值、左子树指针、右子树指针，结构定义如下（Python）：
python

	class TreeNode:
	def __init__(self, val: int):
	self.val = val # 节点值
	self.left = None # 左子树指针
	self.right = None # 右子树指针

7.2 BST的基本操作
7.2.1 查找操作
目标：给定值target，在BST中查找是否存在该值，若存在返回节点，否则返回None。
算法逻辑：
从根节点开始，比较当前节点值与target：
o若当前节点值 等于 target，找到目标节点，返回；
o若当前节点值 大于 target，则目标在左子树，递归或迭代查找左子树；
o若当前节点值 小于 target，则目标在右子树，递归或迭代查找右子树；
若遍历至None（空树），则目标不存在，返回None。
递归实现
python

	def bst_search_recursive(root: TreeNode, target: int) -> TreeNode:
	"""BST查找（递归），返回值为target的节点，不存在返回None"""
	if not root:
	return None # 空树，目标不存在
	if root.val == target:
	return root # 找到目标
	elif root.val > target:
	return bst_search_recursive(root.left, target) # 左子树查找
	else:
	return bst_search_recursive(root.right, target) # 右子树查找

非递归实现（迭代）
python

	def bst_search_iterative(root: TreeNode, target: int) -> TreeNode:
	"""BST查找（非递归），返回值为target的节点，不存在返回None"""
	current = root
	while current:
	if current.val == target:
	return current # 找到目标
	elif current.val > target:
	current = current.left # 左子树查找
	else:
	current = current.right # 右子树查找
	return None # 遍历结束，目标不存在

时间复杂度：理想情况下（平衡BST）为 O(log⁡n)O(\log n)O(logn)（树高为 log⁡n\log nlogn）；最坏情况下（退化为链表）为 O(n)O(n)O(n)。
7.2.2 插入操作
目标：将值val插入BST，保持BST的特性。
算法逻辑：
若树为空，直接以val为根节点；
否则从根节点开始，比较当前节点值与val：
o若val < 当前节点值：若左子树为空，则插入左子树；否则递归/迭代插入左子树；
o若val > 当前节点值：若右子树为空，则插入右子树；否则递归/迭代插入右子树；
注意：BST中通常不允许重复值（若需支持重复值，可定义“左子树≤根”或“右子树≥根”，此处假设值唯一）。
递归实现
python

	def bst_insert_recursive(root: TreeNode, val: int) -> TreeNode:
	"""BST插入（递归），返回插入后的根节点"""
	if not root:
	return TreeNode(val) # 空树，创建新节点作为根
	if val < root.val:
	root.left = bst_insert_recursive(root.left, val) # 插入左子树
	else:
	root.right = bst_insert_recursive(root.right, val) # 插入右子树
	return root # 返回当前节点（维持树结构）

非递归实现
python

	def bst_insert_iterative(root: TreeNode, val: int) -> TreeNode:
	"""BST插入（非递归），返回插入后的根节点"""
	if not root:
	return TreeNode(val) # 空树，直接返回新节点
	current = root
	parent = None # 记录current的父节点，用于插入新节点
	while current:
	parent = current
	if val < current.val:
	current = current.left
	else:
	current = current.right
	# 插入新节点到parent的左或右子树
	if val < parent.val:
	parent.left = TreeNode(val)
	else:
	parent.right = TreeNode(val)
	return root # 根节点不变（除非原树为空）

时间复杂度：同查找操作，理想 O(log⁡n)O(\log n)O(logn)，最坏 O(n)O(n)O(n)。
7.2.3 删除操作
目标：删除BST中值为val的节点，保持BST特性。
难点：删除节点后需重新连接子树，需分情况讨论节点的子树结构。
分类讨论（设待删除节点为node）：
情况1：node为叶子节点（无左右子树）
直接删除node，将其父节点指向node的指针置为None。
示例：删除图7-1中的节点2（叶子节点），其父节点3的左指针置为None。
情况2：node只有左子树或只有右子树
删除node，将其父节点指向node的指针改为指向node的左子树（若只有左子树）或右子树（若只有右子树）。
示例：删除图7-1中的节点3（只有左子树2和右子树4），若节点3只有左子树2，则其父节点5的左指针指向2。
情况3：node既有左子树也有右子树（最复杂）
需找到node的前驱或后继节点替换node，再删除前驱或后继节点（前驱/后继为叶子节点或只有一棵子树，属于情况1或2）：
前驱节点：node左子树中的最大值（左子树最右节点）；
后继节点：node右子树中的最小值（右子树最左节点）。
步骤：
1.找到node的后继节点successor（右子树最左节点）；
2.用successor.val替换node.val；
3.删除successor节点（successor最多只有右子树，属于情况2）。
算法实现（递归）
python

	def bst_delete(root: TreeNode, val: int) -> TreeNode:
	"""BST删除（递归），返回删除后的根节点"""
	if not root:
	return None # 空树，无需删除
	
	# 步骤1：查找待删除节点
	if val < root.val:
	root.left = bst_delete(root.left, val) # 左子树删除
	elif val > root.val:
	root.right = bst_delete(root.right, val) # 右子树删除
	else: # 找到待删除节点root
	# 情况1：叶子节点或只有一棵子树
	if not root.left:
	return root.right # 无左子树，返回右子树（可能为None）
	elif not root.right:
	return root.left # 无右子树，返回左子树（可能为None）
	# 情况2：既有左子树也有右子树，找后继节点（右子树最左节点）
	successor = root.right
	while successor.left: # 遍历至右子树最左节点（最小值）
	successor = successor.left
	root.val = successor.val # 用后继节点值替换当前节点值
	# 删除后继节点（后继最多只有右子树，递归删除）
	root.right = bst_delete(root.right, successor.val)
	
	return root # 返回当前节点（维持树结构）

时间复杂度：理想 O(log⁡n)O(\log n)O(logn)，最坏 O(n)O(n)O(n)。
7.3 BST的平衡性问题
平衡BST：树高为 O(log⁡n)O(\log n)O(logn) 的BST，此时查找、插入、删除操作效率均为 O(log⁡n)O(\log n)O(logn)。
失衡问题：若BST插入的序列接近有序（如递增或递减），会导致树退化为链表，此时树高为 O(n)O(n)O(n)，操作效率降至 O(n)O(n)O(n)。
示例：插入序列[1,2,3,4,5]，BST退化为：

	1 
	\ 
	2 
	\ 
	3 
	\ 
	4 
	\ 
	5

此时查找值5需遍历5个节点，效率极低。
解决方案：引入平衡二叉搜索树，通过特定机制（如旋转、颜色约束）维持树的平衡，确保树高始终为 O(log⁡n)O(\log n)O(logn)。常见平衡树包括AVL树和红黑树。
7.4 平衡二叉搜索树（AVL树）
AVL树（以发明者Adelson-Velsky和Landis命名）是最早的平衡二叉搜索树，其核心是通过平衡因子和旋转操作维持平衡。
7.4.1 AVL树的定义
平衡因子（Balance Factor, BF）：节点的左子树高度减去右子树高度（或反之），即 BF(node)=height(left)−height(right)BF(node) = height(left) - height(right)BF(node)=height(left)−height(right)。
平衡条件：任意节点的平衡因子的绝对值 ≤ 1（即 −1≤BF≤1-1 \leq BF \leq 1−1≤BF≤1）。
树高：含 nnn 个节点的AVL树的树高 h≈1.44log⁡(n+2)−1.328h \approx 1.44\log(n+2) - 1.328h≈1.44log(n+2)−1.328，为 O(log⁡n)O(\log n)O(logn)。
7.4.2 AVL树的节点结构
需额外存储节点高度（用于计算平衡因子）：
python

	class AVLNode(TreeNode):
	def __init__(self, val: int):
	super().__init__(val)
	self.height = 1 # 节点高度（叶节点高度为1，空树高度为0）

7.4.3 旋转操作（核心平衡机制）
当插入或删除节点导致平衡因子绝对值 > 1时，需通过旋转调整树结构，恢复平衡。旋转分为四种类型，本质是通过局部子树的旋转，降低树高，修正平衡因子。
（1）LL旋转（左左型）
场景：节点的左子树的左子树导致失衡（BF(node)=2BF(node) = 2BF(node)=2，BF(left)=1BF(left) = 1BF(left)=1）。
操作步骤：
1.设节点为A，左子树为B，B的左子树为C；
2.将B的右子树作为A的左子树；
3.将A作为B的右子树；
4.更新A和B的高度（A的高度为max(height(A.left), height(A.right)) + 1，B的高度为max(height(B.left), height(A)) + 1）。
图示（简化）：

	A B 
	/ \ / \ 
	B T4 → C A 
	/ \ / \ 
	C T3 T3 T4 
	/ \ 
	T1 T2

代码实现：
python

	def avl_ll_rotate(node: AVLNode) -> AVLNode:
	"""LL旋转，返回旋转后的新根节点（原左子树）"""
	left_child = node.left # B为A的左子树
	node.left = left_child.right # A的左子树 = B的右子树（T3）
	left_child.right = node # B的右子树 = A
	
	# 更新A和B的高度（先更新A，再更新B）
	node.height = 1 + max(
	node.left.height if node.left else 0,
	node.right.height if node.right else 0
	)
	left_child.height = 1 + max(
	left_child.left.height if left_child.left else 0,
	node.height
	)
	return left_child # B成为新根

（2）RR旋转（右右型）
场景：节点的右子树的右子树导致失衡（BF(node)=−2BF(node) = -2BF(node)=−2，BF(right)=−1BF(right) = -1BF(right)=−1）。
操作步骤：与LL旋转对称，将右子树作为新根，原根作为新根的左子树。
图示（简化）：

	A B 
	\ / \ 
	B → A C 
	/ \ / \ 
	T3 C T1 T3 
	/ \ 
	T1 T2

代码实现：
python

	def avl_rr_rotate(node: AVLNode) -> AVLNode:
	"""RR旋转，返回旋转后的新根节点（原右子树）"""
	right_child = node.right # B为A的右子树
	node.right = right_child.left # A的右子树 = B的左子树（T3）
	right_child.left = node # B的左子树 = A
	
	# 更新A和B的高度
	node.height = 1 + max(
	node.left.height if node.left else 0,
	node.right.height if node.right else 0
	)
	right_child.height = 1 + max(
	node.height,
	right_child.right.height if right_child.right else 0
	)
	return right_child # B成为新根

（3）LR旋转（左右型）
场景：节点的左子树的右子树导致失衡（BF(node)=2BF(node) = 2BF(node)=2，BF(left)=−1BF(left) = -1BF(left)=−1）。
操作步骤：先对左子树执行RR旋转，再对原节点执行LL旋转（两次旋转）。
图示（简化）：

	A A C 
	/ \ / \ / \ 
	B T4 → C T4 → B A 
	/ \ / \ / \ / \ 
	T1 C B T3 T1 T2 T3 T4 
	/ \ / \ 
	T2 T3 T1 T2

代码实现：
python

	def avl_lr_rotate(node: AVLNode) -> AVLNode:
	"""LR旋转（先对左子树RR旋转，再对当前节点LL旋转）"""
	node.left = avl_rr_rotate(node.left) # 左子树RR旋转
	return avl_ll_rotate(node) # 当前节点LL旋转

（4）RL旋转（右左型）
场景：节点的右子树的左子树导致失衡（BF(node)=−2BF(node) = -2BF(node)=−2，BF(right)=1BF(right) = 1BF(right)=1）。
操作步骤：先对右子树执行LL旋转，再对原节点执行RR旋转（两次旋转）。
代码实现：
python

	def avl_rl_rotate(node: AVLNode) -> AVLNode:
	"""RL旋转（先对右子树LL旋转，再对当前节点RR旋转）"""
	node.right = avl_ll_rotate(node.right) # 右子树LL旋转
	return avl_rr_rotate(node) # 当前节点RR旋转

7.4.4 AVL树的插入操作
步骤：
1.按BST插入规则插入新节点；
2.回溯更新插入路径上所有节点的高度；
3.计算每个节点的平衡因子，若失衡（∣BF∣>1|BF| > 1∣BF∣>1），根据失衡类型执行相应旋转（LL/RR/LR/RL）；
4.返回调整后的根节点。
代码实现：
python

	def avl_insert(root: AVLNode, val: int) -> AVLNode:
	"""AVL树插入，返回插入并平衡后的根节点"""
	# 步骤1：BST插入
	if not root:
	return AVLNode(val) # 空树，创建新节点
	if val < root.val:
	root.left = avl_insert(root.left, val) # 插入左子树
	else:
	root.right = avl_insert(root.right, val) # 插入右子树
	
	# 步骤2：更新当前节点高度
	root.height = 1 + max(
	root.left.height if root.left else 0,
	root.right.height if root.right else 0
	)
	
	# 步骤3：计算平衡因子，判断是否失衡
	left_height = root.left.height if root.left else 0
	right_height = root.right.height if root.right else 0
	bf = left_height - right_height # 平衡因子 = 左高 - 右高
	
	# 步骤4：根据失衡类型旋转调整
	# LL型：BF=2且左子树BF=1
	if bf > 1 and (root.left.left.height if root.left and root.left.left else 0) >= (root.left.right.height if root.left and root.left.right else 0):
	return avl_ll_rotate(root)
	# RR型：BF=-2且右子树BF=-1
	if bf < -1 and (root.right.right.height if root.right and root.right.right else 0) >= (root.right.left.height if root.right and root.right.left else 0):
	return avl_rr_rotate(root)
	# LR型：BF=2且左子树BF=-1
	if bf > 1 and (root.left.right.height if root.left and root.left.right else 0) > (root.left.left.height if root.left and root.left.left else 0):
	return avl_lr_rotate(root)
	# RL型：BF=-2且右子树BF=1
	if bf < -1 and (root.right.left.height if root.right and root.right.left else 0) > (root.right.right.height if root.right and root.right.right else 0):
	return avl_rl_rotate(root)
	
	# 未失衡，返回当前节点
	return root

7.5 红黑树
红黑树是另一种平衡二叉搜索树，通过颜色规则而非严格的平衡因子维持“黑平衡”（从根到叶子的所有路径包含相同数量的黑节点），平衡性要求低于AVL树，但插入/删除的旋转操作更少，实际应用更广泛（如C++ std::map、Java TreeMap）。
7.5.1 红黑树的颜色规则
1.节点颜色：每个节点非红即黑；
2.根节点：根节点为黑色；
3.叶子节点：所有叶子节点为黑色（通常用None表示“NIL叶子”，视为黑色）；
4.红节点约束：红色节点的左右子节点均为黑色（即“无连续红节点”）；
5.黑平衡：从任一节点到其所有叶子节点的路径中，黑色节点数量相同（称为“黑高”）。
7.5.2 红黑树的插入操作
插入步骤：
1.按BST规则插入新节点，初始颜色设为红色（减少黑平衡破坏的概率）；
2.检查是否违反红黑规则，若违反则通过变色和旋转修复（主要修复规则4和5）。
修复场景（设新节点为z，父节点为p，祖父节点为g，叔叔节点为u）：
场景1：p为黑色 → 无违反规则，无需修复；
场景2：p为红色（违反规则4），此时g必为黑色（否则插入前已违反规则4），需根据u的颜色进一步处理：
o子场景2.1：u为红色 → 变色（p和u变黑，g变红），g成为新的z，继续向上修复；
o子场景2.2：u为黑色（或NIL） → 旋转（LL/RR/LR/RL）+ 变色（p变黑，g变红），修复结束。
示例：插入新节点z（红色），p为红色，u为黑色，且z是p的右子节点，p是g的左子节点（LR型），需先对p左旋，再对g右旋，最后p变黑，g变红。
7.5.3 红黑树与AVL树的对比

7.6 总结
BST：通过“左小右大”特性实现高效查找/插入/删除，但可能因有序插入退化为链表，效率降至 O(n)O(n)O(n)；
AVL树：通过平衡因子（左右子树高度差≤1）维持严格平衡，树高 O(log⁡n)O(\log n)O(logn)，查询效率高，但插入/删除需多次旋转；
红黑树：通过颜色规则维持黑平衡，树高 O(2log⁡n)O(2\log n)O(2logn)，插入/删除旋转少，适合频繁动态操作场景。
平衡树的核心是通过约束条件将树高控制在 O(log⁡n)O(\log n)O(logn)，确保基本操作的高效性，是实现高效映射、集合等数据结构的基础。<|FCResponseEnd|># 第7章 二叉搜索树（BST）与平衡树
7.1 二叉搜索树（BST）的定义与特性
二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其节点值满足以下核心性质：
左子树中所有节点的值 小于 当前节点的值；
右子树中所有节点的值 大于 当前节点的值；
左右子树本身也为二叉搜索树（递归定义）。
关键推论：BST的中序遍历序列是严格递增的（假设所有节点值互不重复）。这一特性是BST查找、插入、删除操作的基础。
7.1.1 BST的节点结构
BST节点包含值、左子树指针和右子树指针，结构定义如下：
python

	class TreeNode:
	def __init__(self, val: int):
	self.val = val # 节点值
	self.left = None # 左子树指针
	self.right = None # 右子树指针

7.2 BST的基本操作
7.2.1 查找操作
目标：在BST中查找值为target的节点，若存在返回节点，否则返回None。
算法逻辑：
从根节点开始，通过值比较决定查找方向：
若当前节点值 等于 target，找到目标节点；
若当前节点值 大于 target，递归/迭代查找左子树；
若当前节点值 小于 target，递归/迭代查找右子树；
若遍历至空树（None），目标不存在。
递归实现
python

	def bst_search_recursive(root: TreeNode, target: int) -> TreeNode:
	if not root:
	return None # 空树，目标不存在
	if root.val == target:
	return root # 找到目标节点
	elif root.val > target:
	return bst_search_recursive(root.left, target) # 左子树查找
	else:
	return bst_search_recursive(root.right, target) # 右子树查找

非递归实现
python

	def bst_search_iterative(root: TreeNode, target: int) -> TreeNode:
	current = root
	while current:
	if current.val == target:
	return current # 找到目标节点
	elif current.val > target:
	current = current.left # 左子树查找
	else:
	current = current.right # 右子树查找
	return None # 遍历结束，目标不存在

时间复杂度：理想情况下（平衡BST）为 O(log⁡n)O(\log n)O(logn)（树高 h=log⁡nh = \log nh=logn）；最坏情况下（退化为链表）为 O(n)O(n)O(n)。
7.2.2 插入操作
目标：将值val插入BST，维持“左小右大”特性。
算法逻辑：
若树为空，直接以val为根节点；
否则从根节点开始，通过值比较定位插入位置：
o若val < 当前节点值，向左子树递归/迭代查找插入位置；
o若val > 当前节点值，向右子树递归/迭代查找插入位置；
o插入位置为空指针处（即叶子节点的左/右子树）。
递归实现
python

	def bst_insert_recursive(root: TreeNode, val: int) -> TreeNode:
	if not root:
	return TreeNode(val) # 空树，创建新节点作为根
	if val < root.val:
	root.left = bst_insert_recursive(root.left, val) # 插入左子树
	else:
	root.right = bst_insert_recursive(root.right, val) # 插入右子树
	return root # 返回当前节点，维持树结构

非递归实现
python

	def bst_insert_iterative(root: TreeNode, val: int) -> TreeNode:
	if not root:
	return TreeNode(val) # 空树，直接返回新节点
	current = root
	parent = None # 记录current的父节点，用于插入新节点
	while current:
	parent = current
	if val < current.val:
	current = current.left
	else:
	current = current.right
	# 插入新节点到parent的左或右子树
	if val < parent.val:
	parent.left = TreeNode(val)
	else:
	parent.right = TreeNode(val)
	return root # 根节点不变（除非原树为空）

7.2.3 删除操作
目标：删除值为val的节点，维持BST特性。
难点：删除节点后需重新连接子树，需根据节点的子树结构分情况处理。
分类讨论（设待删除节点为node）
1.叶子节点（无左右子树）：直接删除node，父节点指向node的指针置为None；
2.只有左子树或只有右子树：删除node，父节点指针指向node的左子树（若只有左子树）或右子树（若只有右子树）；
3.既有左子树也有右子树：用node的前驱（左子树最大值，即左子树最右节点）或后继（右子树最小值，即右子树最左节点）替换node，再删除前驱或后继（前驱/后继为叶子节点或只有一棵子树，属于情况1或2）。
算法实现（递归）
python

	def bst_delete(root: TreeNode, val: int) -> TreeNode:
	if not root:
	return None # 空树，无需删除
	
	# 步骤1：查找待删除节点
	if val < root.val:
	root.left = bst_delete(root.left, val) # 左子树删除
	elif val > root.val:
	root.right = bst_delete(root.right, val) # 右子树删除
	else: # 找到待删除节点root
	# 情况1/2：叶子节点或只有一棵子树
	if not root.left:
	return root.right # 无左子树，返回右子树（可能为None）
	elif not root.right:
	return root.left # 无右子树，返回左子树（可能为None）
	# 情况3：既有左右子树，找后继节点（右子树最左节点）
	successor = root.right
	while successor.left: # 遍历至右子树最左节点（最小值）
	successor = successor.left
	root.val = successor.val # 用后继值替换当前节点值
	root.right = bst_delete(root.right, successor.val) # 删除后继节点
	
	return root # 返回当前节点，维持树结构

7.3 BST的平衡性问题
平衡BST：树高 h=O(log⁡n)h = O(\log n)h=O(logn)，此时所有操作效率为 O(log⁡n)O(\log n)O(logn)。
失衡风险：若插入序列接近有序（如递增/递减），BST会退化为单链表，树高 h=nh = nh=n，操作效率降至 O(n)O(n)O(n)。
示例：插入序列[1,2,3,4,5]，BST退化为：

	1 
	\ 
	2 
	\ 
	3 
	\ 
	4 
	\ 
	5

解决方案：引入平衡二叉搜索树，通过特定机制（如旋转、颜色约束）强制维持树高为 O(log⁡n)O(\log n)O(logn)，常见类型包括AVL树和红黑树。
7.4 AVL树（严格平衡树）
AVL树是最早的平衡二叉搜索树，通过平衡因子和旋转操作维持严格平衡。
7.4.1 定义与平衡条件
平衡因子（BF）：节点左子树高度 - 右子树高度，即 BF(node)=h(left)−h(right)BF(node) = h(left) - h(right)BF(node)=h(left)−h(right)；
平衡条件：任意节点的平衡因子的绝对值 ≤ 1（即 −1≤BF≤1-1 \leq BF \leq 1−1≤BF≤1）；
树高：含 nnn 个节点的AVL树的树高 h≈1.44log⁡(n+2)−1.328h \approx 1.44\log(n+2) - 1.328h≈1.44log(n+2)−1.328，为 O(log⁡n)O(\log n)O(logn)。
7.4.2 AVL树的节点结构
需额外存储节点高度（用于计算平衡因子）：
python

	class AVLNode(TreeNode):
	def __init__(self, val: int):
	super().__init__(val)
	self.height = 1 # 节点高度（叶节点高度为1，空树高度为0）

7.4.3 旋转操作（平衡修复核心）
当插入/删除导致节点平衡因子 ∣BF∣>1|BF| > 1∣BF∣>1 时，通过旋转调整树结构，恢复平衡。旋转分为四种类型：
（1）LL旋转（左左型失衡）
场景：节点的左子树的左子树导致失衡（BF(node)=2BF(node) = 2BF(node)=2，BF(left)=1BF(left) = 1BF(left)=1）。
操作：将左子树作为新根，原根作为新根的右子树，新根的原右子树作为原根的左子树。
代码实现：
python

	def avl_ll_rotate(node: AVLNode) -> AVLNode:
	left_child = node.left # 左子树（新根）
	node.left = left_child.right # 原根左子树 = 新根右子树
	left_child.right = node # 新根右子树 = 原根
	
	# 更新高度（先更新原根，再更新新根）
	node.height = 1 + max(
	node.left.height if node.left else 0,
	node.right.height if node.right else 0
	)
	left_child.height = 1 + max(
	left_child.left.height if left_child.left else 0,
	node.height
	)
	return left_child # 新根

（2）RR旋转（右右型失衡）
场景：节点的右子树的右子树导致失衡（BF(node)=−2BF(node) = -2BF(node)=−2，BF(right)=−1BF(right) = -1BF(right)=−1）。
操作：与LL旋转对称，将右子树作为新根，原根作为新根的左子树。
代码实现：
python

	def avl_rr_rotate(node: AVLNode) -> AVLNode:
	right_child = node.right # 右子树（新根）
	node.right = right_child.left # 原根右子树 = 新根左子树
	right_child.left = node # 新根左子树 = 原根
	
	# 更新高度
	node.height = 1 + max(
	node.left.height if node.left else 0,
	node.right.height if node.right else 0
	)
	right_child.height = 1 + max(
	node.height,
	right_child.right.height if right_child.right else 0
	)
	return right_child # 新根

（3）LR旋转（左右型失衡）
场景：节点的左子树的右子树导致失衡（BF(node)=2BF(node) = 2BF(node)=2，BF(left)=−1BF(left) = -1BF(left)=−1）。
操作：先对左子树执行RR旋转，再对原节点执行LL旋转。
代码实现：
python

	def avl_lr_rotate(node: AVLNode) -> AVLNode:
	node.left = avl_rr_rotate(node.left) # 左子树RR旋转
	return avl_ll_rotate(node) # 原节点LL旋转

（4）RL旋转（右左型失衡）
场景：节点的右子树的左子树导致失衡（BF(node)=−2BF(node) = -2BF(node)=−2，BF(right)=1BF(right) = 1BF(right)=1）。
操作：先对右子树执行LL旋转，再对原节点执行RR旋转。
代码实现：
python

	def avl_rl_rotate(node: AVLNode) -> AVLNode:
	node.right = avl_ll_rotate(node.right) # 右子树LL旋转
	return avl_rr_rotate(node) # 原节点RR旋转

7.4.4 AVL树的插入操作
步骤：
1.按BST规则插入新节点；
2.回溯更新插入路径上节点的高度；
3.计算平衡因子，若失衡（∣BF∣>1|BF| > 1∣BF∣>1），执行对应旋转（LL/RR/LR/RL）；
4.返回调整后的根节点。
代码实现：
python

	def avl_insert(root: AVLNode, val: int) -> AVLNode:
	# 步骤1：BST插入
	if not root:
	return AVLNode(val)
	if val < root.val:
	root.left = avl_insert(root.left, val)
	else:
	root.right = avl_insert(root.right, val)
	
	# 步骤2：更新当前节点高度
	root.height = 1 + max(
	root.left.height if root.left else 0,
	root.right.height if root.right else 0
	)
	
	# 步骤3：计算平衡因子并旋转
	left_h = root.left.height if root.left else 0
	right_h = root.right.height if root.right else 0
	bf = left_h - right_h
	
	# LL型
	if bf > 1 and val < root.left.val:
	return avl_ll_rotate(root)
	# RR型
	if bf < -1 and val > root.right.val:
	return avl_rr_rotate(root)
	# LR型
	if bf > 1 and val > root.left.val:
	return avl_lr_rotate(root)
	# RL型
	if bf < -1 and val < root.right.val:
	return avl_rl_rotate(root)
	
	return root # 未失衡，返回当前节点

7.5 红黑树（近似平衡树）
红黑树通过颜色规则维持“黑平衡”（从根到叶子的所有路径含相同数量的黑节点），平衡性要求低于AVL树，但插入/删除旋转更少，实际应用更广泛。
7.5.1 红黑树的颜色规则
1.每个节点非红即黑；
2.根节点为黑色；
3.叶子节点（NIL节点）为黑色；
4.红色节点的子节点必为黑色（无连续红节点）；
5.从任一节点到其叶子节点的所有路径，黑色节点数量相同（黑高相等）。
7.5.2 红黑树与AVL树的对比

7.6 总结
BST是基础，通过“左小右大”特性支持高效查找/插入/删除，但可能失衡退化为链表；
AVL树通过平衡因子和旋转维持严格平衡，查询效率高，适合查询密集场景；
红黑树通过颜色规则维持近似平衡，插入/删除旋转少，适合动态操作频繁的场景（如映射、集合实现）。
平衡树的核心是将树高控制在 O(log⁡n)O(\log n)O(logn)，确保基本操作的时间复杂度为 O(log⁡n)O(\log n)O(logn)，是高效数据结构设计的基础。

本站原创，转载请注明出处：