读书人

毕竟AVL(平衡二叉树)要满足什么条件

发布时间: 2013-12-10 15:05:55 作者: rapoo

到底AVL(平衡二叉树)要满足什么条件?
书上说是 左子树和右子树高度差最多为1
不过我感觉还是对 AVL树的定义有些模糊 为了验证自己是否搞懂了,下面说下我的判断方式,大家看下对不对.
8
/ \
1 9
/ \
0 2
此树的左结点高度为1 右结点高度为0 所以是AVL树
7
/ \
2 8
/ \
1 4
/
3
此树左结点高度为2 右结点高度为0 所以不是AVL树
5
/ \
3 6
为什么当左右结点高度一样时 书上说实际超出了AVL性质的要求?书上说高度差 最多为1 这也就是说如果不越过1就行了啊

[解决办法]
没看明白你要问啥,但是平衡的意思应是递归定义,以你的
8
/ \
1 9
/ \
0 2

应该分析每一个节点,节点0左右子树高度都为0,2的左右都为0,1的都为1,8的左2右1,9左0右0.

所有节点的左右子树高度差都不超过1,平衡了。
[解决办法]

引用:
Quote: 引用:

Quote: 引用:

书上说是 左子树和右子树高度差最多为1
不过我感觉还是对 AVL树的定义有些模糊 为了验证自己是否搞懂了,下面说下我的判断方式,大家看下对不对.
8
/ \
1 9
/ \
0 2
此树的左结点高度为1 右结点高度为0 所以是AVL树
7
/ \
2 8
/ \
1 4
/
3
此树左结点高度为2 右结点高度为0 所以不是AVL树
5
/ \
3 6
为什么当左右结点高度一样时 书上说实际超出了AVL性质的要求?书上说高度差 最多为1 这也就是说如果不越过1就行了啊
其实二楼已经说的很明白了:平衡的意思应是递归定义,

就这最简单的例子
5
/
3
以为5的结点来说,左节点3高度为0 那右结点不存在的话 高度为几呢?

直说这个 ,我就能解惑了!!!


为0

读书人网 >C语言

热点推荐