课程分类

课程介绍
课程目录
用户评论
课程介绍
课程目录
用户评论

你将获得

  • AVL树的算法

教学服务

  • icon

    录播课程

讲师介绍

  • 16年java开发经验,10的架构经验,曾就职于当当等大型互联网企业。熟练掌握分布式、高并发、高可用等技术。掌握支付平台、理财业务等业务架构。

  • 发现一个很富有活力,声音很干净,很有激情的老师在课堂上讲SpringMVC内容,然后就深深的吸引了我。

  • 基础老师讲的很好,由简入深,循序渐进,是一条由菜鸟成长为大神的捷近,当然要成为大神除以老师占一部分原因,更多的是自己要勤加练习,认真听老师讲课,

  • 罗老师讲得很好,并且讲的很有激情,对我很有帮助,感谢罗老师罗老师辛苦了。

  • 内心真的很感动。后来,我还报名了老师的VIP课程,现在在VIP的大班级里面,感觉这里的学习氛围更好。

  • 课程详情





    定义

    二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序,例如序列A = {1,2,3,4,5,6},构造二叉搜索树如图3.1。依据此序列构造的二叉搜索树为右斜树,同时二叉树退化成单链表,搜索效率降低为O(n)。



    在此二叉搜索树中查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度,因此保持树的高度最小,即可保证树的查找效率。同样的序列A,改为图3.2方式存储,查找元素6时只需比较3次,查找效率提升一倍。



    可以看出当节点数目一定,保持树的左右两端保持平衡,树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。



    非平衡二叉树



    平衡二叉树

    平衡因子

    定义:某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子(BF,Balance Factor),平衡二叉树中不存在平衡因子大于1的节点。在一棵平衡二叉树中,节点的平衡因子只能取-1、1或者0。

    对于给定结点数为n的AVL树,最大高度为O(log2n).

    左旋与右旋

    (1) 左旋

    如图3.4.1所示的平衡二叉树



    如在此平衡二叉树插入节点62,树结构变为:



    可以得出40节点的左子树高度为1,右子树高度为3,此时平衡因子为-2,树失去平衡。为保证树的平衡,此时需要对节点40做出旋转,因为右子树高度高于左子树,对节点进行左旋操作,流程如下:

    (1)节点的右孩子替代此节点位置

    (2)右孩子的左子树变为该节点的右子树

    (3)节点本身变为右孩子的左子树

    温馨提示
    • 请勿私下交易
      请勿在平台外交易。与机构和老师私下交易造成的任何损失及纠纷,腾讯课堂不承担任何责任
    • 听课说明

      1、电脑:访问腾讯课堂官网 ke.qq.com 查看我的课表或下载win/mac客户端听课

      2、手机/平板:下载腾讯课堂APP, 进入学习页面听课