7.3.1 二叉排序树

BST对每结点满足左子树关键字更小、右子树更大；重复键策略需明确。查找与插入沿一条根叶路径。删除叶直接移除；单孩子用孩子替代；双孩子用中序前驱或后继替换再删。

手工推演

依次插50,30,70,20,40,60。删30可用后继40替换，原40叶再删除；中序仍为20,40,50,60,70。

结构与代码

递归查找根据比较只进一侧。平均性能取决于树高；随机形态约O(log n)，有序插入会退化链O(n)。

正确性

中序遍历BST得到递增序列；删除替换值来自相邻有序位置，所以保持左右范围。

错解反馈

只比较父子不检查整棵子树；删除双孩子直接接两棵树；把BST复杂度无条件写log n。

迁移训练

插入1,2,3,4后树高多少？答案4，说明需平衡树避免退化。