大数据培训面试题分析之平衡二叉树的插入删除操作

发布时间:2020年03月16日作者:atguigu浏览次数:968

平衡二叉树(Balanced binary tree)是由阿德尔森维尔斯和兰迪斯(Adelson-Velskii and Landis)1962年首先提出的,所以又称为AVL树。

定义:平衡二叉树或为空树,或为如下性质的二叉排序树:

  1)左右子树深度之差的绝对值不超过1;

  2)左右子树仍然为平衡二叉树.

      平衡因子BF=左子树深度-右子树深度.

平衡二叉树每个结点的平衡因子只能是10-1。若其绝对值超过1,则该二叉排序树就是不平衡的。

插入操作
当我们执行插入一个节点时,很可能会破坏AVL树的平衡特性,所以我们需要调整AVL树的结构,使其重新平衡,而调整的方式称之为旋转。

这里我们针对父节点的位置分为左-左,左-右,右-右,右-左这4类情况分析,而对左-左,右-右情况进行单旋转,也就是一次旋转,对左-右,右-左情况进行双旋转,两次旋转,最终恢复其平衡特性。

删除操作
对于二叉查找树,我们都知道它的删除要分三种情况:
– 删除的节点为叶子节点
– 删除的节点左子树或右子树有一个为空
– 删除的节点有两个子树

AVL本身是带有平衡性质的二叉搜索树,所以它的删除策略是与二叉查找树相似的,只不过删除节点后可能会造成树失去平衡性,所以需要做平衡处理
想要了解跟多关于大数据培训课程内容欢迎关注尚硅谷大数据培训,尚硅谷除了这些技术文章外还有免费的高质量大数据培训课程视频供广大学员下载学习


上一篇:
下一篇:
相关课程

java培训 大数据培训 前端培训

关于尚硅谷
教育理念
名师团队
学员心声
资源下载
视频下载
资料下载
工具下载
加入我们
招聘岗位
岗位介绍
招贤纳师
联系我们
全国统一咨询电话:010-56253825
地址:北京市昌平区宏福科技园2号楼3层(北京校区)

深圳市宝安区西部硅谷大厦B座C区一层(深圳校区)

上海市松江区谷阳北路166号大江商厦3层(上海校区)

武汉市东湖高新开发区东湖网谷(武汉校区)

西安市雁塔区和发智能大厦B座3层(西安校区)

成都市成华区北辰星拱青创园(成都校区)