数据结构与算法——18.avl树

这篇具有很好参考价值的文章主要介绍了数据结构与算法——18.avl树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这篇文章我们来看一下avl树

目录

1.概述

2.AVL树的实现

1.概述

我们前面讲了二叉搜索树,它是有一个key值,然后比父节点key值大的在左边,小的在右边。这样设计是为了便于查找。但是有一种极端的情况,就是所有的结点都在一边,那查找的时间复杂度和在链表的查找时间复杂度就一样了。那有没有解决方法呢?有!

为了解决上述的问题,人们提出了一种新的概念:平衡二叉树

平衡二叉树:它且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树,avl树是平衡二叉树的一种。

这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。

数据结构与算法——18.avl树,数据结构与算法,算法,java,数据结构

如上图所示,就是一个典型的平衡二叉树。

当平衡二叉树添加或删除节点失去平衡的时候,它就进行自选,从而使自己达到平衡。

下面说一下旋转:

左旋:当根节点的右子树的高度减去左子树的高度大于1时,此时二叉树(肯定是二叉搜索树)不平衡了,需要左旋转。具体做法是:以当前根节点的右孩子为新的根节点,当前跟结点及其左子树为新根节点的左孩子,如果新的根节点原本就有左孩子,则其左孩子作为新根节点的新左孩子的右孩子。

数据结构与算法——18.avl树,数据结构与算法,算法,java,数据结构

右旋:当根节点的左子树的高度减去右子树的高度大于1时,此时二叉树(肯定是二叉搜索树)不平衡了,需要左旋转。具体做法是:以当前根节点的左孩子为新的根节点,当前跟结点及其右子树为新根节点的右孩子,如果新的根节点原本就有右孩子,则其右孩子作为新根节点的新右孩子的左孩子。

数据结构与算法——18.avl树,数据结构与算法,算法,java,数据结构

2.AVL树的实现

下面看一下AVL树的实现:

package Tree;
/**AVL树的操作*/
public class L3_AVLTree {

    static class AVLNode{
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1; //高度

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    /**求节点的高度*/
    private int getHeight(AVLNode node){
        return node == null? null:node.height;
    }

    /**更新节点的高度*/
    private void updateHeight(AVLNode node){
        node.height =
                Integer.max(getHeight(node.left),getHeight(node.right))+1;
    }

    /**求一个节点左右子树的高度差*/
    private int bf(AVLNode node){
        return (getHeight(node.left) - getHeight(node.right));
    }

    /**
     *右旋
     * 参数:失衡的结点(即要选择的结点)
     * 返回值:新的根节点
     * */
    private AVLNode rightRotate(AVLNode node){
        AVLNode nodeLeft = node.left;
        AVLNode nodeRightLeft = nodeLeft.right;
        nodeLeft.right = node;//上位
        node.left = nodeRightLeft;//换爹
        updateHeight(node);
        updateHeight(nodeLeft);
        return nodeLeft;
    }

    /**
     * 左旋
     * 参数:失衡的结点(即要选择的结点)
     * 返回值:新的根节点
     * */
    private AVLNode leftRotate(AVLNode node){
        AVLNode nodeRight = node.right;
        AVLNode nodeRightLeft = nodeRight.left;
        nodeRight.left = node;//上位
        node.right = nodeRightLeft;//换爹
        updateHeight(node);
        updateHeight(nodeRight);
        return nodeRight;
    }

