java - AVL 树最大和最小节点

Question

给定高度 8 时，如何获取 AVL 树中的最大和最小节点数。

我似乎无法从公式 f(8)=f(7)+f(6)+1 中正确地找出它

2*f(6)+f(5)+2
2*[f(5)+f(4)+1]+f(5)+2
3*f(5)+2*f4+4
3*[f(4)+f(3)+1]+2*f(4)+4
5*f(4)+3*f(3)+7
5*[f(3)+f(2)+1]+3*f(3)+7
8*f(3)+5*f(2)+12
8*[f(2)+f(1)+1]+5*f(2)+12
13*f(2)+8*f(1)+20
13*[f(1)+f(0)+1]+8*f(1)+20
21*f(1)+13*f(0)+33=54 whereas answer is 88 is the minimum

Answer 1

对于 AVL 树中的每个节点，我们知道左子树和右子树的深度最多相差 1(这是由定义给出的)。

由此，下一步就非常明显了:我们采用深度为 N 和 N - 1 的最小树，并将它们放置为新根的子树。很明显，AVL 规则仍然成立，并且树包含尽可能少的节点(从归纳基本情况可以明显看出)。

由此，我们得到了递归公式:minnodes(深度) = 1 + minnodes(深度-1) + minnodes(深度 - 2)。这是一个简单的递归方程，Wolfram Alpha 可以为您解决这个问题 ( link )。

第二种情况很简单 - 深度为 h 的完美二叉树包含给定深度的尽可能多的节点，并且简单地满足 AVL 条件。