遞歸樹的高度與水平

Question

我讀到樹的高度爲lgn，基數= 2，層數爲lgn + 1。 b/w有什麼不同？他們不包括高度計算中的最頂層還是基本情況？有人可以用一些實際的例子來證明我這個，用更多的語法來代替數學方程嗎？

Answer 1

首先，高度爲平衡的樹是O（lg n）;完全不平衡的樹（例如鏈表）的高度爲O（n）。

節點的高度是它與根的距離（因此樹的高度是從根開始的最大距離節點的任何節點）。從這個定義中，您可以看到根的高度爲0，其子高度爲1，，其子的子女的高度爲2，依此類推。一個級別可以被認爲是具有相同高度的所有節點。

現在考慮樹中的一組等級。有0級的唯一方法是有一棵空樹;只要有單個節點，就會有至少一個級別，即包含高度爲0的根節點的級別。也就是說，在標籤級別和級別之間存在差異，計數級別。 1級是高度爲0的節點;等級2是具有高度1的節點的集合，等級i是具有高度i-1的節點的集合，直到達到由具有高度lg n的節點組成的等級lg n + 1。