Java详解AVL树的应用

目录
  • 一.什么是AVL树
    • 1.二叉搜索树
    • 2.为什么引入了AVL树
    • 3.什么是AVL树
  • 二.自己构造AVL树
  • 三.AVL树的插入和删除
    • 1.插入
      • 1.1.右单旋
      • 1.2.左单旋
      • 1.3.左右双旋
      • 1.4.右左双旋
    • 2.删除

一.什么是AVL树

在认识AVL树之前我们先认识一下什么是二叉搜索树:

1.二叉搜索树

二叉搜索树又称为二叉排序树,二叉搜索树满足所有的左孩子节点都小于其根节点的值,所有的右孩子节点都大于其根节点的值,二叉搜索树上的每一棵子树都是一棵二叉搜索树,因此二叉搜索树通过中序遍历可以获得一个有序的序列(由小到大);

类似于这样的树就是一棵二叉搜索树;

2.为什么引入了AVL树

二叉搜索树看似很美好,但其却有一些缺陷.对于二叉搜索树而言,是和查找相关的,而不论是查找还是删除,都需要先进行查找,也就是对整棵树来进行遍历,而对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度函数,也就是结点越深,则比较次数越多.最优的情况下是:二叉搜索树为完全二叉树,其平均比较次数为: l o g 2 n log_2{n} log2​n,但是如果二叉搜索树退化成了一棵单分支的树,其平均比较次数为:n/2,就是最差的情况了

这就相当于是一个顺序表的查找了,这样二叉搜索树的优势就完全消失了,因此就引入了AVL树!

3.什么是AVL树

AVL树又称自平衡二叉查找树,是高度平衡的二叉搜索树,就是在二叉搜索树的基础上进行了优化,既当向二叉搜索树中插入新结点后,保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),也就是降低树的高度,这样就可以减少平均搜索长度了,因此AVL树满足它的左右子树都是AVL树,左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1),这就是AVL树的优势所在,因此如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 ,搜索时间复杂度O( l o g 2 n log_2{n} log2​n)!!!

平衡因子 = 右子树的高度 - 左子树的高度

二.自己构造AVL树

这里的构造还是和二叉搜索树的构造差不多的,只不过在这里插入元素的话就需要考虑平衡因子的事情了,因为一定要保证插入元素后此树还是一棵AVL树,就需要进行相关调整,这里就先不过多介绍了,下面再详细介绍,先来构造一棵简单的AVL树:

public class AVLTree {
    static class TreeNode{
        //内部类,表示AVL树的每个节点
        //val值
        public int val;
        //左孩子的引用
        public TreeNode left;
        //右孩子的引用
        public TreeNode right;
        //父亲节点的引用
        public TreeNode parent;
        //平衡因子(每个节点都有)
        public int bf;
        public TreeNode(int val){
            this.val = val;
        }
    }
    //根节点
    public TreeNode root;
    public boolean insert(int val){
    }
}

这样一棵简单的AVL树就构造好了,下面就来写一下AVL树的插入!

三.AVL树的插入和删除

1.插入

首先就是将节点插进来,和二叉搜索树一样,先只看位置在哪,不关注平衡因子

这个为要插入节点:

   TreeNode node = new TreeNode(val);
        if(root == null){
            //没有根节点,要插入的就是根节点
            root = node;
            return true;
        }
        //记录每个节点的父节点
        TreeNode parent = null;
        //要移动的代节点
        TreeNode cur = root;
        //根据val的值和root进行比较来确定应该插入节点的位置
        while (cur != null){
            if(cur.val > val){
                //大于证明此节点应在左子树
                parent = cur;
                cur = cur.left;
            }else if(cur.val < val){
                //大于证明此节点应在右子树
                parent = cur;
                cur = cur.right;
            }else {
                //不能有值一样的节点
                return false;
            }
        }
        //此时cur为空,需要找到对应的位置
        if(parent.val > val){
            parent.left = node;
        }else{
            parent.right = node;
        }

