站长家园(原代码之家)(www.adminjie.com)网站源码,微信源码,游戏源码,商业源码分享平台。
当前位置:网站首页 技术文章 网络编程 正文

Java数据结构之AVL树详解

时间:2022-06-01 [网络编程]作者:fabuyuan 浏览:5 次

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于平衡二叉树(AVL树)的相关知识,AVL树本质上是带了平衡功能的二叉查找树,下面一起来看一下,希望对大家有帮助。

推荐学习:《java视频教程

AVL树的引入

搜索二叉树有着极高的搜索效率,但是搜索二叉树会出现以下极端情况:

这样的二叉树搜索效率甚至比链表还低。在搜索二叉树基础上出现的平衡二叉树(AVL树)就解决了这样的问题。当平衡二叉树(AVL树)的某个节点左右子树高度差的绝对值大于1时,就会通过旋转操作减小它们的高度差。

基本概念

AVL树本质上还是一棵二叉搜索树,它的特点是:

  1. 本身首先是一棵二叉搜索树
  2. 每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。
  3. 当插入一个节点或者删除一个节点时,导致某一个节点的左右子树高度差的绝对值大于1,这时需要通过左旋右旋的操作使二叉树再次达到平衡状态。

平衡因子(balanceFactor)

  • 一个结点的左子树与右子树的高度之差
  • AVL树中的任意结点的BF只可能是-1,0和1。

基础设计

下面是AVL树需要的简单方法和属性:

public class AVLTree <E extends Comparable<E>>{
    class Node{
        E value;
        Node left;
        Node right;
        int height;
        public Node(){}
        public Node(E value){
            this.value = value;
            height = 1;
            left = null;
            right = null;
        }
        public void display(){
            System.out.print(this.value + " ");
        }
    }
    Node root;
    int size;
    public int size(){
        return size;
    }
    public int getHeight(Node node) {
        if(node == null) return 0;
        return node.height;
    }
    //获取平衡因子(左右子树的高度差,大小为1或者0是平衡的,大小大于1不平衡)
    public int getBalanceFactor(){
        return getBalanceFactor(root);
    }
    public int getBalanceFactor(Node node){
        if(node == null) return 0;
        return getHeight(node.left) - getHeight(node.right);
    }

    //判断一个树是否是一个平衡二叉树
    public boolean isBalance(Node node){
        if(node == null) return true;
        int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right));
        if(balanceFactor > 1) return false;
        return isBalance(node.left) && isBalance(node.right);
    }
    public boolean isBalance(){
        return isBalance(root);
    }

    //中序遍历树
    private  void inPrevOrder(Node root){
        if(root == null) return;
        inPrevOrder(root.left);
        root.display();
        inPrevOrder(root.right);
    }
    public void inPrevOrder(){
        System.out.print("中序遍历:");
        inPrevOrder(root);
    }}

RR(左旋)

往一个树右子树的右子树上插入一个节点,导致二叉树变得不在平衡,如下图,往平衡二叉树中插入5,导致这个树变得不再平衡,此时需要左旋操作,如下:

代码如下:

