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

简介: 平衡二叉树的插入和删除(从现在开始摆脱旋转)

一.插入操作

1.找到合适位置插入


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


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



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


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


再来一个例子


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



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



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



二.删除操作


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


1.直接删除叶子节点



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



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



4.左右都有孩子


那么就找左子树中最大的数(63)替换,或者找右子树中最小的数(67)进行替换


下面是替换了63的例子

目录
相关文章
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
11854 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
|
数据库 索引
数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解(题目讲解 简单易懂)
数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解(题目讲解 简单易懂)
980 0
|
存储 机器学习/深度学习 人工智能
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
828 1
|
数据库 C++
【数据结构进阶】红黑树超详解 + 实现(附源码)
本文深入探讨了红黑树的实现原理与特性。红黑树是一种自平衡二叉搜索树,通过节点着色(红/黑)和特定规则,确保树的高度接近平衡,从而实现高效的插入、删除和查找操作。相比AVL树,红黑树允许一定程度的不平衡,减少了旋转调整次数,提升了动态操作性能。文章详细解析了红黑树的性质、插入时的平衡调整(变色与旋转)、查找逻辑以及合法性检查,并提供了完整的C++代码实现。红黑树在操作系统和数据库中广泛应用,其设计兼顾效率与复杂性的平衡。
4234 3
奈氏准则、香农公式、最大码元速率与最大信息速率
奈氏准则、香农公式、最大码元速率与最大信息速率
3428 0
|
算法 Java C语言
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
【数据结构】后缀(逆波兰)表达式的计算以及中缀转后缀的方法
5067 1
|
Java
手撸二叉树——AVL平衡二叉树
本文介绍了AVL平衡二叉树的基本概念和实现方法。首先回顾了二叉查找树在插入节点后的不平衡问题,然后详细讲解了四种旋转操作:左左单旋转、右右单旋转、左右双旋转和右左双旋转,以确保树的平衡。文章还提供了Java代码实现,包括节点插入、删除和平衡调整的具体方法。通过这些操作,AVL树能够保持较低的高度,从而提高查询性能。
545 0
|
存储
外部排序快速入门详解:基本原理,败者树,置换-选择排序,最佳归并树
外部排序用于处理无法一次性加载到内存中的大规模数据排序问题。其基本原理是将外存数据划分为若干已内部排序的小块,利用内存中的缓冲区进行多路归并排序,并逐步合并以生成更大的有序块。通过增加缓冲区数量、优化关键字比较次数(如使用败者树)和调整归并段长度等方法可进一步提高排序效率。最佳归并树的应用则能有效减少磁盘I/O次数,从而优化整个排序过程。
1567 9
|
人工智能 自然语言处理 IDE
通义灵码让AI帮你实现自动化编程
通义灵码是由阿里云与通义实验室联合开发的智能编码辅助工具,具备行级/函数级实时续写、自然语言生成代码、单元测试生成、代码优化、注释生成、代码解释、研发智能问答及异常报错排查等功能。该工具支持200多种编程语言,兼容主流IDE,如Visual Studio Code、Visual Studio和JetBrains IDEs。通义灵码在Gartner发布的AI代码助手魔力象限中表现出色,成为唯一进入挑战者象限的中国科技公司。目前,通义灵码下载量已超过470万,每日辅助生成代码超3000万次,被开发者广泛采用。
1799 1

热门文章

最新文章