平衡二叉搜索树

一、定义

平衡二叉搜索树（Balanced Binary Search Tree，简称 BBST），是在二叉搜索树（BST）的基础上，增加了 [平衡约束] 的特殊二叉树。它的核心目标是避免二叉树退化成链表，让树的高度始终维持在 O （log n）量级，从而保证查找、插入、删除操作的时间复杂度稳定为 O （log n)。

它必须同时满足两个核心属性：

1.二叉搜索树属性：任意节点的左子树所有节点值 < 该节点值 < 右子树所有节点值，中序遍历可得到有序序列。(也就是左<根<右）

2.平衡属性：任意节点的左右子树高度差被限制在合理范围内，不会出现一侧子树极长、另一侧极短的失衡情况。

平衡的核心调整方式：旋转

当插入、删除节点破坏了平衡约束时，树会通过旋转操作在不改变二叉搜索树性质的前提下，调整节点的层级关系，恢复平衡状态。基础旋转分为两类：

• 右旋：将左孩子提升为新的根，原根下沉为右孩子，解决左子树过高的失衡。
• 左旋：将右孩子提升为新的根，原根下沉为左孩子，解决右子树过高的失衡。

对于更复杂的失衡场景（如子树方向不一致），会组合使用两次旋转（左右双旋、右左双旋）。

两种最经典的实现类型

不同的平衡约束标准，衍生出了不同的平衡二叉搜索树实现，最具代表性的是以下两种：

1. AVL 树（严格平衡）

• 平衡规则：任意节点的左右子树高度差（称为「平衡因子」）的绝对值不超过 1。
• 特点：平衡要求最严格，树的高度最低，查找性能最优；但插入、删除时触发旋转的频率更高、开销更大。适合查找频繁、修改较少的场景。

2. 红黑树（近似平衡）

• 平衡规则：通过给节点标记红 / 黑两种颜色，配合 5 条性质约束，保证从根到任意叶子节点的最长路径长度，不超过最短路径的 2 倍。
• 特点：平衡要求相对宽松，插入、删除最多只需要 2 次旋转即可恢复平衡，修改性能远优于 AVL 树；查找性能略逊但仍为 O (log n)。是工业界应用最广的平衡二叉搜索树。

接下来，我们将用leetCode上的一道题目来深入了解一下这个知识点

示例：

给你一个整数数组nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例与约束

• 示例 1输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]说明：选取左中点构造，[0,-10,5,null,-3,null,9]同样为正确答案。

图1：

• 示例 2输入：nums = [1,3]输出：[3,1]说明：[1,null,3]和[3,1]均满足高度平衡要求。

图2：

• 提示
  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums按严格递增顺序排列

二、核心思路：中序序列 + 二分根节点 = 平衡 BST

升序数组本质就是二叉搜索树的中序遍历序列，但仅靠中序遍历无法唯一确定一棵 BST。题目额外要求「高度平衡」，这就给出了确定根节点的唯一最优策略：

要让树平衡，必须让左右子树的节点数量尽可能接近，因此选择数组的中间元素作为根节点。

递归构造流程：

1. 确定根节点：取当前数组区间的中点mid，以nums[mid]作为当前子树的根节点，保证左右子树节点数差不超过 1。
2. 递归构造左子树：使用区间[left, mid-1]的元素构建左子树，作为根节点的左孩子。
3. 递归构造右子树：使用区间[mid+1, right]的元素构建右子树，作为根节点的右孩子。
4. 递归边界：当left > right时，区间为空，返回空节点None。

三、Python代码实现

from typing import List, Optional # LeetCode 标准二叉树节点定义 class TreeNode: def \_\_init\_\_(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> optional[TreeNode]: if left > right: return None #计算左中点 mid = left + (right - left) // 2 #以中点元素作为当前子树的根 root = TreeNode(nums[mid]) #递归构建左右子树 root.left = build(left, mid - 1) root.right = build(mid + 1, right) return root #初始区间，整个数组 return build(0, len(nums) - 1)

代码细节说明

1. 中点选取：代码中mid = left + (right - left) // 2选取左中点；若需选取右中点，可改为mid = left + (right - left + 1) // 2，两种写法均符合题目要求，对应不同的合法输出。
2. 区间设计：使用左右闭区间[left, right]，边界条件清晰，递归终止条件直观。
3. 时间效率：每个节点仅创建一次，无重复计算，是构造平衡 BST 的最优解法。

四、拓展与延伸

1. 迭代法实现：可通过栈模拟递归过程，或用队列按层构造，核心逻辑依然是二分区间划分，适合对递归栈深度有顾虑的场景。
2. 与动态平衡树的对比：本题属于静态构建平衡树，一次性生成平衡结构；而 AVL 树、红黑树属于动态维护平衡树，在插入 / 删除节点时通过旋转维持平衡，二者是平衡树的两种典型实现思路。
3. 同源延伸题目：LeetCode 109. 有序链表转换二叉搜索树，思路完全一致，但链表无法随机访问中点，需配合快慢指针定位中点。

五、总结

本题的核心是利用「有序数组 = BST 中序序列」的性质，通过二分法选取根节点天然保证平衡性，是分治思想在树结构中的经典应用。整体代码简洁、逻辑严谨，是二叉搜索树与平衡树知识点的基础必刷题，掌握后可举一反三解决同类构造类题目。