代码之家 › 专栏 › 技术社区 › McLovin

AVL树:叶子的深度不同?

avl-tree binary-tree data-structures

2

McLovin · 技术社区 · 8 年前

测试中的问题:

让 T 做一棵AVL树,并且 x,y 树上有两片叶子吗( x != y )。最大值是多少 depth(x) - depth(y) 是吗?

A. 0
B. 1
C. 2
D. None of the above

正确的(?)答案是D。有人能解释为什么它不是B吗,因为AVL的一个特性是 height(a.left) - height(a.right) <= 1 对于每个节点 a 是吗?

2 回复 | 直到 8 年前

1

2

lrleon 8 年前

用一般的方式解释比用反例要花更多的时间。所以,考虑下面的8阶斐波那契树,它是一个avl树:

以深度为从根到节点的边数,叶0的深度为7,叶52的深度为4。差别是3。对于其他树和较大的AVL树,差异可能更大。

记住,树avl的作用是,每个节点的左子树和右子树的高度差小于或等于1。深度是另一回事。

老实说,这是一个棘手的问题。

以深度为从根到节点的边数,叶0的深度为7,叶52的深度为4。差别是3。对于其他树和较大的AVL树,差异可能更大。

记住,树avl的作用是,每个节点的左子树和右子树的高度差小于或等于1。深度是另一回事。

老实说,这是一个棘手的问题。

2

user8991265 8 年前

AVL树保证“最坏”情况查找时间是O(log(n))。它保证任何两个子树的高度差至多为1。但这并不能保证整棵树的最低和最高节点之间的高度差为1。在一棵大树中,作为一个整体,它可以得到很大的高度差。

理解AVL树的关键是理解它对“子树”的定义。对于任何给定的节点,都有两个子树,有时称为左子树和右子树。这两个子树之间的高度差至多为1。现在假设这两个子树都可以连接到一个节点上,并成为一个更大的树中的一个子树。这个新的子树,称之为节点的左子树,与同一个节点上的右子树的高度差至多为1。但这也意味着这整棵树中任意两片叶子之间的最大高度差为2。这一过程可以重复进行,而AVL树的任何到叶之间都可以有较大的高度差,但仍然保持着它的大O运行时间。