如何在 Go 中实现二叉搜索树和 AVL 树-Golang-PHP中文网

二叉搜索树插入和查找必须递归维持全局左小右大有序性，avl树需严格更新高度与平衡因子并正确旋转，go中必须使用指针接收者和返回新根来避免指针副本问题。

如何在 go 中实现二叉搜索树和 avl 树

二叉搜索树的插入和查找必须保证左小右大

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.Right = t.insert(node.Right, val)
    }
    return node // 必须返回，保持父指针连通
}

AVL 树的平衡因子必须在每次插入/删除后更新并旋转

AVL 不是 BST 加个高度字段就行——关键在 height 字段必须严格定义为：从该节点到最远叶子的边数（或节点数），且每次修改子树后必须立即重算，否则旋转判断失效。

典型坑是：只在插入时更新高度，但忘记在旋转函数内部重新计算被旋转节点及其子节点的高度；或误把平衡因子（leftHeight - rightHeight）当成高度本身。

旋转前先更新子节点高度，再算当前节点平衡因子
四种旋转（LL、RR、LR、RL）中，LR 和 RL 必须分两步：先内旋再外旋，顺序错则树仍失衡
删除后需向上回溯检查并旋转，不能只处理被删节点的父节点

LL 旋转示例（右旋）：

Golang Uber Dig

使用 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