平衡二叉树
标签: 数据结构
学习人数: 10258


全屏播放
赞赏支持

基本概念
平衡二叉树也叫AVL树,它或者是一颗空树,或者具有以下性质的二叉排序树

它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。

 

结构
如基本概念所述,它具有一个左子树和一个右子树,且对于任意一个子树而言,左子树和右子树高度只差不超过1.

 

平衡二叉树判别
如下有3棵树,分别判断下哪个是平衡二叉树?

图1:

图2:

图3:

图一,很明显就能看出图1中任何子树的高度差都在没有超过1,

图二,节点25的左子树高度是3,而右子树高度是5,高度差已经超过1;对于节点32而言,左子树高度是3,右子树高度是1,高度差已经超出1,所以该树不是平衡二叉树。

图三,对于节点25的左子树高度是3,而右子树高度是5,高度差已经超过1;对于节点28来说,左子树的高度是0,右指数的高度是2,高度差已经超过1;所以两处不平衡,不是平衡二叉树。

从上图这几个案例,应该能明白什么是平衡二叉树了吧。

首先,平衡二叉树是一个...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】在任意一棵非空平衡二又树(AVL树)T1中,删除某结点v之后形成平衡二又树T2,再将w插入T2形成平衡二又树T3。下列关于T1与T3的叙述中,正确的是
I.若v是T1的叶结点,则T1与T3可能不相同
Ⅱ.若v不是T1的叶结点,则T1与T3一定不相同
Ⅲ.若v不是T1的叶结点,则T1与T3一定相同
A.仅I          B. 仅II          C. 仅I、Ⅱ          D. 仅I、Ⅲ

参考答案:A

 

【2015年真题】现有一棵无重复关键字的平衡二叉树(AVL树),对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中,正确的是()。
A.根结点的度一定为 2    B.树中最小元素一定是叶结点
C.最后插入的元素一定是叶结点    D.树中最大元素一定是无左子树

参考答案:D

 

【2012年真题】若平衡二叉树的高度为 6,且所有非叶结点的平衡因子均为 1,则该平衡二叉树的结点总数为()。 
A. 10 
B. 20 
C. 32 
D. 33

参考答案:B
答案解析:考查平衡二叉树的最少结点情况。 
所有非叶结点的平衡因子均为 1,即平衡二叉树满足平衡的最少结点情况,如图 xxx 所示。画图时, 先画出 T1 和 T2;然后新建一个根结点,连接 T2、T1 构成 T3;新建一个根结点,连接 T3、T2 构成 T4;„„ 依此类推,直到画出 T6,可知 T6 的结点数为 20。对于高度为 N 的题述的平衡二叉树,它的左、右子树分别为高度为 N-1 和 N-2 的所有非叶结点的平衡因子均为 1 的平衡二叉树。二叉树的结点总数公式为: 
CN=CN-1+CN-2+1,C2=2,C3=4,递推可得 C6=20。 
【排除法】 对于选项 A,高度为 6、结点数为 10 的树怎么也无法达到平衡。对于选项 C,接点较多时,考虑较极端情形,即第 6 层只有最左叶子的完全二叉树刚好有 32 个结点,虽然满足平衡的条件,但显然再删去部分结点,依然不影响平衡,不是最少结点的情况。同理 D 错误。只可能选 B。

 

【2010年真题】在右图所示的平衡二叉树中,插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中,关键字 37 所在结点的左、右子结点中保存的关键字分别是()

A.13,48 
B.24,48 
C.24,53 
D、24,90 

参考答案:C
答案解析:考查平衡二叉树的插入算法。 
插入 48 以后,该二叉树根结点的平衡因子由-1 变为-2,失去平衡,需进行两次旋转(先右旋后左旋)操作。 


登录后发布评论

暂无评论,来抢沙发