在给定多个节点的情况下,在AVL树中查找最小和最大高度？

Question

在给定一定数量的节点的情况下,是否有公式来计算AVL树的最大和最小高度？

例如:
教科书问题:
3个节点,5个节点和7个节点的AVL树的最大/最小高度是多少？
教科书答案:
3个节点的AVL树的最大/最小高度为2/2,5个节点的最大/最小高度为3/3,7个节点的最大/最小高度为4/3

我不知道他们是否通过一些神奇的公式计算出来,或者他们是否为每个给定的高度绘制了AVL树并确定了它.

Answer 1

下面的解决方案适合手工处理并获得直觉,请查看本答案底部的确切公式,了解更大的树木(54个以上的节点).

那么最小高度很容易,只需用节点填充树的每个级别,直到你用完为止.那个高度是最低的.

要找到最大值,请执行与最小值相同的操作,但是然后返回一步(删除最后放置的节点)并查看是否将该节点添加到相反的子树(从它刚才的位置)违反了AVL树属性.如果是这样,您的最大高度就是您的最小高度.否则这个新高度(应该是最小高度+ 1)是你的最大高度.

如果您需要概述AVL树的属性,或者只是对AVL树的一般解释,那么维基百科是一个很好的起点.

例:

我们来看7节点的例子.你填写所有级别并找到一个完全填充的高度为3的树.(1级为1,级别2为2,级别为3级.1 + 2 + 4 = 7个节点.)这意味着3是你的最小值.

现在找到最大值.删除最后一个节点并将其放在左侧子树而不是右侧.右子树仍然具有高度3,但左子树现在具有高度4.然而,这些值相差小于2,因此它仍然是AVL树.因此你的最大高度是4.(最小值+ 1)

下面列出了所有三个示例(请注意,数字对应于放置顺序,而不是值):

公式¹:

如果您的树具有非常大的节点数,则上面显示的技术不成立.在这种情况下,可以使用以下公式来计算精确的最小值/最大值.

给定n个节点²:

最小值: ceil(log ₂(n + 1))

最大值:楼层(1.44*log ₂(n + 2) - .328)

如果你很好奇,max-min> 1时第一次是n = 54.

^{1感谢Jamie S将更大节点数的故障引起我的注意.}

^{2这些公式来自维基百科AVL页面,插入了常量.原始来源是Donald E. Knuth(第2版)的排序和搜索.}

Answer 2

重要的是要注意AVL树的以下定义特征.

AVL树属性

• AVL树的节点遵守BST属性
• AND任何节点的左右子树的高度相差不超过1.

定理:AVL属性足以维持O(log N)的最坏情况树高.

请注意下图.

- T1由T0 + 1节点组成,高度为1.
- T2由T1和T0 + 1节点组成,高度为2.
- T3由左子树的T2和右子树的T1 + 1节点组成,高度为3.
- T4由左子树的T3和右子树的T2 + 1节点组成,高度为4.

如果采用O(log N)的上限,其中N表示AVL树中的节点数,则获得高度.

例)T4包含12个节点.[ceiling] O(log 12)= 4.

看到这里发展的模式??

**最坏的情况是