Java数据结构之AVL树详解

Java数据结构之AVL树详解,第1张

Java数据结构之AVL树详解 本篇文章给大家带来了关于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树详解的详细内容,

欢迎分享,转载请注明来源:内存溢出

原文地址:https://outofmemory.cn/langs/1372008.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-06-16
下一篇2022-06-16

随机推荐

  • 佐治亚理工学院一年学费怎么申请奖学金

      佐治亚理工学院一年学费?怎么申请奖学金?请咨询立思辰留学360美国专家团队。立思辰留学360介绍:佐治亚理工学院(Georgia Institute of Technology),又译乔治亚理工学

    2022-06-28
    300
  • 申请佐治亚理工学院研究生怎么样

      申请佐治亚理工学院研究生怎么样?请咨询立思辰留学360美国专家团队。立思辰留学360介绍:佐治亚理工学院(Georgia Institute of Technology),又译乔治亚理工学院,简称

    2022-06-28
    300
  • 佐治亚理工学院毕业后如何移民

      佐治亚理工学院毕业后如何移民?请咨询立思辰留学360美国专家团队。立思辰留学360介绍:佐治亚理工学院(Georgia Institute of Technology),又译乔治亚理工学院,简称G

    2022-06-28
    300
  • 波士顿学院硕士研究生申请条件怎么样

      波士顿学院硕士研究生申请条件怎么样?请咨询立思辰留学360美国专家团队。立思辰留学360介绍,在基督复临安息日会环境中,大波士顿学院为学生提供了依据,最大限度激发他们的潜能。在课程所有方面,学校强

    2022-06-28
    400
  • 美国门罗社区学院如何

    门罗社区学院成立于1961年,是一所公立学校,位于美国纽约州门罗郡。门罗社区学院拥有许多可以学习的:一个可以继续学习和掌握职业技能的地方,一个为四年制学士打基础,为学术和文化创造机会的中心,是劳动力发

    2022-06-28
    000
  • 美国密西西比学院优势

    密西西比学院优势有哪些密西西比学院,是美国一所历史悠久的基督教大学。密西西比学院包括位于密西西比州克林顿市的主校区,坐落於弗洛伍德市和麦迪逊市的卫星校区,以及坐落於州府杰克逊市的法学院。立思辰留学36

    2022-06-28
    300
  • 2018年加拿大卡尔顿大学怎么样

      立思辰留学360介绍,卡尔顿大学是一所综合类大学,教学与研究并重,在著名的麦克琳杂志(Maclean‘s Magazine)的大学排行榜上,位于综合类大学前10名。卡尔顿大学拥有15个教学研究学院

    2022-06-28
    300
  • 救世主大学学院是野鸡大学吗

    立思辰留学360介绍,救世主大学学院是一所拥有古典基督教信念的私立本科文理大学,拥有超过850的学生和教员,致力于学术卓越,使学生发现自己独特的天赋和一生的职业。基本信息[加拿大] 救世主大学学院Re

  • 卡尔顿大学托福要求详解

    立思辰留学360介绍,卡尔顿大学建于1942年成立,是由安大略湖省的基督教青年会发起建立的,1957年正式成为大学,是加拿大著名的公立大学。卡尔顿大学位于加拿大首都渥太华市中心,校园占地62公顷,风景

    2022-06-28
    400

发表评论

登录后才能评论

评论列表(0条)

    保存