平衡二叉搜索树

一、定义平衡二叉搜索树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^4nums按严格递增顺序排列二、核心思路中序序列 二分根节点 平衡 BST升序数组本质就是二叉搜索树的中序遍历序列但仅靠中序遍历无法唯一确定一棵 BST。题目额外要求「高度平衡」这就给出了确定根节点的唯一最优策略要让树平衡必须让左右子树的节点数量尽可能接近因此选择数组的中间元素作为根节点。递归构造流程确定根节点取当前数组区间的中点mid以nums[mid]作为当前子树的根节点保证左右子树节点数差不超过 1。递归构造左子树使用区间[left, mid-1]的元素构建左子树作为根节点的左孩子。递归构造右子树使用区间[mid1, right]的元素构建右子树作为根节点的右孩子。递归边界当left right时区间为空返回空节点None。三、Python代码实现from typing import List, Optional # LeetCode 标准二叉树节点定义 class TreeNode: def \_\_init\_\_(self, val0, leftNone, rightNone): 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)代码细节说明中点选取代码中mid left (right - left) // 2选取左中点若需选取右中点可改为mid left (right - left 1) // 2两种写法均符合题目要求对应不同的合法输出。区间设计使用左右闭区间[left, right]边界条件清晰递归终止条件直观。时间效率每个节点仅创建一次无重复计算是构造平衡 BST 的最优解法。四、拓展与延伸迭代法实现可通过栈模拟递归过程或用队列按层构造核心逻辑依然是二分区间划分适合对递归栈深度有顾虑的场景。与动态平衡树的对比本题属于静态构建平衡树一次性生成平衡结构而 AVL 树、红黑树属于动态维护平衡树在插入 / 删除节点时通过旋转维持平衡二者是平衡树的两种典型实现思路。同源延伸题目LeetCode 109. 有序链表转换二叉搜索树思路完全一致但链表无法随机访问中点需配合快慢指针定位中点。五、总结本题的核心是利用「有序数组 BST 中序序列」的性质通过二分法选取根节点天然保证平衡性是分治思想在树结构中的经典应用。整体代码简洁、逻辑严谨是二叉搜索树与平衡树知识点的基础必刷题掌握后可举一反三解决同类构造类题目。