    /**
     * 先左旋左子树,再右旋根节点
     * */
    private AVLNode leftRightRotate(AVLNode node){
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    /**
     * 先右旋右子树,再左旋根节点
     * */
    private AVLNode rightLeftRotate(AVLNode node){
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    /**检查结点是否失衡,如果失衡,则重新平衡结点*/
    private AVLNode balance(AVLNode node){
        if (node == null){
            return null;
        }
        int bf = bf(node);
        if (bf > 1 && bf(node.left) >= 0){//LL
            return rightRotate(node);
        }else if (bf > 1 && bf(node.left) < 0){//LR
            return leftRightRotate(node);
        }else if (bf < -1 && bf(node.right) <= 0){//RR
            return leftRotate(node);
        }else if (bf < -1 && bf(node.right) > 0){//RL
            return rightLeftRotate(node);
        }
        return node;
    }

    AVLNode root;
    /**新增结点*/
    public void put(int key,Object value){
        root = doPut(root,key,value);
    }
    private AVLNode doPut(AVLNode node,int key,Object value){
        //找到空位,创建新节点
        if (node == null){
            return new AVLNode(key,value);
        }
        //key已有,更新操作
        if (key == node.key){
            node.value = value;
            return node;
        }
        //继续查找
        if (key < node.key){
            node.left = doPut(node.left,key,value);//向左
        }else {
            node.right = doPut(node.right,key,value);//向右
        }
        updateHeight(node);
        return balance(node);
    }

    public void remove(int key){
        root = doRemove(root,key);
    }
    private AVLNode doRemove(AVLNode node,int key){
        if (node == null){
            return null;
        }
        //没找到key
        if (key < node.key){
            node.left = doRemove(node.left,key);
        }else if (node.key < key){
            node.right = doRemove(node.right,key);
        }else { //找到key:没有孩子;只有一个孩子,两个孩子都有
            if (node.left == null && node.right == null){
                return null;
            }else if (node.left == null){
                node = node.right;
            }else if (node.right == null){
                node = node.left;
            }else {
                AVLNode s = node.right;//后继结点
                while (s.left != null){
                    s = s.left;
                }
                s.right = doRemove(node.right,s.key);
                s.left = node.left;
                node = s;
            }
        }

        //更新 高度
        updateHeight(node);
        //检查失衡
        return balance(node);
    }
}

总结:会者不难,难者不会。知道定义,会画图,会递归,那就能写出来。然后再查缺补漏一下,就没啥问题。文章来源地址https://www.toymoban.com/news/detail-729836.html

到了这里,关于数据结构与算法——18.avl树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [数据结构]-AVL树

    前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、AVL树基本知识 1、概念 2、节点定义 3、插入 二、AVL树的旋转 1、右单旋

    2024年02月04日
    浏览(32)
  • 【数据结构】AVL 树

    前面对 map / multimap / set / multiset 进行了简单的介绍【C++】map set,在其文档介绍中发现,这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的 ,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度

    2024年04月12日
    浏览(31)
  • 【数据结构】AVL树

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 我们知道,二叉搜索树的搜索效率非常高,平均时间复杂度是O(log 2 N),但是当数据原本就有序时,插入二叉树中就会形成单支结构,此时搜索的时间复杂度就是O(N)。 为了避免

    2023年04月18日
    浏览(32)
  • 【数据结构】AVL树/红黑树

    目录 1.AVL树(高度平衡二叉搜索树) 10.1.基本概念 10.2.实现 10.2.1.AVL树节点的定义 10.2.2.AVL树的插入 10.2.3.AVL树的旋转 1.新节点插入较高左子树的左侧---左左:右单旋 2.新节点插入较高右子树的右侧---右右:左单旋 3.新节点插入较高左子树的右侧---左右:先左单旋再右单旋(左

    2024年02月15日
    浏览(46)
  • 【高阶数据结构】AVL树详解

    前面对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现。 这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此

    2024年02月12日
    浏览(40)
  • 数据结构进阶(一):AVL树

    所谓的AVL树也叫做高度平衡的二叉搜索树。 啥是高度平衡的二叉搜索树? 高度平衡的二叉搜索树: 意味着左右子树的高度最大不超过一 。 我们先来回顾一下二叉搜索树的概念: 二叉搜索树又称二叉排序树,它或者是一棵空树 ,或者是具有以下性质的二叉树: 若它的左子树

    2024年02月12日
    浏览(33)
  • C++&&数据结构——AVL树

    根据前面对二叉搜索树的学习我们可以了解到二叉搜索树可以提高查找的效率,但是如果数据本身有序,搜索树将退化成单支树,查找时相当于顺序表查找,效率低下,如下图: 为了解决上面的问题,来自俄罗斯的两位天才数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方

    2024年01月19日
    浏览(65)
  • 数据结构:AVL树讲解(C++)

    普通二叉搜索树: 二叉搜索树 二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序普通的二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法

    2024年02月04日
    浏览(40)
  • 【1++的数据结构】之AVL树

    👍作者主页:进击的1++ 🤩 专栏链接:【1++的数据结构】 在说AVL树之前我们先来说说为什么会出现AVL树。在前面的文章中我们讲过二叉搜索树,虽然查找,插入效率比较高,但其有个缺陷:在某些情况下其可能会成为一颗单支树或其他高度较高的树,这时我们的效率就比较

    2024年02月11日
    浏览(34)
  • 【数据结构】—AVL树(C++实现)

                                                            🎬慕斯主页 : 修仙—别有洞天                                                  💜 本文前置知识:  搜索二叉树                                                       ♈️ 今日夜电波

    2024年02月05日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包