此时节点就已经插进来了,此时就需要看其每个节点的平衡因子了

        //而此时就需要对树进行平衡因子的调整了,保证树是高度平衡的
        //再反着回去写
        node.parent = parent;
        cur = node;
        //当父亲节点一直存在的时候,就表示没有调到根节点就需要继续调整
        while(parent != null){
            if(cur == parent.right){
                //在右边右树高度加一,因此bf+1
                parent.bf++;
            }else{
                //再左边,左树高度加一,因此bf-1
                parent.bf--;
            }
            //在这里就要进行判断了,如果此时的父亲节点如果平衡因子为0了,那么就不需要再往上走了,因为上面的都是平衡的
	        if(parent.bf == 0){
	            return true;
	        }else if(parent.bf == -1 || parent.bf == 1){
	            //此时父亲节点的平衡因子为1、-1
	             //此时表示当前树平衡了,但是不表示整棵树都平衡了,因此还需要继续往上走
	            cur = parent;
	            parent = cur.parent;
	        }else{
	            //此时父亲节点的平衡因子为2、-2
	            if(parent.bf == 2){
                //此时右树高 需要降低右树的高度
	                if(cur.bf == 1){
	                    //左单旋
	                    rotateLeft(parent);
	                }else{
	                    //右左双旋
	                    rotateRL(parent);
	                }
	            }else{
	                //此时左树高,需要降低左树的高度
	                if(cur.bf == 1){
	                    //左右双旋
	                    rotateLR(parent);
	                }else{
	                    //右单旋
	                    rotateRight(parent);
	                }
	            }
	            //调整完就平衡了
	            break;
	        }
        }

这是当前会出现的问题:

先来讨论一下调整平衡因子会出现的一些情况,来分别看一下:

首先是平衡因子调整为0了,那么就不需要再往上走了,因为上面的都是平衡的,当前的父亲节点的平衡因子为0了表示插入的这个元素只影响到了这一棵树,上面是没有影响的,因此是0的话就结束了

因此是0的话就表示当前已经结束了,不需要再往上了,其他变为0 的情况也是一样的这里就不细画了

而如果是1或者-1的话,表示当前树平衡了,但是不表示整棵树平衡了,因此需要再往上走;

而如果是2或者-2的话,会以下四种情况,再来分别看一下:

1.1.右单旋

此时左树高,需要降低左树的高度,也就是右旋(parent.bf = -2,cur.bf = -1):

也就是如下的效果:

也就是这样的调整过程:

下面写一下代码:

private void rotateRight(TreeNode parent){
        //右单旋
        //此时parent的平衡因子为-2,cur的平衡因子为-1
        TreeNode cur = parent.left;
        //记录cur的右节点
        TreeNode curR = cur.right;
        parent.left = curR;
        cur.right = parent;
        //如果cur有右节点需要赋给parent的左节点,但是没有就不需要给了
        if(curR != null){
            curR.parent = parent;
        }
        //然后将cur的右孩子改变为parent
        //需要记录parent的根节点
        TreeNode pParent = parent.parent;
        parent.parent = cur;
        //检查当前是不是根节点,不是根节点需要看是左子树,还是右子树
        if(pParent != null){
            //改变之前的指向
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //此时parent就是root,因为没有根节点
            root = cur;
            root.parent = null;
        }
        //最后记得一定要修改平衡因子
        parent.bf = 0;
        cur.bf = 0;
    }

这样一个“简单”的右单旋就结束了~

1.2.左单旋

这种情况就是最开始的情况了

此时右树高,需要降低右树的高度,也就是左旋(parent.bf = 2,cur.bf = 1):

也就是如下的效果:

也就是这样的调整过程:

代码如下:

private void rotateLeft(TreeNode parent){
        //左单旋
        //此时parent平衡因子为2,cur的平衡因子为1
        //需要记录父亲节点
        TreeNode pParent = parent.parent;
        TreeNode cur = parent.right;
        //记录cur的左节点
        TreeNode curL = cur.left;
        parent.right = curL;
        cur.left = parent;
        //判断左节点是不是空的,如果是空的就不需要管了,不是空的就需要将parent右节点指向它,并且它的父亲节点为parent
        if(curL != null){
            //改变指向
            curL.parent = parent;
        }
        //改变cur的指向
        parent.parent = cur;
        //判断如果pParent不为空,就表示parent不是root,就需要看其是左孩子还是右孩子
        if(pParent != null){
            cur.parent = pParent;
            if(parent == pParent.right){
                pParent.right = cur;
            }else{
                pParent.left = cur;
            }
        }else{
            //是根节点
            root = cur;
            root.parent = null;
        }
        cur.bf = 0;
        parent.bf = 0;
    }

