09 二叉搜索树
按键搜索、插入、删除与中序有序
对应本节 12 道题。点击题目展开答案和理由，保留此前生成的详细解析。
第 01 题 问题 1
BST 的顺序规则只检查直接孩子就足够吗？
参考答案
不够，整个左子树键更小、右子树键更大（本章唯一键约定）。
解析
更深后代也受祖先范围约束。
第 02 题 问题 2
插入 [8,3,10,1,6] 后搜索 6，比较路径是什么？
参考答案
8 → 3 → 6。
解析
6<8 向左，6>3 向右，再命中。
第 03 题 问题 3
该树中序遍历结果？
参考答案
[1,3,6,8,10]。
解析
左、根、右配合 BST 顺序规则得到升序键。
第 04 题 问题 4
教材重复键插入采用什么规则？
参考答案
更新对应记录/值，不再新增同键节点。
解析
唯一键字典语义；允许重复的树需另外定义策略。
第 05 题 问题 5
删除叶节点需要什么连接变化？
参考答案
把父节点对应孩子引用设为 None；若它是根则更新根。
解析
叶没有子树需要接回。
第 06 题 问题 6
删除只有一个孩子的节点，如何保留剩余结构？
参考答案
让其父引用（或根）直接指向唯一孩子。
解析
不能只清空目标节点而丢掉整棵孩子子树。
第 07 题 问题 7
删除有两个孩子的节点，可以选哪条后继记录？
参考答案
右子树的最小记录，即中序后继。
解析
把后继完整键/负载替换到目标，再删除原后继位置。
第 08 题 问题 8
替换目标键时只改 key、不改关联 value，有什么风险？
参考答案
键与记录负载错配。
解析
应移动完整记录或同时更新相关字段。
第 09 题 问题 9
按 [1,2,3,4,5] 顺序插入普通 BST，形状和查找最坏成本如何？
参考答案
可能形成向右的链，最坏 O(n)。
解析
BST 有序关系不自动保证树高为对数。
第 10 题 问题 10
BST 搜索、插入、删除的路径成本一般写成什么？
参考答案
O(h)，h 为树高。
解析
均衡时 h=O(log n)，退化时 h=O(n)。
第 11 题 问题 11
BST 相对哈希表在什么查询上有优势？
参考答案
按序遍历、范围查询、最小最大、前驱后继。
解析
哈希表天然偏向按键定位，迭代不是按键大小排序。
第 12 题 问题 12
如何验证整棵 BST 规则而不只看直接孩子？
参考答案
递归传递允许的上下界，或检查中序严格递增（唯一键约定）。
解析
上下界由所有祖先累积，能发现深层越界。