2024年Go最全【数据结构】平衡二叉树的插入、删除_平衡二叉树插入怎么插，Golang内存优化面试题

package main

import (
    "fmt"
)

type TreeNode struct {
    Val         int
    Left, Right *TreeNode
    Height      int
}

func NewNode(v int) *TreeNode {
    return &TreeNode{Val: v, Height: 1}
}

// 获取以节点t为根节点的树的高度
func height(t *TreeNode) int {
    if t == nil {
        return -1
    }
    return t.Height
}

// 更新节点t的高度
func updateHeight(t *TreeNode) {
    t.Height = max(height(t.Left), height(t.Right)) + 1
}

// 比较两个整数的大小
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

// 获取节点t的平衡因子
func getBalanceFactor(t *TreeNode) int {
    return height(t.Left) - height(t.Right)
}

// 左旋转
func rotateLeft(t *TreeNode) *TreeNode {
    r := t.Right
    t.Right = r.Left
    r.Left = t
    updateHeight(t)
    updateHeight(r)
    return r
}

// 右旋转
func rotateRight(t *TreeNode) *TreeNode {
    l := t.Left
    t.Left = l.Right
    l.Right = t
    updateHeight(t)
    updateHeight(l)
    return l
}

// 插入节点
func insert(t *TreeNode, v int) *TreeNode {
    if t == nil {
        return NewNode(v)
    }

    if v < t.Val {
        t.Left = insert(t.Left, v)
    } else {
        t.Right = insert(t.Right, v)
    }

    // 更新平衡因子并进行相应的旋转
    bf := getBalanceFactor(t)
    if bf > 1 && v < t.Left.Val {
        return rotateRight(t)
    }
    if bf < -1 && v > t.Right.Val {
        return rotateLeft(t)
    }
    if bf > 1 && v > t.Left.Val {
        t.Left = rotateLeft(t.Left)
        return rotateRight(t)
    }
    if bf < -1 && v < t.Right.Val {
        t.Right = rotateRight(t.Right)
        return rotateLeft(t)
    }

    updateHeight(t)
    return t
}

func main() {
    var root *TreeNode
    root = insert(root, 5)
    root = insert(root, 3)
    root = insert(root, 7)
    root = insert(root, 1)
    root = insert(root, 4)
    root = insert(root, 6)
    root = insert(root, 8)
    fmt.Println(root)
}