平衡二叉树-阿里云开发者社区

开发者社区> 云计算> 正文

平衡二叉树

简介:

前面我写了一篇二叉排序树,最后我们提到提高二叉排序树的查找效率是让二叉树的形状均衡,所以就引入了平衡二叉树。

特点:

  • 一种特殊类型的二叉排序树

  • 所有结点的左、右子树深度之差的绝对值≤1

  • 左右子树是平衡二叉树;

平衡因子:该结点左子树和右子数的高度差

任意一个结点的平衡因子只能取:-1、0或1;如果树中任意一个结点的平衡因子的绝对值大于1,则这棵二叉树就失去平衡,不再是AVL树;

对于一棵有n个结点的AVL树,其高度保持在O(log2n)数量级,ASL也保持在O(log2n)量级。

这里写图片描述

如果在一棵AVL树中插入一个新结点,就有可能造成失衡,此时必须重新调整树的结构,使之恢复平衡。我们称调整平衡过程为平衡旋转

调整方法:找到最小不平衡子树,可将重新平衡的范围局限于这棵子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各个结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。

最小不平衡子树:离插入结点最近且平衡因子绝对值超过1的祖先结点,以该结点为根的子树称为最小不平衡子树。

假设最小不平衡子树的根结点为A,则失去平衡后进行调整的规律可归纳为以下四种情况。

  • LL平衡旋转

  • RR平衡旋转

  • LR平衡旋转

  • RL平衡旋转

1)LL平衡旋转:

若在A的左子树的左子树插入结点,使A的平衡因子从1增加到2,需要进行一次向右顺时针旋转(以B为旋转轴)
这里写图片描述

这里写图片描述

2)RR平衡旋转:

若在A的右子树上插入结点,使A的平衡因子从-1
增加至-2,需要进行一次逆时针旋转(以B为旋转轴)

这里写图片描述

这里写图片描述

3)LR平衡旋转:

若在A的左子树的右子树上插入结点,使A的平衡因子从1增加到2,需要先进行逆时针旋转,再顺时针旋转。(以插入的结点

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章