定义
二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序,例如序列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)节点本身变为右孩子的左子树
课程介绍
课程目录
往期学员作品
用户评论
课程介绍
课程目录
往期学员作品
用户评论
你将获得
- AVL树的算法
教学服务
录播课程
讲师介绍
课程详情
温馨提示
- 请勿私下交易请勿在平台外交易。与机构和老师私下交易造成的任何损失及纠纷,腾讯课堂不承担任何责任
- 听课说明
1、电脑:访问腾讯课堂官网 ke.qq.com 查看我的课表或下载win/mac客户端听课
2、手机/平板:下载腾讯课堂APP, 进入学习页面听课