上一节我们看到，平衡让 BST 退化为「逐层折半」。顺着这条线索，本节把它说透：为什么平衡的树每次比较都能砍掉一半候选，从而达到 O(log n)？

从根 1 出发，顺右侧箭头依次读 2→3→4→5；所有左箭头都指向空，结构等同于单链表。

上一页已经看到，按有序序列插入，BST 会一路向右退化成一条单链。这条「长得像链表」的树，搜索代价到底是多少？和真正的链表拉出来直接比一比。

上一页说最坏能退化成 O(n)，但那是刻意按顺序插入的结果。真实工程里数据往往是乱的，罕有人专门构造最坏情况。我们真正关心的是「典型情况下到底有多快」。

沿推导链读:随机顺序→根均分→子树减半→递推求解。

三种插入顺序，决定 BST 是高效还是崩溃——它们之间差的不只是速度，而是量级。

前面看到随机插入能让高度趋近期望值，但「运气」不可控。有没有一种树的形态是结构上就保证平衡的？完全二叉树就是其中最经典的一种。

从完全二叉树形态看高度h与节点数n的精确数量关系

完全二叉树是教科书里最理想的形态，但真实插入顺序千变万化，没有两棵树长得一样。我们需要一个数字来量化「这棵树离理想有多远」——左右子树的高度差，就是平衡因子。

高度h对应O(log₂(n+1))复杂度

上页说理想平衡带来 O(log n) 的查找效率。但插入一个新节点后，理想平衡往往就被打破。修复需要多大代价？这就是这页要回答的问题。

上一页我们看到，追求完美平衡的维护代价不小——每次插入都可能引发大规模调整。能不能允许一点点偏差，换来维护上的轻松？

从任一节点算BF，按|BF|大小分流，标出合法边界。

自上而下读：5条规则 → 路径约束 → 高度上界 → 维护代价的因果链。

AVL要求每个节点左右严格平衡，红黑树放宽到路径长度比——两种思路直接决定增删查的取舍。

一组数字按不同顺序插入，会得到形态各异的BST——有的高瘦像竹竿，有的矮胖像蘑菇。它们是否等价？判别只看一件事，和形态毫无关系。

同一组数据的不同树形态

上页我们看到，多棵形态各异的BST可以拥有相同的中序序列——对外部世界'长得一样'。这并非偶然，而是平衡算法能存在的根基——等价性给了我们'不改数据、只调结构'的自由。

前面看到，等价的BST能长成截然不同的形态——有的瘦高像链条，有的矮胖较平衡。从一种形态变成另一种，靠的不是整体重建，而是一种局部变形——这就是「旋转」。

右旋是BST维持平衡的基本动作，把X绕左子L顺时针转一圈，整个过程分四步，缺一不可。

一次左旋让过深的右子树变浅，支点是失衡节点的右孩子

原树经右旋变新树，节点位置改变但中序遍历相同 → 两棵BST等价

沿流程看一棵左斜树如何通过右旋把高度压低一层。

两种自平衡树共用BST等价变换，但触发条件和策略选择截然不同

前面看到，插入顺序不同可能得到形状不同、甚至退化的 BST；但只要中序遍历相同，它们保存的键值序列就相同。接下来把这两件事放在一起看。

下列关于BST旋转的描述，哪一项最准确？

• ✓平衡是查找与维护之间的取舍
• ✓等价BST形状不唯一，中序相同即可
• ✓旋转是连接平衡与等价的桥梁
• ✓严格平衡查找快，宽松平衡维护省
• ✓适度平衡比理想平衡更实用

先合上笔记自己想五分钟，再对照参考答案——好的思考题不在于答得'对'，在于把它想透。