这两个概念很多人会混在一起其实它们不是一个东西二叉搜索树BST是“规则”平衡二叉树AVL/红黑树是“优化”一、什么是二叉搜索树BST核心只有一句话左子树 根节点 右子树并且这个规则对每一个子树都成立递归定义举个例子5 / \ 3 8 / \ \ 2 4 10特点左边都比 5 小右边都比 5 大每个子树也满足这个规则二、BST 的核心优势中序遍历 有序数组这一点非常重要中序遍历左 → 根 → 右 → 升序查找效率理想情况下类似二分查找时间复杂度O(log n)但有个致命问题如果数据是有序插入1 → 2 → 3 → 4 → 5会变成1 \ 2 \ 3 \ 4 \ 5直接退化成链表复杂度变成O(n)三、什么是平衡二叉树为了解决 BST 退化问题引入平衡二叉树Balanced Binary Tree定义AVL任意节点的左右子树高度差 ≤ 1举例平衡3 / \ 2 4 / 1不平衡1 \ 2 \ 3四、为什么要平衡保证树的高度始终接近 log n这样查找 O(log n)插入 O(log n)删除 O(log n)五、如何保持平衡核心思想旋转Rotation当树不平衡时通过旋转调整结构四种情况LL左左→ 右旋RR右右→ 左旋LR左右→ 先左旋再右旋RL右左→ 先右旋再左旋举个最简单例子LL3 / 2 / 1右旋后2 / \ 1 3六、常见平衡树类型1. AVL 树严格平衡高度差 ≤ 1查询快插入删除调整多2. 红黑树工程常用实际开发最常用比如 C map / set特点不严格平衡调整次数少性能稳定七、BST vs 平衡树总结对比项二叉搜索树平衡二叉树是否有序有有是否平衡不一定一定最坏复杂度O(n)O(log n)实现难度简单较复杂使用场景理论/基础工程/面试八、一句话理解BST 解决“查找有序”问题平衡树解决“查找效率稳定”问题九、你该掌握到什么程度如果你是现在这个阶段大一建议分三步第一步熟练 BST 基本操作插入、删除、查找第二步理解“为什么会退化”第三步掌握“平衡的思想”不用手写 AVL 也行十、面试高频考点你很可能会被问为什么 BST 会退化红黑树和 AVL 区别为什么 map 用红黑树十一、终极总结BST 是基础结构平衡树是工程优化版本例/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { return build(nums, 0, nums.size() - 1); } private: TreeNode* build(vectorint nums, int left, int right) { if (left right) return nullptr; int mid left (right - left) / 2; TreeNode* root new TreeNode(nums[mid]); root-left build(nums, left, mid - 1); root-right build(nums, mid 1, right); return root; } };有序数组转二叉搜索树从“有序”到“平衡”的经典构造这道题非常重要它把两个知识点串起来了有序数组顺序结构 → 二叉搜索树树结构同时还要求是“高度平衡”的你这份代码已经是标准最优解我们把它彻底讲透。一、题目本质给你一个升序数组构造一棵二叉搜索树BST并且是平衡的二、关键矛盾问题在于BST 要求左 根 右平衡要求左右子树高度尽量接近三、核心思路每次选择“中间元素”作为根节点这样可以保证左边一半 → 左子树右边一半 → 右子树天然平衡四、代码在做什么入口函数TreeNode* sortedArrayToBST(vectorint nums) { return build(nums, 0, nums.size() - 1); }把问题转化为在区间[left, right]构建树核心递归TreeNode* build(vectorint nums, int left, int right)五、递归拆解重点1. 终止条件if (left right) return nullptr;区间为空返回空节点2. 选中间节点int mid left (right - left) / 2;防止溢出的写法面试加分点3. 创建根节点TreeNode* root new TreeNode(nums[mid]);4. 构建左右子树root-left build(nums, left, mid - 1); root-right build(nums, mid 1, right);递归划分左右区间六、构造过程示例数组[-10, -3, 0, 5, 9]过程0 / \ -10 5 \ \ -3 9每一步都取中间保证平衡七、为什么一定是平衡的因为每次都均分数组所以左右子树节点数接近高度差 ≤ 1或接近八、时间和空间复杂度时间复杂度O(n)每个节点构建一次空间复杂度O(log n)递归深度九、这一题的本质分治 递归构造树你可以这样理解数组 → 切一半左边 → 左子树右边 → 右子树十、和 BST 的关系关键理解你构造出来的树一定是 BST因为数组有序一定是平衡的因为每次取中点
【数据结构与算法】二叉搜索树 vs 平衡二叉树：一篇彻底搞懂（面试核心）
发布时间：2026/6/22 23:13:10
这两个概念很多人会混在一起其实它们不是一个东西二叉搜索树BST是“规则”平衡二叉树AVL/红黑树是“优化”一、什么是二叉搜索树BST核心只有一句话左子树 根节点 右子树并且这个规则对每一个子树都成立递归定义举个例子5 / \ 3 8 / \ \ 2 4 10特点左边都比 5 小右边都比 5 大每个子树也满足这个规则二、BST 的核心优势中序遍历 有序数组这一点非常重要中序遍历左 → 根 → 右 → 升序查找效率理想情况下类似二分查找时间复杂度O(log n)但有个致命问题如果数据是有序插入1 → 2 → 3 → 4 → 5会变成1 \ 2 \ 3 \ 4 \ 5直接退化成链表复杂度变成O(n)三、什么是平衡二叉树为了解决 BST 退化问题引入平衡二叉树Balanced Binary Tree定义AVL任意节点的左右子树高度差 ≤ 1举例平衡3 / \ 2 4 / 1不平衡1 \ 2 \ 3四、为什么要平衡保证树的高度始终接近 log n这样查找 O(log n)插入 O(log n)删除 O(log n)五、如何保持平衡核心思想旋转Rotation当树不平衡时通过旋转调整结构四种情况LL左左→ 右旋RR右右→ 左旋LR左右→ 先左旋再右旋RL右左→ 先右旋再左旋举个最简单例子LL3 / 2 / 1右旋后2 / \ 1 3六、常见平衡树类型1. AVL 树严格平衡高度差 ≤ 1查询快插入删除调整多2. 红黑树工程常用实际开发最常用比如 C map / set特点不严格平衡调整次数少性能稳定七、BST vs 平衡树总结对比项二叉搜索树平衡二叉树是否有序有有是否平衡不一定一定最坏复杂度O(n)O(log n)实现难度简单较复杂使用场景理论/基础工程/面试八、一句话理解BST 解决“查找有序”问题平衡树解决“查找效率稳定”问题九、你该掌握到什么程度如果你是现在这个阶段大一建议分三步第一步熟练 BST 基本操作插入、删除、查找第二步理解“为什么会退化”第三步掌握“平衡的思想”不用手写 AVL 也行十、面试高频考点你很可能会被问为什么 BST 会退化红黑树和 AVL 区别为什么 map 用红黑树十一、终极总结BST 是基础结构平衡树是工程优化版本例/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { return build(nums, 0, nums.size() - 1); } private: TreeNode* build(vectorint nums, int left, int right) { if (left right) return nullptr; int mid left (right - left) / 2; TreeNode* root new TreeNode(nums[mid]); root-left build(nums, left, mid - 1); root-right build(nums, mid 1, right); return root; } };有序数组转二叉搜索树从“有序”到“平衡”的经典构造这道题非常重要它把两个知识点串起来了有序数组顺序结构 → 二叉搜索树树结构同时还要求是“高度平衡”的你这份代码已经是标准最优解我们把它彻底讲透。一、题目本质给你一个升序数组构造一棵二叉搜索树BST并且是平衡的二、关键矛盾问题在于BST 要求左 根 右平衡要求左右子树高度尽量接近三、核心思路每次选择“中间元素”作为根节点这样可以保证左边一半 → 左子树右边一半 → 右子树天然平衡四、代码在做什么入口函数TreeNode* sortedArrayToBST(vectorint nums) { return build(nums, 0, nums.size() - 1); }把问题转化为在区间[left, right]构建树核心递归TreeNode* build(vectorint nums, int left, int right)五、递归拆解重点1. 终止条件if (left right) return nullptr;区间为空返回空节点2. 选中间节点int mid left (right - left) / 2;防止溢出的写法面试加分点3. 创建根节点TreeNode* root new TreeNode(nums[mid]);4. 构建左右子树root-left build(nums, left, mid - 1); root-right build(nums, mid 1, right);递归划分左右区间六、构造过程示例数组[-10, -3, 0, 5, 9]过程0 / \ -10 5 \ \ -3 9每一步都取中间保证平衡七、为什么一定是平衡的因为每次都均分数组所以左右子树节点数接近高度差 ≤ 1或接近八、时间和空间复杂度时间复杂度O(n)每个节点构建一次空间复杂度O(log n)递归深度九、这一题的本质分治 递归构造树你可以这样理解数组 → 切一半左边 → 左子树右边 → 右子树十、和 BST 的关系关键理解你构造出来的树一定是 BST因为数组有序一定是平衡的因为每次取中点
