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)
}

这段代码定义了一个二叉查找树以及相关的旋转操作,并实现了插入节点的功能。在插入过程中,会检查平衡因子并进行相应的旋转以维护树的平衡。

评论已关闭

推荐阅读

DDPG 模型解析,附Pytorch完整代码
2024年11月24日
DQN 模型解析,附Pytorch完整代码
2024年11月24日
AIGC实战——Transformer模型
2024年12月01日
Socket TCP 和 UDP 编程基础(Python)
2024年11月30日
python , tcp , udp
如何使用 ChatGPT 进行学术润色?你需要这些指令
2024年12月01日
AI
最新 Python 调用 OpenAi 详细教程实现问答、图像合成、图像理解、语音合成、语音识别(详细教程)
2024年11月24日
ChatGPT 和 DALL·E 2 配合生成故事绘本
2024年12月01日
omegaconf,一个超强的 Python 库!
2024年11月24日
【视觉AIGC识别】误差特征、人脸伪造检测、其他类型假图检测
2024年12月01日
[超级详细]如何在深度学习训练模型过程中使用 GPU 加速
2024年11月29日
Python 物理引擎pymunk最完整教程
2024年11月27日
MediaPipe 人体姿态与手指关键点检测教程
2024年11月27日
深入了解 Taipy:Python 打造 Web 应用的全面教程
2024年11月26日
基于Transformer的时间序列预测模型
2024年11月25日
Python在金融大数据分析中的AI应用(股价分析、量化交易)实战
2024年11月25日
AIGC Gradio系列学习教程之Components
2024年12月01日
Python3 `asyncio` — 异步 I/O,事件循环和并发工具
2024年11月30日
llama-factory SFT系列教程:大模型在自定义数据集 LoRA 训练与部署
2024年12月01日
Python 多线程和多进程用法
2024年11月24日
Python socket详解,全网最全教程
2024年11月27日