bst非递归插入必须用cur和parent双指针：cur遍历定位空位，parent记录父节点以挂载新节点；须先判root为空，否则parent为nullptr时解引用将崩溃。
非递归插入时如何避免指针误操作
直接用 root 指针一路向下遍历会丢失父节点引用，导致无法挂载新节点。必须用两个指针：一个跟踪当前节点（cur），一个记录父节点（parent）。插入位置确定后，靠 parent 的左/右指针完成挂载。
常见错误是只用一个指针、在循环里修改 cur 后直接赋值 cur = new Node(val) —— 这只会改局部变量，原树结构完全没变。
- 初始化
parent为nullptr，进入循环前先判断root是否为空 - 循环中每次移动前更新
parent = cur，再按值大小决定cur = cur->left或cur = cur->right - 循环退出后，根据
val和parent->val关系，把新节点挂到parent->left或parent->right
搜索优化的关键在于提前终止和缓存友好
非递归搜索本身已比递归少函数调用开销，但真正影响性能的是内存访问模式。BST 若不平衡，会导致大量 cache miss；若平衡（如 AVL 或红黑树），搜索路径长度可控，但标准 BST 不保证平衡。
实际优化点不在算法逻辑，而在数据布局和访问习惯：
- 避免在循环内反复解引用（如
cur->left->val），先存到局部变量再比较 - 搜索失败时尽早返回，不要等
cur == nullptr才结束——可在比较时加条件：若val == cur->val立即返回，否则再判左右 - 若批量搜索同一棵树，考虑将节点按中序展开成数组+二分查找——前提是树静态且查询密集
为什么 insert 和 search 都要检查 root 为空的边界
空树是合法 BST，但容易被忽略。非递归实现中，如果没单独处理 root == nullptr，后续 while 循环直接跳过，parent 保持 nullptr，最后尝试给 parent->left 赋值就会 crash。
这个边界不是“可选优化”，而是必经路径。几乎所有线上 BST 实现崩溃都源于此处未防护。
- 插入前先写
if (!root) { root = new Node(val); return; } - 搜索同理：
if (!root) return false;，否则后续解引用root->val会 segfault - 别指望调用方保证非空——接口契约应由实现侧守卫
迭代器风格遍历对插入/搜索无加速作用
有人试图用类似 STL 的 iterator 包装 BST 来“统一接口”，但这对插入或搜索本身毫无性能提升，反而增加间接层和对象构造开销。BST 的核心操作就是指针跳转，任何封装都会掩盖原始路径。
真需要优化搜索吞吐量，应关注：是否重复构造/析构临时节点？是否在高并发下缺少读写锁？是否该换用 std::set（底层红黑树，已高度优化）？
- 手写 BST 适合学习或特殊场景（如需自定义比较、带子树统计信息）
- 生产环境优先用
std::set或std::map，它们的非递归实现经过多年打磨，内联程度高、分支预测友好 - 若坚持手写，把
Node设为 struct、成员 public、禁用虚函数——减少指令数和内存对齐浪费
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
