Go语言实现平衡二叉树（AVL树）详解：从零构建高效自平衡搜索树

Go语言实现AVL树的核心结构

首先，我们定义AVL树的节点结构。每个节点包含值、左右子节点指针以及高度信息：

type AVLNode struct {    Value int    Left  *AVLNode    Right *AVLNode    Height int}// 获取节点高度（空节点高度为-1或0，这里设为-1便于计算）func getHeight(node *AVLNode) int {    if node == nil {        return -1    }    return node.Height}// 更新节点高度func updateHeight(node *AVLNode) {    if node != nil {        node.Height = 1 + max(getHeight(node.Left), getHeight(node.Right))    }}func max(a, b int) int {    if a > b {        return a    }    return b}

四种旋转操作

当插入或删除节点导致树失衡时，AVL树通过旋转来恢复平衡。共有四种情况：

• 右旋（LL型）：左子树过高
• 左旋（RR型）：右子树过高
• 先左后右旋（LR型）：左子树的右子树过高
• 先右后左旋（RL型）：右子树的左子树过高

下面是右旋和左旋的Go语言实现：

// 右旋（针对LL型失衡）func rotateRight(y *AVLNode) *AVLNode {    x := y.Left    T2 := x.Right    // 执行旋转    x.Right = y    y.Left = T2    // 更新高度    updateHeight(y)    updateHeight(x)    return x // 新的根节点}// 左旋（针对RR型失衡）func rotateLeft(x *AVLNode) *AVLNode {    y := x.Right    T2 := y.Left    // 执行旋转    y.Left = x    x.Right = T2    // 更新高度    updateHeight(x)    updateHeight(y)    return y // 新的根节点}

插入操作与自动平衡

插入新节点后，我们需要检查并修复可能的失衡。核心逻辑如下：

func insert(node *AVLNode, value int) *AVLNode {    // 1. 执行标准BST插入    if node == nil {        return &AVLNode{Value: value, Height: 0}    }    if value < node.Value {        node.Left = insert(node.Left, value)    } else if value > node.Value {        node.Right = insert(node.Right, value)    } else {        // 不允许重复值        return node    }    // 2. 更新当前节点高度    updateHeight(node)    // 3. 获取平衡因子    balance := getHeight(node.Left) - getHeight(node.Right)    // 4. 如果失衡，进行旋转    // Left Left Case    if balance > 1 && value < node.Left.Value {        return rotateRight(node)    }    // Right Right Case    if balance < -1 && value > node.Right.Value {        return rotateLeft(node)    }    // Left Right Case    if balance > 1 && value > node.Left.Value {        node.Left = rotateLeft(node.Left)        return rotateRight(node)    }    // Right Left Case    if balance < -1 && value < node.Right.Value {        node.Right = rotateRight(node.Right)        return rotateLeft(node)    }    // 返回未改变的节点指针    return node}

完整使用示例

func main() {    var root *AVLNode    // 插入一系列值    values := []int{10, 20, 30, 40, 50, 25}    for _, v := range values {        root = insert(root, v)    }    // 此时root指向一个平衡的AVL树    fmt.Println("AVL树已构建完成！")}

总结

通过本教程，你已经掌握了如何用Go语言实现一个完整的AVL树。这种平衡二叉树结构在需要频繁查找且要求高效性能的场景中非常有用，是高级数据结构学习的重要一环。

建议你动手编写代码并测试各种插入顺序，观察树是如何自动保持平衡的。这不仅能加深理解，还能提升你的算法思维能力。