Java源码解析之平衡二叉树
作者：不会编程的派大星 发布时间：2023-11-29 11:16:40
一、平衡二叉树的定义
平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1 。它是一种高度平衡的二叉排序树。意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1 。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor)，那么平衡二叉树上所有结点的平衡因子只可能是-1 、0 和1。
这里举个栗子：
仔细看图中值为18的节点，18的节点的深度为2 。而它的右子树的深度为0，其差值的绝对值大于1了，所以这不是一科平衡二叉树。
二、平衡二叉树的实现原理
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了树的平衡性，如果是，则找出最小不平衡二叉树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各节点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。最小不平衡子树是指距离插入节点最近，且平衡因子的绝对值大于1的节点为根的子树。
下面就让我们通过一个栗子来看看平衡二叉树是怎么构建的呢
首先我们将{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}这样的数组构建成一个二叉排序树，按照二叉排序树的性质，我们将得到下图这样的树：
从图中可以看出，树的高度达到了8，对于查找和插入效率肯定是不够理想的。
接下里我们来看看怎么将这颗二叉排序树一步步构建成平衡二叉树的：
1.按数组顺序将2和3插入，此时没有什么影响，3的平衡因子为1， 2的平衡因子为0，到这里还没什么问题
2.此时我们再来插入1，根据二叉排序树，1只能是2的左子树，然而此时3的平衡因子为2，已经不符合平衡二叉树的规则，这个时候，这棵树就是最小不平衡子树
3.我们将其右旋：三个元素的平衡因子都为0，没什么毛病，我们继续
4.在插入4，根据二叉排序树的规则，4只能放在3的右子树，此时没什么大毛病，我们继续
5.在插入元素5，同理，5只能放在4的右子树，此时元素2的平衡因子为2大于1，
6.将其左旋：没什么大毛病，我们继续
7.在插入元素6，此时为最小不平衡子树
8.再将其左旋，这里具体怎么左旋，就这么想，就是在满足二叉排序树性质的同时，让根节点左边的深度增加，右子树的深度减小，以达到满足二叉平衡树的性质。
接下来的过程大家可以自行去尝试做出来
三、最终结果
可以看到，最后树的高度仅为4，比之前的8对比来说，效率就高了近一半。
平衡二叉树的删除操作与插入类似，这里将不再介绍。大家可以自己思考如何最高效地删除元素，可以分叶结点、仅有一个子结点和有两个子结点三种情况考虑，这里还用到了递归的思想。
来源：https://blog.csdn.net/weixin_45827693/article/details/116543511
0
投稿猜你喜欢
本文实例讲述了Spring与Struts整合之让Spring管理控制器操作。分享给大家供大家参考，具体如下：一 Web配置<?xml- 最近在用SpringMvc写项目的时候，遇到一个问题，就是方法的鉴权问题，这个问题弄了一天了终于解决了，下面看下解决方法项目需求：需要鉴权的
- Okhttp 处理了很多网络疑难杂症，比如从很多常用的连接问题中自动恢复。如果你服务器配置了多个IP地址，当一个IP地址连接失败后Okhtt
- 今天看到已经更新了devblogs，新增的C# 11的!!（用于检查null的语法）经过非常长的讨论，最后取消了。然后我又想起来null检查
- 使用Scroller实现绚丽的ListView左右滑动删除Item效果这里来给大家带来使用Scroller的小例子，同时也能用来帮助初步解除
- 本文实例讲述了Android开发之imageView图片按比例缩放的实现方法。分享给大家供大家参考，具体如下：android:scaleTy
- Spring Boot读取配置文件1）通过注入ApplicationContext 或者 Environment对象来读取配置文件里的配置信
- 方案实施1、 spring和ehcache集成主要获取ehcache作为操作ehcache的对象。spring.xml中注入ehcacheM
- 前言有时候我们想克隆一个List去做别的事，而不影响原来的List,我们直接在list后面加上小点点，发现并没有Clone这样的扩展函数。这
- 我就废话不多说了，大家还是直接看代码吧~ public Sprite LoadSourceSprite(string relat
- 一、相关知识SearchView控件：以下是几个简单网址：SearchView简单用法：Android搜索框（SearchView）的功能和
- 缘由首先说明一下为什么会有这篇文章。前段时间，插件化以及热修复的技术很热，Nuwa热修复的工具NuwaGradle，携程动态加载技术Dyna
- 加密代码using System;using System.IO;using System.Security.Cryptography;pu
- Eureka什么是服务治理为什么需要服务治理？  服务治理是主要针对分布式服务框架的微服务，处理服务调用
- 说到人脸检测，首先要了解Haar特征分类器。Haar特征分类器说白了就是一个个的xml文件，不同的xml里面描述人体各个部位的特征值，比如人
- 在 C# 以二进制形式读取数据时使用的是 BinaryReader 类。BinaryReader 类中提供的构造方法有 3 种，具体的语法形
- 继上一次利用Servlet实现图片上传，这次利用基于MVC的Struts框架，封装了Servlet并简化了JSP页面跳转。JSP上传页面上传
- 项目中有这样一个需求，网页上上传了一个视频，需要获取此视频的时长、大小，把这两个数据返回给前
- itextpdf解决PDF合并的问题本文章是我在项目开发过程中解决了一个关于PDF显示的需求而记录的。需求是这样的，需要将两个PDF进行合并
- C#中保存Session的三种方法及Web.Config设置保存session到sql server;，需要指定Sql Server;服务器
