二叉搜索树的查找效率是多少？为什么会退化？和平衡有什么关系？

简化版

BST 的查找/插入/删除复杂度取决于树高 h——都是 O(h)。树平衡时 h ≈ log n，操作 O(log n)；但如果按有序顺序插入，每个新节点都挂在一侧，树退化成一条链，h = n，操作退化到 O(n)（和链表一样）。为了避免退化，人们发明了自平衡搜索树（AVL、红黑树），靠旋转把高度始终控制在 O(log n)。

详细版

BST 所有核心操作（查找、插入、删除）都沿从根到某节点的一条路径进行，所以复杂度 = 路径长度 = 树高 O(h)。

树的形态	高度 h	操作复杂度
完全平衡	log₂n	O(log n)
一般随机插入	约 1.4·log₂n	O(log n)
完全退化（链）	n	O(n)

退化的原因：BST 的形状由插入顺序决定。若插入序列本身有序（升序或降序），例如依次插入 1,2,3,4,5：

1
 \
  2
   \
    3
     \
      4     ← 退化成右斜链，高度 = n

每个新值都比前面所有值大，全挂到右边，树变成链表，查找变 O(n)。

完整版教学

一、效率的唯一决定因素：树高

BST 之所以快，是因为每次比较能排除一棵子树。但「能排除多少」取决于树长什么样：

平衡时，每次大约排除一半，路径长 log n，所以 O(log n)。
不平衡时，可能每次只排除一个节点，路径长接近 n，退化到 O(n)。

所以谈 BST 效率，本质就是谈树高。控制住树高，就控制住了效率。

二、退化是怎么发生的

普通 BST 没有任何「自我调整」机制，它完全被动地按插入顺序生长。最坏的输入就是有序序列：

升序插入 → 一直往右挂 → 右斜链。
降序插入 → 一直往左挂 → 左斜链。

而现实中「有序插入」并不罕见（比如把已排好序的数据导入），所以退化是一个真实且常见的风险，不能忽视。退化后 BST 相对链表毫无优势，甚至因为每个节点多存指针还更费空间。

三、平衡的意义：把高度锁在 O(log n)

解决退化的思路是：在插入/删除时主动调整结构，强制让树保持平衡，从而把高度始终维持在 O(log n)。这就是自平衡二叉搜索树：

AVL 树：严格平衡，任意节点左右子树高度差 ≤ 1，靠旋转维持。查找最快，但插入删除的旋转较频繁。
红黑树：弱平衡（最长路径不超过最短路径的 2 倍），靠节点染色 + 旋转维持。插入删除调整更少，综合性能好，被 Java 的 TreeMap/TreeSet、C++ map、Linux 内核等广泛采用。

它们都保证操作 O(log n)，代价是维护平衡的额外逻辑。（AVL、红黑树的具体机制属于平衡树板块。）

四、随机插入的期望高度

有趣的是，如果插入顺序是随机的，BST 的期望高度约为 1.39·log₂n，仍是 O(log n) 量级。也就是说「平均而言」普通 BST 表现不错，只有在对抗性/有序输入下才会退化。但工程上不能赌输入随机，所以关键系统都用自平衡树来保证最坏情况。

五、和其他结构的对比

哈希表：查找平均 O(1)，比 BST 快，但不保证有序、不能高效范围查询。
平衡 BST：查找 O(log n)，但天然有序，支持范围查询、找前驱后继、第 K 小等。
普通 BST：平均 O(log n)、最坏 O(n)，实现简单但有退化风险。

需要「有序 + 动态增删 + 范围操作」就用平衡 BST；只要「按键快速存取、不关心顺序」用哈希表。

六、常见误区与追问

考点	正确口径
树形	高度
平衡 BST	约 log2(n)
退化链表	n

n = 1024:
balanced height ≈ 10
degenerated height = 1024
search cost follows height, not node count alone

BST 的效率不是由“二叉搜索树”这个名字保证的，而是由树高保证的。

误区：BST 的查找复杂度固定是 O(log n)。 BST 每层只走一边，但能走多少层取决于高度；高度退化时就是 O(n)。
误区：插入有序数据也会自动平衡。 普通 BST 不会旋转，有序插入会形成单链。
误区：随机插入就等价于严格平衡。 随机插入通常期望较好，但不能提供 AVL、红黑树那样的最坏复杂度保证。
追问：平衡树解决了什么问题？ 通过旋转维持高度上界，把查找、插入、删除的最坏复杂度约束在 O(log n)。
追问：为什么哈希表平均查找更快还要 BST？ BST 支持有序遍历、范围查询、前驱后继；哈希表主要支持等值查找。
追问：如何描述退化原因？ 插入顺序让每个新节点都落在同一侧，树高从 log n 增长到 n。

七、加强记忆

BST 操作都是 O(h)，效率完全取决于树高。平衡时 h≈log n → O(log n)；按有序顺序插入会退化成链，h=n → O(n)（和链表一样）。退化根源是「BST 被动按插入顺序生长、无自我调整」。解决办法是自平衡搜索树（AVL 严格平衡、红黑树弱平衡），靠旋转把高度锁在 O(log n)。随机插入期望高度仍是 O(log n)，但工程不赌输入随机。

简化版

详细版