如果给定高度，AVL Trees:Maximimum 和最小节点数？

Question

最小和最大节点数是AVL树高度6?

Answer 1

n(h)为高度h的AVL树的最小节点数，则：

n(0) = 1
n(1) = 2
n(h) = 1 + n(h-1) + n(h-2)

讨论 here.

一个完整的AVL树是一个完整的二叉树，因此最大节点数为2^{k + 1} - 1，如讨论here.