7.3 选择题：搜索树不变量

BST看中序，AVL再看高度差，红黑树看颜色和黑高。不要用一种树的条件判断另一种。

手工推演

序列30,20,10插AVL触发LL右旋，20成为根。插BST不旋转则形成左斜。

结构与代码

多选：A BST最坏O(n)；B AVL任意结点平衡因子仅-1,0,1；C 红黑树每条根叶路径长度相等；D 红黑树高度O(logn)。答案A、B、D。

正确性

各结构都保持有序不变量，但平衡约束不同。

错解反馈

看到搜索树就写log；把黑高相等误为路径长度相等；旋转后忘中序必须不变。

迁移训练

BST中序为1,2,3能确定唯一形态吗？答案不能，多种形态有相同中序。