節點數量與高度之間的關係

我正在閱讀算法設計手冊。作者指出，一棵樹的高度是：節點數量與高度之間的關係

h = log n, 
where 
h is height 
n = number of leaf nodes 
log is log to base d, where d is the maximum number of children allowed per node.

然後，他接着說，一個完美的平衡二叉搜索樹的高度，應該是：

h = log n

不知n在第二個語句表示'總數爲葉節點'或'總數節點'。

這引出了一個更大的問題，節點總數與完美平衡二叉搜索樹高度之間是否存在數學關係？

來源

2013-08-07 Quest Monger

當然，n = 2^h其中h, n分別表示樹的高度和其節點的數量。

證明草圖：

完全平衡二進制樹具有

在每個內節點的2的實際支化因子。
等於每個葉節點的根路徑長度。

大約在完全平衡的二叉樹的葉節點：

作爲葉子的數量是節點的數量減去節點的完全平衡二進制樹具有由一個，遞減的高度數葉子數量是所有節點數量的一半（準確地說，是n+1的一半）。

所以h只是變化1，這通常不會在複雜性考慮方面產生任何實際差異。這種說法可以通過記住它與將單個節點樹的高度定義爲0（標準）或1（不尋常，但可能方便地將其與空樹區分開來）相同的變化來說明。

來源

2013-08-07 09:37:19 collapsar

的所有節點所以它是安全的說，此高度節點關係是更漸進的性質比精確的平等關係？ –

@QuestMonger：它的關係是精確的。然而，在應用程序中，您絕對不會有非常平衡的二叉樹，因爲這需要節點數爲2（-1）的冪。確實存在有效的算法來維護平衡二叉樹，因爲所有葉的根路徑長度變化不會超過1.特別是與完美平衡的樹相比，您不會失去效率。所以關係儘可能精確（純數學以外，無論如何你都會抽象出不變的因素）。 – collapsar

瞭解。謝謝。 –

如果您談論所有節點或葉節點，它並不重要：或者被上面和下面的數據乘以一個常數因子。在一個完全平衡的二叉樹中，完整級別上的節點數量是所有級別上的節點數加1。

來源

2013-08-07 09:37:29 Joni

在完整的二叉樹中，樹（h）的節點數（n）和高度在下面有這樣的關係。

N = 2 ^（H + 1）-1

這是樹

來源

2015-05-20 03:46:46

節點數量與高度之間的關係

回答

相關問題