//节点最多的时候是满二叉树，如果认为第一层的高度为0，那么节点数最多应该是2^(h+1) -1

//把h理解成层数才是2^h-1，下面写的最多有错误

高度为 h 的 AVL 树，节点数 N 最多2^h − 1; 最少N(h)=N(h− 1) +N(h− 2) + 1。

最少节点数n 如以斐波那契数列可以用数学归纳法证明:

即:

N(0) = 1 (表示 AVL Tree 高度为0的节点总数)

N(1) = 2(表示 AVL Tree 高度为1的节点总数)

N(2) = 4(表示 AVL Tree 高度为2的节点总数)

N(h)=N(h− 1) +N(h− 2) + 1 (表示 AVL Tree 高度为h的节点总数)

节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。