在CLRS，第三版，第155頁，這是因爲在MAX-HEAPIFY，Max-Heapify最糟糕的情況 - 你如何獲得2n/3？
孩子們的子樹各有最多2N/3 -the最壞的情況下 出現底部水平時的大小的樹正好是半滿的。
我明白爲什麼最差的時候樹的底部水平恰好是半滿的。這也是在這個問題上回答worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"
我的問題是如何獲得2n/3？
爲什麼如果最底層是半滿的，那麼子樹的大小是多達2n/3？
如何計算？
由於
在一個樹，其中每個節點具有正好爲0或2個孩子，節點0的孩子的數目大於節點的帶2個孩子的數目多一個{解釋：在高度節點的數量h爲2^h，由幾何級數的求和公式等於（從高度0到h-1的節點之和）+ 1;和所有從高度0到h-1的節點是與正好2個孩子}
ROOT
L R
/\ /\
/ \/ \
----- -----
*****
節點設k爲節點的數量在R.爲L的節點的數量爲k +（K + 1） = 2k + 1。節點總數爲n = 1 +（2k + 1）+ k = 3k + 2（根加L加R）。比例是（2k + 1）/（3k + 2），其範圍在2/3以上。沒有少於2/3的常量，因爲作爲k的極限達到無窮大是2/3。
是的，我明白了，你的意思是L/n = 2/3 – 2012-02-01 16:42:29
哇。那很深。你是怎麼知道的？ – 2012-10-15 07:33:17
對於高度爲h的完整二叉樹，節點數量爲f(h) = 2^h - 1。在上面的情況下，我們有幾乎完整的二叉樹，下半部分已滿。我們可以將其視爲root + left complete tree + right complete tree的集合。如果原樹的高度爲h，則左側高度爲h - 1，右側爲h - 2。所以等式變成
n = 1 + f(h-1) + f(h-2)（1）
我們希望上面解決了f(h-1)表示在n
f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2（2）
條款（1）我們有
以上使用n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2
=> f(h-1) = 2*(n-1/2)/3
因此O（2n/3）
f（h）= 2 ^（h + 1） - 1是不是？ – 2013-09-17 10:52:57
優秀的答案。請更正@fnrf – Ajay 2014-08-29 02:58:43
要添加到swen的答案。當k趨於無窮大時，（2k + 1）/（3k + 2）趨向於2/3，當k趨於無窮大時， k）（2 + k）/ k（3 + 2/k）= Lim_（k-> inf）（2 + 1/k）/（3 + 2/k）
適用限制，你會得到2/3
Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.
一旦明確，勢必2N/3的是輕鬆搞定。
讓我們假設樹中的節點總數爲N.
節點的樹數= 1 +（在左子樹節點的數量）+（在右子樹的節點數）
對於我們的情況下樹有最後一級半滿的，如果我們假設右子樹的高度h，然後左子樹，如果高度（H + 1）：
數在左子樹中的節點= 1 + 2 + 4 + 8 ... 2 ^（h + 1）= 2 ^（h + 2）-1 .....（i）
在右子樹= 1 + 2 + 4 + 8 .... 2 ^（H）2 ^（H + 1）-1 .....（II）
因此節點=數，插入到：
樹中的節點的總數= 1 +（在左子樹的節點的數量）+（在右子樹的節點的數量）
=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)
=> N = 1 + 3*(2^(h+1)) - 2
=> N = 3*(2^(h+1)) -1
=> 2^(h+1) = (N + 1)/3
堵在這個值代入式（i）中，我們得到：
Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)
因此上的節點中的子樹的最大數目的上界具有N樹節點是2N/3。在節點的
提及的f（h），他們比其他人更好，更清楚 – 2015-04-02 20:05:22
數 -
總和從級別0到級別n的所有節點，
從幾何級數求和規則，我們知道
代x = 2時，我們得到
由於2 ^（n + 1）是級別爲n + 1的總節點，可以說0個子節點的節點數量比2個子節點的節點數量多1個。
現在讓我們計算在左子樹，右樹和總節點數..
通過以上推理，左子樹中的葉節點數或 root = k + 1 根樹右子樹中的非葉節點的數量與樹一樣被稱爲恰好是半滿。
總數+ 1 = 2K +
這就是說每個孩子的子樹的大小最多爲2n/3的原因。
這個博客提供了一個簡單的計算：http://bit.ly/138f43F。 – akaHuman 2013-06-26 12:28:39