BST类骨架：__init__设self.root=None；节点仅含val,left,right；插入用迭代避免挂接失败；查找返回True/False或节点；删除双子节点时用右子树最小值覆值后递归删。
怎么写一个能跑通的 Python BST 类
直接给骨架：别从空节点开始折腾，__init__ 里默认 root=None，所有操作都通过 self.root 进入。插入、查找、删除三个方法必须共用同一套节点结构——每个节点存 val、left、right，不加额外字段（比如 parent），否则删除时容易指针错乱。
常见错误现象：insert(5); insert(3); insert(7) 后查 search(3) 返回 None，大概率是插入逻辑没把新节点真正挂到父节点上，而是只在局部变量里 new 了 Node 却没赋值给 parent.left 或 parent.right。
- 递归插入必须有返回值，并层层 return 节点引用，否则父层接不住
- 非递归插入更直观：用
current遍历，用parent记前驱，找到空位后直接parent.left = Node(val)或parent.right = Node(val) - 别在
insert里做重复值判断——BST 定义本身不要求去重，是否忽略/报错/覆盖由业务定，但得明确写出来
查找操作为什么总返回 None 而不是 False
search 的语义是“是否存在”，返回 True/False 最直觉；但很多教程返回节点或 None，这是为了后续删除复用查找逻辑。你得自己决定：如果只是判断存在性，就别让调用方再写 if search(x) is not None:，直接 return True 或 False。
使用场景差异明显：
立即学习“Python免费学习笔记（深入）”；
- 单纯判断：用
bool返回值，简洁安全 - 要取值或删节点：返回节点引用，但注意——返回
None时，调用方必须判空，否则node.val报AttributeError: 'NoneType' object has no attribute 'val' - 递归写法里，漏掉某条分支的
return（比如 if-elif 没 else），会导致隐式返回None，查不到就静默失败
删除节点时最常卡在“有两个子节点”的情况
这是 BST 删除唯一需要逻辑转换的地方：不能直接删，得找中序后继（右子树最小值）或中序前驱（左子树最大值）来顶替。选哪个不影响正确性，但选右子树最小值更常见，因为代码统一性好。
关键不是“找”，而是“怎么换”：
- 找到后继节点
successor后，把它的val覆盖当前待删节点的val，然后递归删除successor——它一定最多只有一个子节点（否则就不是最小值） - 别尝试移动整个节点对象，容易断链；只挪值，再删原位置
- 如果后继节点是其父节点的右孩子，删它时要设
parent.right = successor.left；如果是左孩子，则设parent.left = successor.left——这个分支必须写清楚，不能笼统用“替换”带过 - 测试用例一定要覆盖：删根节点、删叶子、删只有左/右孩子、删有两个孩子且后继是叶子/有左孩子的情况
Python 实现 BST 真的适合生产环境吗
不适合。不是写不对，而是没必要。Python 的 dict 和 set 底层是哈希表，平均 O(1)；标准库没有内置 BST，第三方包如 sortedcontainers 是纯 Python + C 扩展，性能远超手写。
手写 BST 的真实用途很窄：
- 算法题训练（LeetCode 上 BST 题要求返回 TreeNode 结构）
- 教学演示中序遍历和树形结构的关系
- 需要严格 O(log n) 最坏查询（哈希表退化成 O(n)）且数据量不大、不频繁变更的配置索引
容易被忽略的一点：Python 的递归默认限制是 1000 层，建一棵 1000 个节点的偏斜树就会触发 RecursionError。真要用，得手动改 sys.setrecursionlimit()，或者全改成迭代——但迭代版插入/删除代码量翻倍，可读性骤降。
