AI 助理
文档备案控制台
开发者社区 云计算 文章 正文

平衡二叉树的插入和删除（从现在开始摆脱旋转）

2024-05-14 835
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 平衡二叉树的插入和删除（从现在开始摆脱旋转）

一.插入操作

1.找到合适位置插入


2.从下到上，沿着插入节点与根节点的连线，找到不平衡的二叉树


以68为根节点的二叉树平衡，左右子树高度差为1



以60为根节点的二叉树不平衡，左右子树高度差为2，不平衡


3.使不平衡的二叉树平衡，最后插入到原来的二叉树中


再来一个例子


同理，从下到上找根节点，判断是否为平衡二叉树



经观察可以发现，整棵树才是非平衡二叉树，所以从根节点，沿着路径画三个节点，将这三个节点调整为平衡二叉树



调整完毕后剩下的节点按照平衡二叉树的规则填补进去即可



二.删除操作


要求：二叉树的高度不增加


1.直接删除叶子节点



2.被删除的节点无左子树，就让右子树的根节点代替



3.被删除节点无右子树，就让左子树的根节点代替



4.左右都有孩子


那么就找左子树中最大的数（63）替换，或者找右子树中最小的数（67）进行替换


下面是替换了63的例子

dulu~dulu
目录
相关文章
路遥叶子
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强，强强在哪里？
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强，强强在哪里？
路遥叶子
11777 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强，强强在哪里？
热烈的马
|
数据库 索引
数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解（题目讲解 简单易懂）
数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解（题目讲解 简单易懂）
热烈的马
958 0
sky_qiyi
数据结构学习记录——平衡二叉树的调整（基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算）
数据结构学习记录——平衡二叉树的调整（基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算）
sky_qiyi
799 1
dulu~dulu
|
存储
计算机组成原理（7）----CPU内部单总线数据通路
计算机组成原理（7）----CPU内部单总线数据通路
dulu~dulu
2308 0
ephemerals__
|
数据库 C++
【数据结构进阶】红黑树超详解 + 实现（附源码）
本文深入探讨了红黑树的实现原理与特性。红黑树是一种自平衡二叉搜索树，通过节点着色（红/黑）和特定规则，确保树的高度接近平衡，从而实现高效的插入、删除和查找操作。相比AVL树，红黑树允许一定程度的不平衡，减少了旋转调整次数，提升了动态操作性能。文章详细解析了红黑树的性质、插入时的平衡调整（变色与旋转）、查找逻辑以及合法性检查，并提供了完整的C++代码实现。红黑树在操作系统和数据库中广泛应用，其设计兼顾效率与复杂性的平衡。
ephemerals__
4093 3
Want595
奈氏准则、香农公式、最大码元速率与最大信息速率
奈氏准则、香农公式、最大码元速率与最大信息速率
Want595
3395 0
2的n次方_
|
存储 算法 Java
【DFS（深度优先搜索）详解】看这一篇就够啦
本文介绍了深度优先搜索（DFS）算法及其应用。DFS从某个顶点出发，深入探索图的每条路径，直到无法前进为止，然后回溯。文章详细解释了DFS的基本思想，并通过示例图展示了其执行过程。此外，文中还探讨了三种枚举方式：指数型枚举、排列型枚举和组合型枚举，并提供了具体的代码实现。最后，文章通过几道练习题帮助读者更好地理解和应用DFS算法。
2的n次方_
11097 19
【DFS（深度优先搜索）详解】看这一篇就够啦
椰椰椰耶
|
算法 Java C语言
【数据结构】后缀（逆波兰）表达式的计算以及中缀转后缀的方法
【数据结构】后缀（逆波兰）表达式的计算以及中缀转后缀的方法
椰椰椰耶
5034 1
2的n次方_
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略，从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成，具有层次关系。二叉树每个节点最多有两个子树，分为左子树和右子树。文中详细描述了二叉树的不同类型，如完全二叉树、满二叉树、平衡二叉树及搜索二叉树，并阐述了二叉树的基本性质与存储方式。此外，还介绍了二叉树的实现方法，包括节点定义、遍历方式（前序、中序、后序、层序遍历），并提供了多个示例代码，帮助理解二叉树的基本操作。
2的n次方_
1557 13
【数据结构】二叉树全攻略，从实现到应用详解

热门文章

最新文章

  • 1
    拍立淘的图像搜索与识别
  • 2
    阿里云大数据利器之-RDS迁移到Maxcompute实现动态分区
  • 3
    Docker 进阶之镜像分层详解
  • 4
    查看 SELinux状态及关闭SELinux
  • 5
    剑池CDK开发工具介绍 | 《平头哥剑池CDK快速上手指南》第一章
  • 6
    WebAssembly 在 MOSN 中的实践 - 基础框架篇
  • 7
    userdel使用说明
  • 8
    自己看系统的“系统还原”
  • 9
    AngularJS 五大特性，加快 Web 应用开发
  • 10
    WPF游戏开发——小鸡快跑
  • 1
    如何搭建企业网盘？一位CTO的完整技术复盘
    27
  • 2
    从0到1搭建企业网盘：架构设计、技术选型与落地实践全解析
    30
  • 3
    【2026实测】Maven下载、安装、配置一篇搞定（附官网安装包）
    27
  • 4
    企业网盘搭建全攻略：从存储到智能检索的完整指南
    19
  • 5
    企业网盘搭建实战：从架构设计到代码实现
    28
  • 6
    学生课堂行为目标检测数据集：3类别、4,200张图像 | 目标检测
    28
  • 7
    阿里云千问模型前缀续写是什么？Partial Mode工作原理介绍
    32
  • 8
    刚刚：Qwen3.8-Max发布：概述、功能、定价、速率限制与上下文、内置工具及API 参考指南
    57
  • 9
    生产级实战：基于Spring Boot + Redis的分布式延迟队列设计与实现
    36
  • 10
    马斯克：Grok 4.6 预计8.7发布，Grok 5 年内发布
    45

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    一条命令迁移，帮你实现 OpenClaw 与 Hermes Agent 记忆互通！