这样一个“简单”的左单旋就结束了~

1.3.左右双旋

此时左树高,需要降低左树的高度,(parent.bf = -2,cur.bf = 1):

而此时仅通过单旋是无法完成的,需要通过两种旋转才能完成:

上面左单旋和右单旋已经介绍过了,这里就不详细介绍了,

先左旋:

此时修改的平衡因子是没有用的

再右旋:

两次旋转之后只需要进行平衡因子的改变就可以了,

通过观察curR的平衡因子,会决定最后其他节点的平衡因子

代码如下:

private void rotateLR(TreeNode parent){
        //左右双旋
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        //此时就需要看curR的平衡因子,再决定最后其他节点的平衡因子
        int bf = curR.bf;
        //先调用左旋再右旋
        rotateLeft(cur);
        rotateRight(parent);
        //这里通过规律可以得到当curR的bf值不同的时候,其需要改变的bf值也是不同的,因此里就需要做出修改
        if(bf == -1){
            //当bf为-1时,其应修改的如下
            curR.bf = 0;
            cur.bf = 0;
            parent.bf = 1;
        }else if(bf == 1){
            //当bf为1时,其应修改的如下
            curR.bf = 0;
            cur.bf = -1;
            parent.bf = 0;
        }
        //另外当bf为0的时候就已经平衡了,就不需要改了,因为在两次旋转的时候就已经将其改为0了
    }

这样一个左右双旋就结束了~

1.4.右左双旋

此时右树高,需要降低右树的高度(parent.bf = 2,cur.bf = -1):

而此时仅通过单旋是无法完成的,需要通过两种旋转才能完成:

先右旋:

再左旋:

通过观察发现其需要改变的平衡因子和curL有关系:

因此

代码如下:

  private void rotateRL(TreeNode parent) {
        //右左双旋
        TreeNode cur = parent.right;
        TreeNode curL = cur.left;
        //此时就需要看curL的平衡因子了,再决定最后其他节点的平衡因子
        int bf = curL.bf;
        rotateRight(cur);
        rotateLeft(parent);
        //这里通过规律可以得到当curR的bf值不同的时候,其需要改变的bf值也是不同的,因此里就需要做出修改
        if(bf == -1){
            //当bf为-1时,其应修改的如下
            parent.bf = 0;
            cur.bf = 0;
            curL.bf = 1;
        }else if(bf == 1){
            //当bf为1时,其应修改的如下
            parent.bf = -1;
            curL.bf = 0;
            cur.bf = 0;
        }
        //另外当bf为0的时候就已经平衡了,就不需要改了,因为在两次旋转的时候就已经将其改为0了
    }

2.删除

删除和上面的插入是差不多的,由于AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不过与删除不同的是,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。

具体步骤:

  • 找到需要删除的节点
  • 按照搜索树的删除规则删除节点
  • 更新平衡因子,如果出现了不平衡,进行旋转。–单旋,双旋

我这里就不进行完整的代码书写了!!

到这儿,AVL树就介绍完毕了,后面会继续介绍红黑树!!!

