對數字

Question

我想畫從1號平衡二叉搜索樹20

   _______10_______ 
      /    \ 
     ___5___    15 
    /  \   / \ 
     3   8   13  18 
    /\  /\  /\ /\ 
    2 4  7 9  12 14 17 19 
/  /  / / 
    1   6   11  16 

平衡二叉搜索樹是上述樹正確和平衡？

Answer 1

在回答您的正本問題是否需要先計算身高，否則不需要。您必須明白，平衡樹是最高和最短節點之間的高度差爲零或一的平衡樹，實現此目的的最簡單方法是確保始終選擇可能列表的中點，頂層節點在子樹中。

您的示例樹是平衡的，因爲所有葉節點都位於底部或底部到底部，因此任何兩個葉節點之間的高度差最多爲1。

要從數字1到20創建一個平衡樹，您可以使根條目10或11（這些數字的中點爲10.5），以便在子樹中有相同數量的數字。

然後，對每個子樹遞歸地執行該操作。對10下側，5是中點：

  10 
     /\ 
     5 11-thru-19 sub-tree 
     /\ 
1-thru-4 6-thru-9 
sub-tree sub-tree 

就擴大這一點，你會喜歡的東西最終會：

  _______10_______ 
     /    \ 
    ___5___    15 
/  \   /\ 
    2   7   13 17 
/\  /\  / /\ 
1 3  6 8  11 16 18 <- depth of highest leaf node 
    \   \  \   \ 
     4   9  12   19 <- depth of lowest leaf node 
                ^
                | 
               Difference is 1 

中點可以在數發現那裏的數字之上和之下的數量之間的差異是一個或零。對於從1到20的整個數字列表，有9個不到10個，10個大於10個（或者，如果選擇11作爲中間點，則數量爲10和9）。

你們的樣本和我的區別可能是因爲我喜歡在有選擇的地方捨去中點（意味着我的右邊的子樹傾向於「更重」）。因爲你的左邊的子樹較重，你似乎已經四捨五入了。

選擇10作爲初始中點後，左邊的子樹沒有餘地，你必須選擇5，因爲它有四個上下兩個子樹。任何其他中點將導致兩半之間至少有兩個不同（例如，選擇4作爲中點將具有三個和五個尺寸的兩個半部）。這仍然可以爲根據數據給出平衡子樹，但選擇中點「更安全」。