二叉搜索樹（前平衡）

我在二叉搜索樹讀書了，我有一個問題來回答類似Ordered Binary Tree of Strings 二叉搜索樹（前平衡）

是我畫下面正確的之前和之後的平衡樹？所輸入的數據是字符串，在水星，金星，地球，火星，木星，土星，天王星

爲了平衡之前：

 Mercury 
    /  \ 
    Earth  Venus 
    \  /
    Mars Saturn 
    /  \ 
Jupiter  Uranus

平衡後：

  Mercury 
     /  \ 
    Jupiter  Uranus 
/ \  / \ 
Earth Mars Saturn Venus

是它也糾正第一棵樹的深度爲3，第二棵樹的深度爲2，最大尺寸爲7（基於n = 2^(d+1)-1其中d =深度？

來源

2013-12-12 Iain

是的，由於二叉搜索樹排序正確（對於任何給定節點，左子樹中的所有節點都較小並且右子樹中的所有節點都較大），所以平衡看起來是正確的，並且它是完全平衡的。

雖然我不確定是否有一個通用的「平衡樹」算法（至少不是我聽說過的）。然而有像紅黑樹和AVL樹那樣的self-balancing BST's。

是的，深度是正確的，因爲每Wikipedia：

樹的深度（或高度）是路徑的從根到樹中的最深的節點的長度。僅具有一個節點（根）的（有根）樹具有零深度。

是的，最大尺寸計算也是正確的。你可以這樣想：
最大大小是1 + 2 + 4 + 8 + ... + 2^depth（每個項對應於每個級別的最大節點數）。
這就是1111111...111（depth 1）的二進制。
而且，當然，上面加上的是100000...000（depth 0），即2^{depth + 1}。
再減去一個，我們得到2^{(depth + 1)} - 1。

來源

2013-12-12 21:54:32 Dukeling

謝謝@Dukeling。我關聯的另一個SO問題引起了一些混淆，因爲我認爲初始（不平衡）樹的排序方式可能存在錯誤。感謝您回答有關計算最大尺寸和深度的其他問題！ :) – Iain

@Iain是的，鏈接的問題似乎對給定的插入順序具有不正確的樹。我爲這個問題添加了一個註釋。 – Dukeling

二叉搜索樹（前平衡）

回答

相關問題