到此这篇关于Java详解AVL树的应用的文章就介绍到这了,更多相关Java AVL树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java实现二叉查找树的增删查详解

    目录 定义 增加节点 查询节点 删除节点 定义 二叉查找树(ADT)是一个具有对于树种的某个节点X,它的左节点都比X小,它的右节点都比X大的二叉树.如下就是一个符合 要求的二叉查找树: 增加节点 1.定义节点类: class Node{ int val; Node left; Node right; public Node(int val){ this.val=val; } } 2.插入元素 我们采用递归的方法: 1.判断与根节点是否相同,相同无需操作 2.比根元素小往左边查找,左节点不存在的话

  • Java数据结构之线段树的原理与实现

    目录 简介 实现思路 节点定义 构建线段树 求解区间和 更新线段树 简介 线段树是一种二叉搜索树,是用来维护区间信息的数据结构.可以在O(logN)的时间复杂度内实现单点修改.区间修改.区间查询(区间求和,求区间最大值,求区间最小值)等操作.接下来我以实现区间求和为例子来讲解线段树(最大值和最小值与求和实现方式几乎无异),假设存在一个数组[1,4,6,3,9]. 实现思路 从线段树的定义,我们首先需要定义一个树节点,节点包含区间和(23),区间([1-5]),左节点,右节点等.(如果要实现求区间

  • Java数据结构之二叉搜索树详解

    目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数

  • Java超详细讲解排序二叉树

    目录 排序二叉树概念 排序二叉树类的定义 添加节点 中序遍历 查找节点 查找某一节点的父节点 删除节点 排序二叉树概念 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树.是数据结构中的一类. 对于二叉排序树的任何一个非叶子节点, 要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大. 对二叉排序树进行中序遍历,结果就是按从小到大排序的. 排序二叉树类的定义 public class binarySortTree {

  • Java数据结构之线索化二叉树的实现

    目录 1.线索化二叉树的介绍 2.线索化二叉树的基本特点 3.线索化二叉树的应用案例 4.前序线索化二叉树.遍历 5.后序线索化二叉树 1.线索化二叉树的介绍 将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. 问题分析: 1.当我们对上面的二叉树进行中序遍历时,数列为 {8, 3, 10, 1, 6, 14 } 2.但是 6, 8, 10, 14 这几个节点的 左右指针,并没有完全的利用上. 3.如果我们希望充分的利用 各个节点的左右指针, 让各个节点可以指向自己的前后节点

  • Java实现树形结构的示例代码

    目录 前言 数据库表结构 实现思路 具体代码 1.造数据,和数据库表数据一致 2.树型结构实体类 前言 由于业务需要,后端需要返回一个树型结构给前端,包含父子节点的数据已经在数据库中存储好,现在需要做的是如何以树型结构的形式返给给前端. 数据库表结构 实现思路 1.拿到有父子节点的集合数据 2.遍历集合数据,拿到所有的根节点 3.遍历根节点,拿到所有的子节点 4.递归子节点,将递归的子节点接上其父节点,直到子节点为空,递归完成 5.递归好后以集合形式返回,返回前端时以JSON格式转换后返回 具体

  • Java深入分析了解平衡二叉树

    目录 AVL树的引入 基本概念 基础设计 RR(左旋) LL(右旋) LR(先左旋再右旋) RL(先右旋再左旋) 添加节点 删除节点 AVL树的引入 搜索二叉树有着极高的搜索效率,但是搜索二叉树会出现以下极端情况: 这样的二叉树搜索效率甚至比链表还低.在搜索二叉树基础上出现的平衡二叉树(AVL树)就解决了这样的问题.当平衡二叉树(AVL树)的某个节点左右子树高度差的绝对值大于1时,就会通过旋转操作减小它们的高度差. 基本概念 AVL树本质上还是一棵二叉搜索树,它的特点是: 本身首先是一棵二叉搜索

  • Java详解AVL树的应用

    目录 一.什么是AVL树 1.二叉搜索树 2.为什么引入了AVL树 3.什么是AVL树 二.自己构造AVL树 三.AVL树的插入和删除 1.插入 1.1.右单旋 1.2.左单旋 1.3.左右双旋 1.4.右左双旋 2.删除 一.什么是AVL树 在认识AVL树之前我们先认识一下什么是二叉搜索树: 1.二叉搜索树 二叉搜索树又称为二叉排序树,二叉搜索树满足所有的左孩子节点都小于其根节点的值,所有的右孩子节点都大于其根节点的值,二叉搜索树上的每一棵子树都是一棵二叉搜索树,因此二叉搜索树通过中序遍历可以

  • Java 详解Map集合之HashMap和TreeMap

    目录 HashMap 创建HashMap 添加元素 访问元素 删除元素 TreeMap 创建TreeMap 添加元素 访问元素 删除元素 HashMap.TreeMap区别 Map接口储存一组成对的键-值对象,提供key(键)到value(值)的映射,Map中的key不要求有序,不允许重复.value同样不要求有序,但可以重复.最常见的Map实现类是HashMap,他的储存方式是哈希表,优点是查询指定元素效率高. Map接口被HashMap和TreeMap两个类实现. HashMap HashM

  • Java详解如何将excel数据转为树形

    目录 前言 拆分原始数据 1.创建实体类 2.处理数据 手动设置每棵树每个节点的id以及父id 递归封装为树结构 总结 前言 今天收到一个导入的任务,要求将excel数据保存到数据库中,不同于普通的导入,这个导入的数据是一个树形结构,如下图: 通过观察数据中的层级列我们发现表格数据由2棵树组成,分别是第3,4,5,6,7,8,9,10,11和12,13,14,15,16,17,18,它们由0作树的根节点,1为0的子节点,2为相邻1的子节点,由此得出第一颗树的结构为: 拆分原始数据 1.创建实体类

  • java 详解类加载器的双亲委派及打破双亲委派

    java 详解类加载器的双亲委派及打破双亲委派 一般的场景中使用Java默认的类加载器即可,但有时为了达到某种目的又不得不实现自己的类加载器,例如为了达到类库的互相隔离,例如为了达到热部署重加载功能.这时就需要自己定义类加载器,每个类加载器加载各自的类库资源,以此达到资源隔离效果.在对资源的加载上可以沿用双亲委派机制,也可以打破双亲委派机制. 一.沿用双亲委派机制自定义类加载器很简单,只需继承ClassLoader类并重写findClass方法即可.如下例子: ①先定义一个待加载的类Test,它

  • Java 详解单向加密--MD5、SHA和HMAC及简单实现实例

    Java 详解单向加密--MD5.SHA和HMAC及简单实现实例 概要: MD5.SHA.HMAC这三种加密算法,可谓是非可逆加密,就是不可解密的加密方法. MD5 MD5即Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致.MD5是输入不定长度信息,输出固定长度128-bits的算法. MD5算法具有以下特点: 1.压缩性:任意长度的数据,算出的MD5值长度都是固定的. 2.容易计算:从原数据计算出MD5值很容易. 3.抗修改性:对原数据进行任何

  • Java详解线上内存暴涨问题定位和解决方案

    前因: 因为REST规范,定义资源获取接口使用GET请求,参数拼接在url上. 如果按上述定义,当参数过长,超过tomcat默认配置 max-http-header-size :8kb 会报一下错误信息: Request header is too large 可以修改springboot配置,调整请求头大小 server: max-http-header-size: xxx 后果: 如果max-http-header-size设置过大,会导致接口吞吐下降,jvm oom,内存泄漏. 因为tom

  • Java 详解异常的处理机制

    目录 1.异常概述与异常体系结构 1.1异常概述 1.2运行时异常与编译时异常 1.3异常体系结构 2.常见异常 1. ArrayIndexOutOfBoundsException 2.NullPointerException 3.ArithmeticException 4.ClassCastException 3.异常处理机制 3.1异常的抛出与捕获 3.2异常处理机制:try-catch-finally 5.用户自定义异常类 6.异常处理5个关键字 1.异常概述与异常体系结构 1.1异常概述

  • Java 详解循环屏障CyclicBarrier如何实现多线程分段等待执行完成

    前言 工作中是否有这样的场景,多个线程任务,如果所有线程完成到某个阶段,你希望知道所有线程均完成该阶段.当然你使用线程计数可以实现,只是不够优雅. 所以我即:Java 多线程等待优雅的实现方式之Phaser同步屏障 之后再提供一个循环屏障,CyclicBarrier,更优雅的实现工具. Maven依赖 可以依赖,也可以不依赖,只是代码要稍微多一些,最好添加. <dependency> <groupId>org.projectlombok</groupId> <ar

  • Java 详解如何获取网络接口信息

    前言 查看本机的网络接口信息,本文有详细的介绍哦. 代码 不废话,上代码. package com.hy.csdn.tools; import java.net.InetAddress; import java.net.NetworkInterface; import java.net.SocketException; import java.util.Enumeration; /** * @Program: hy-utils @ClassName: StuNetworkInterface @A

  • Java 详解分析链表的中间节点

    目录 1.题目描述 2.解法 3.复杂度 1.题目描述 给定一个头结点为 head 的非空单链表,返回链表的中间结点. 如果有两个中间结点,则返回第二个中间结点. 题目来源:力扣(LeetCode) 2.解法 定义一个快指针 fast 和一个慢指针 slow :fast 走两步, slow 走一步,当 fas t走到尽头时, slow 就刚好在中间节点.因为 fast 比slow 多走一半路程 class Solution { public ListNode middleNode(ListNod

随机推荐