二叉搜索树插入和查找必须递归维持全局左小右大有序性，AVL树需严格更新高度与平衡因子并正确旋转，Go中必须使用指针接收者和返回新根来避免指针副本问题。
二叉搜索树的插入和查找必须保证左小右大
BST 的核心约束是：对任意节点 node，其左子树所有值 node.Val，右子树所有值 > node.Val。实现时不能只比父节点，要递归维持全局有序性。
常见错误是插入时仅与当前节点比较就终止递归，导致结构退化为链表；或查找时未处理 nil 节点直接解引用，触发 panic。
- 插入逻辑必须递归到叶子位置再新建节点，不能中途“插在中间”
- 查找返回
*Node时，务必先判空：if node == nil { return nil } -
Insert和Search都应接收**Node或返回新根（避免指针副本丢失）
示例插入片段：
func (t *BST) Insert(val int) {
t.root = t.insert(t.root, val)
}
func (t *BST) insert(node *Node, val int) *Node {
if node == nil {
return &Node{Val: val}
}
if val < node.Val {
node.Left = t.insert(node.Left, val)
} else if val > node.Val {
node.Right = t.insert(node.Right, val)
}
return node // 必须返回，保持父指针连通
}AVL 树的平衡因子必须在每次插入/删除后更新并旋转
AVL 不是 BST 加个高度字段就行——关键在 height 字段必须严格定义为：从该节点到最远叶子的边数（或节点数），且每次修改子树后必须立即重算，否则旋转判断失效。
典型坑是：只在插入时更新高度，但忘记在旋转函数内部重新计算被旋转节点及其子节点的高度；或误把平衡因子（leftHeight - rightHeight）当成高度本身。
- 旋转前先更新子节点高度，再算当前节点平衡因子
- 四种旋转（LL、RR、LR、RL）中，
LR和RL必须分两步：先内旋再外旋，顺序错则树仍失衡 - 删除后需向上回溯检查并旋转，不能只处理被删节点的父节点
LL 旋转示例（右旋）：
使用 uber-go/dig 在 Golang 中实现依赖注入——基于反射容器，提供 Provide/Invoke、dig.In/dig.Out 参数与结果对象，支持命名依赖等
func (t *AVL) rotateRight(y *Node) *Node {
x := y.Left
y.Left = x.Right
x.Right = y
y.Height = max(height(y.Left), height(y.Right)) + 1
x.Height = max(height(x.Left), height(x.Right)) + 1
return x
}Go 中实现树结构要特别注意指针和方法接收者类型
Go 没有隐式 this，Insert 方法若用值接收者（func (t BST) Insert(...)），对 t.root 的任何修改都不会反映到原变量上——这是最常被忽略的致命错误。
同时，节点指针的传递也容易出错：比如想修改某子节点的 Left 字段，却传了 *Node 值而非 **Node，导致赋值只作用在副本上。
- 树结构体方法一律用指针接收者：
func (t *BST) Insert(...) - 递归操作节点时，若需修改父节点的
Left或Right字段，函数应返回新子树根，并由父级显式赋值（如上文t.root = t.insert(...)） - 避免在方法里对
node.Left = &Node{...}后，又调用node.Left.SomeMethod()却没检查是否为 nil
AVL 删除比插入更难调试，建议先禁用删除只测插入+查找
AVL 删除涉及三种情况（无子、单子、双子），其中双子情况要找中序后继再递归删除，每一步都可能破坏高度和平衡因子。实际调试中，90% 的崩溃来自删除后的高度未更新或旋转条件判断反了（比如该用 bf 却写成 <code>bf > 1）。
一个实用技巧：在每次旋转前后打印节点值和高度，用固定输入（如插入 1,2,3,4,5）观察是否在第 4 步就触发 LL 旋转。稳定后再放开删除逻辑。
- 删除双子节点时，中序后继一定在右子树最左，但它可能有右子树——这个右子树要挂到后继父节点的左位，不是直接丢弃
- 删除后回溯路径上每个祖先都要重新计算高度和平衡因子，哪怕它原本平衡
- 测试集至少覆盖：插入升序序列（触发持续右偏）、降序序列（触发左偏）、以及带重复值（BST 应忽略，AVL 同理）
真正难的不是写完，而是验证每一层高度和平衡因子数值是否符合预期——手画三五层树，把每个节点的 Height 和 BF 标出来，再对照代码输出逐行比对。
