在给定多个节点的情况下，在AVL树中查找最小和最大高度? [英] Finding the minimum and maximum height in a AVL tree, given a number of nodes?

问题描述

在给定一定数量的节点的情况下，是否存在一个公式来计算AVL树的最大和最小高度?

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

我不知道他们是否通过某种魔术公式将其找出来，或者是否为每个给定的高度绘制了AVL树并以此方式确定它.

解决方案

以下解决方案适用于手动工作并获得直觉，请参阅此答案底部的较大树的确切公式(超过54个节点).

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

要找到最大值，请执行与最小值相同的操作，然后返回一个步骤(删除最后一个放置的节点)，然后查看将该节点添加到相反的子树(从原来的位置开始)是否违反了AVL树属性.如果是这样，则您的最大身高就是您的最小身高.否则，此新高度(应为最小高度+1)是您的最大高度.

如果您需要概述AVL树的性质，或者仅是AVL树的一般说明，请 Jamie S 带来了更大的失败节点值得我注意.

^{2 这些公式来自 Wikipedia AVL页面，其中插入了常量.原始来源是Donald E. Knuth(第二版)的排序和搜索.}

Is there a formula to calculate what the maximum and minimum height for an AVL tree, given a certain number of nodes?

For example:
Textbook question:
What is the maximum/minimum height for an AVL tree of 3 nodes, 5 nodes, and 7 nodes?
Textbook answer:
The maximum/minimum height for an AVL tree of 3 nodes is 2/2, for 5 nodes is 3/3, for 7 nodes is 4/3

I don't know if they figured it out by some magic formula, or if they draw out the AVL tree for each of the given heights and determined it that way.

解决方案

The solution below is appropriate for working things out by hand and gaining an intuition, please see the exact formulas at the bottom of this answer for larger trees (54+ nodes).

Well the minimum height is easy, just fill each level of the tree with nodes until you run out. That height is the minimum.

To find the maximum, do the same as for the minimum, but then go back one step (remove the last placed node) and see if adding that node to the opposite sub-tree (from where it just was) violates the AVL tree property. If it does, your max height is just your min height. Otherwise this new height (which should be min height+1) is your max height.

If you need an overview of what the properties of an AVL tree are, or just a general explanation of an AVL tree, Wikipedia is a great place to start.

Example:

Let's take the 7 node example case. You fill in all levels and find a completely filled tree of height 3. (1 at level 1, 2 at level 2, 4 at level 3. 1+2+4=7 nodes.) That means 3 is your minimum.

Now find the max. Remove that last node and place it on the left subtree instead of the right. The right subtree still has height 3, but the left subtree now has height 4. However these values differ by less than 2, so it is still an AVL tree. Therefore your max height is 4. (Which is min+1)

All three examples worked out below (note that the numbers correspond to order of placement, NOT value):

---

Formulas¹:

The technique shown above doesn't hold if you have a tree with a very large number nodes. In this case, one can use the following formulas to calculate the exact min/max.

Given n nodes²:

Minimum: ceil(log₂(n+1))

Maximum: floor(1.44*log₂(n+2)-.328)

If you're curious, the first time max-min>1 is when n=54.

^{1Thanks to Jamie S for bringing this failure at larger node counts to my attention.}

^{2These formulas are from the Wikipedia AVL page, with constants plugged in. The original source is Sorting and searching by Donald E. Knuth (2nd Edition).}

这篇关于在给定多个节点的情况下，在AVL树中查找最小和最大高度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！