//左旋,并且返回新的根节点
    public Node leftRotate(Node node){
        System.out.println("leftRotate");
       Node cur = node.right;
       node.right = cur.left;
       cur.left = node;
       //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LL(右旋)

往一个AVL树左子树的左子树上插入一个节点,导致二叉树变得不在平衡,如下图,往平衡二叉树中插入2,导致这个树变得不再平衡,此时需要左旋操作,如下:

代码如下:

 //右旋,并且返回新的根节点
    public Node rightRotate(Node node){
        System.out.println("rightRotate");
        Node cur = node.left;
        node.left = cur.right;
        cur.right = node;
        //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LR(先左旋再右旋)

往AVL树左子树的右子树上插入一个节点,导致该树不再平衡,需要先对左子树进行左旋,再对整棵树右旋,如下图所示,插入节点为5.

RL(先右旋再左旋)

往AVL树右子树的左子树上插入一个节点,导致该树不再平衡,需要先对右子树进行右旋,再对整棵树左旋,如下图所示,插入节点为2.

添加节点

//添加元素
    public  void add(E e){
        root = add(root,e);
    }
    public Node add(Node node, E value) {
        if (node == null) {
            size++;
            return new Node(value);
        }
        if (value.compareTo(node.value) > 0) {
            node.right = add(node.right, value);
        } else if (value.compareTo(node.value) < 0) {
            node.left = add(node.left, value);
        }
        //跟新节点高度
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        //获取当前节点的平衡因子
        int balanceFactor = getBalanceFactor(node);
        //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的左子树上,此时需要进行右旋
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上,此时需要进行左旋
        else if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的右子树上,此时需要先对左子树左旋,在整个树右旋
        else if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        //balanceFactor < -1 && getBalanceFactor(node.left) > 0
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上,此时需要先对右子树右旋,再整个树左旋
        else if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

删除节点

 //删除节点
    public E remove(E value){
        root = remove(root,value);
        if(root == null){
            return null;
        }
        return root.value;
    }
    public Node remove(Node node, E value){
        Node retNode = null;
        if(node == null)
            return retNode;
        if(value.compareTo(node.value) > 0){
            node.right = remove(node.right,value);
            retNode = node;
        }
        else if(value.compareTo(node.value) < 0){
            node.left = remove(node.left,value);
            retNode = node;
        }
        //value.compareTo(node.value) = 0
        else{
            //左右节点都为空,或者左节点为空
            if(node.left == null){
                size--;
                retNode = node.right;
            }
            //右节点为空
            else if(node.right == null){
                size--;
                retNode = node.left;
            }
            //左右节点都不为空
            else{
                Node successor = new Node();
                //寻找右子树最小的节点
                Node cur = node.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                successor.value  = cur.value;
                successor.right = remove(node.right,value);
                successor.left = node.left;
                node.left =  node.right = null;
                retNode = successor;
            }
            if(retNode == null)
                return null;
            //维护二叉树平衡
            //跟新height
            retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right));
        }
        int balanceFactor = getBalanceFactor(retNode);
        //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的左子树上,此时需要进行右旋
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
            return rightRotate(retNode);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上,此时需要进行左旋
        else if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
            return leftRotate(retNode);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的右子树上,此时需要先对左子树左旋,在整个树右旋
        else if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上,此时需要先对右子树右旋,再整个树左旋
        else if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return  retNode;
    }

推荐学习:《java视频教程》

以上就是Java数据结构之AVL树详解的详细内容,更多请关注站长家园其它相关文章!

本文标签:  java

转载请注明来源:Java数据结构之AVL树详解

本文永久链接地址:https://www.adminjie.com/post/13037.html

免责声明:
本站所发布的一切资源仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。

附:
二○○二年一月一日《计算机软件保护条例》第十七条规定:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!

版权声明:
一、本站致力于为软件爱好者提供国内外软件开发技术和软件共享,着力为用户提供优资资源。
二、本站提供的部分源码下载文件为网络共享资源,请于下载后的24小时内删除。如需体验更多乐趣,还请支持正版。
三、我站提供用户下载的所有内容均转自互联网。如有内容侵犯您的版权或其他利益的,若有侵犯你的权益请:提交版权证明文件到邮箱 2225329873#qq.com(#换为@) 站长会进行审查之后,情况属实的会在三个工作日内为您删除。

  • 站长家园(原代码之家)会员升级
  • 最新文章
    • git怎么撤回刚删除的分支

      git怎么撤回刚删除的分支

      git撤回刚删除分支的方法:1、利用“gitremoteprune”命令查看被删除的分支;2、利用“gitreflog”命令找到被删除分支的最后一次提交记...

    • 如何安装并管理多版本node?方法介绍

      如何安装并管理多版本node?方法介绍

      如何安装并管理多版本node?下面本篇文章给大家介绍一下多版本node的安装与切换详细操作,希望对大家有所帮助!安装多版本node的原因:在项目开发过程中,不同...

    • git为什么会产生冲突

      git为什么会产生冲突

      在git中,冲突产生的原因是因为在合并文件时同一个文件的同一个位置都修改了,并且内容不同;也即两个已经提交的分支的相同文件相同位置的不同操作进行了合并,所以产生...

    • git分离头指针是什么

      git分离头指针是什么

      git分离头指针是一种HEAD指针不再指向分支,而是直接指向某个commit的状态;一般情况下HEAD指针指向分支,而分支是指向提交,分离头指针指的是变更没有基...

    • git bash做什么的

      git bash做什么的

      gitbash是用于git版本控制,上传下载项目代码用的;gitbash是Windows下的一个命令行工具,是基于“msysGNU”环境,有git分布式版...

    热门文章