什么是二叉搜索树（BST）？它有哪些重要性质？

简化版

二叉搜索树（BST）是一种有序的二叉树：每个节点的左子树所有值都比它小，右子树所有值都比它大。最重要的性质是——对 BST 做中序遍历（左根右），得到的是一个升序序列。正因为这个有序性，BST 的查找、插入、删除平均都是 O(log n)（前提是树保持平衡）。

详细版

BST 的定义：对树中任意节点 node，

它左子树中所有节点的值都 < node.val；
它右子树中所有节点的值都 > node.val；
左右子树本身也都是 BST（递归定义）。

        8
       / \
      3   10
     / \    \
    1   6    14

核心性质：中序遍历 = 升序。上面这棵树中序遍历得到 1 3 6 8 10 14，严格递增。

BST 的主要操作复杂度（h 为树高）：

操作	平均	最坏
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

平均 O(log n) 是因为每次比较能排除一半子树；最坏 O(n) 是树退化成链的情况。

完整版教学

一、BST 为什么高效：每次砍掉一半

BST 把「有序」的信息编码进了树的结构里。查找一个值时，拿它和当前节点比：小了就只往左子树找、大了只往右子树找，每比较一次就排除掉另一整棵子树。如果树是平衡的，每次排除一半，n 个节点最多比较 log₂n 次，所以平均 O(log n)。这和有序数组上的二分查找是同一个思想，只不过 BST 用树结构支持了高效的动态插入删除。

二、最关键的性质：中序遍历得升序

这是 BST 一切操作的基石。中序遍历顺序是「左 → 根 → 右」，而 BST 保证「左 < 根 < 右」，所以遍历出来天然从小到大。很多 BST 题的本质都是「利用中序有序」：

验证一棵树是不是 BST → 中序遍历看是否严格递增。
找第 K 小的元素 → 中序遍历的第 K 个。
找某节点的中序后继 → 中序序列里它的下一个。
恢复被交换的 BST → 中序序列里找逆序对。

记住「BST 中序有序」，一大批题就有了统一入口。

三、BST vs 普通二叉树 vs 有序数组

普通二叉树：无值的大小约束，查找只能遍历 O(n)。
有序数组：查找 O(log n)（二分），但插入/删除要搬移元素 O(n)。
BST：查找、插入、删除平均都 O(log n)，兼顾了「有序查找快」和「动态增删快」——这正是它存在的意义。

四、致命弱点：会退化

BST 的 O(log n) 有个前提——树是平衡的。如果按有序顺序依次插入（如 1,2,3,4,5），每个新节点都挂到右边，树就退化成一条链：

此时高度变成 n，查找退化到 O(n)，和链表一样慢。为了解决这个问题，才有了自平衡搜索树（AVL、红黑树），它们在插入删除时通过旋转维持平衡，保证高度始终 O(log n)。

五、值通常不允许重复

标准 BST 一般假设节点值互不相同（严格 < 和 >）。如果要处理重复值，需要额外约定（比如相等的放右子树，或在节点里存一个计数）。面试中若没特别说明，默认值唯一。

六、常见误区与追问

考点	正确口径
核心性质	任意节点左子树都小于当前、右子树都大于当前
直接收益	查找时每层只走一边，树高决定效率
重要推论	中序遍历得到严格递增序列

BST valid:
forall node:
  max(node.left) < node.val < min(node.right)
inorder(root) = sorted values

BST 的考点不是“二叉树长得有序”，而是这个有序性必须对整棵子树成立。

误区：只比较当前节点和左右孩子就能验证 BST。 BST 约束来自祖先边界，右子树里的所有节点都必须大于根，左子树里的所有节点都必须小于根。
误区：BST 查找一定是 O(log n)。 只有树高接近 log n 时才是 O(log n)，退化成链表后查找会变成 O(n)。
误区：中序有序是普通二叉树的性质。 中序有序依赖 BST 的左小右大约束，普通二叉树中序遍历没有排序语义。
追问：BST 通常如何处理重复值？ 面试题通常默认不允许重复；工程实现若允许重复，要明确放左、放右或用计数器。
追问：BST 和有序数组相比优势在哪里？ BST 插入删除只需局部调整指针，平均 O(log n)；有序数组查找快，但插入删除需要移动元素。
追问：BST 为什么要引出平衡树？ 普通 BST 的形状受插入顺序影响，平衡树通过旋转把高度维持在 O(log n)。

七、加强记忆

BST = 有序二叉树：左子树全小于根、右子树全大于根（递归成立）。最核心的性质是中序遍历得升序，验证 BST、第 K 小、中序后继、恢复 BST 等题都靠它。查找/插入/删除平均 O(log n)（每次砍掉一半），但按序插入会退化成链、变 O(n)——这正是 AVL / 红黑树等自平衡树要解决的问题。默认节点值唯一。

简化版

详细版