【数据结构与算法学习笔记二十五】 平衡二叉树节点跟高度的关系

设f(n)为高度为n的平衡二叉树最少含有的节点数,则:f(1) = 1;f(2) = 2; f(3) = 4;f(4) = 7;……

这些可以通过画图就能得到,但是当n很大时呢?其实有如下结论:f(n) = f(n-1) + f(n-2) +1,(n>=3)。这个递推结论如何得到的呢?

引导问题:求一棵二叉树的节点数目:

假设一颗二叉树T,其左右子树分别为TL,TR。又假设T的节点数目为F(T),TL,TR的节点数目分别为F(TL),F(TR)。则显然:

F(T) = F(TL) + F(TR) + 1。

本文的问题:求高度为n的平衡二叉树最小需要多少节点:

同样假设T为高度为n的平衡二叉树,其需要最少的节点数目为F(n)。又假设TL,TR为T的左右子树,因此TL,TR也为平衡二叉树。假设F1,F2为TL,TR的最少节点数,则,F(n) = F1+F2 +1。那么F1,F2 到底等于多少呢?由于TL,TR与T一样是平衡二叉树,又由于我们知道T的最少节点数是F(n),其中n为T的高度,因此如果我们知道TL,TR的高度就可以知道F1,F2的值了。由平衡二叉树的定义可以知道,TL和TR的高度要么相同,要么相差1,而当TL与TR高度相同(即:都等于n-1)时,我们算出来的F(n)并不能保证最小,因此只有当TL与TR高度相差一(即:一个高度为n-1,一个高度为n-2)时,计算出来的F(n)才能最小。此时我们假设TL比TR高度要高1(即:TL高度为n-1,TR高度为n-2),则有:F1 = F(n-1),F2 = F(n-2)。因此得到结论:F(n) = F(n-1) + F(n -2 ) + 1!
又有结论:深度为h的平衡二叉树的最少节点数N=F(h+2)-1;
F(n)为斐波那契数列,
高度范围:F(h+2)-1<=n

发表评论

电子邮件地址不会被公开。 必填项已用*标注