最小化高度的二叉搜索樹

Question

如果我試圖儘量減少二叉搜索樹的高度，這些都是正確的步驟？：

1）從樹上 2產生有序陣列）重建通過添加排序元素融入到樹序

Answer 1

排序的元素後，通過定義中間元件是根節點重建樹，然後遞歸地構建分別從前面和後面的中間，元件的左和右子樹。

Answer 2

添加一個已排序列表，一個簡單的非平衡二叉搜索樹將建立一個二叉搜索樹的理論最壞情況下樹。該值最低的節點是根，每一個節點添加到立即在列表前面的節點的「權利」，與您共創最大深度的樹，在O（n）的搜索時間，而不是O（LGñ ）。你實際上只是在構建一個過於複雜的鏈表。

Answer 3

我認爲，如果你重建樹形結構中，嘗試通過前向inorder插入排序的元素，你所提供的解決方案將是正確的。

1. 重建樹。就像堆。

       (5) 
         (3)   (6) 
        (2)  (4) 
       (1) 
   

   1. 重構樹是這樣的：：

   2. 插入經由序

   例如，如果原來的樹是這樣排序的元素

     () 
       ()   () 
   ()  () () 
   

2. 插入通過inorder排序的元素：1，2，3，4，5，6

     (4) 
       (2)    (6) 
   (1)  (3) (5) 
   

Answer 4

我想你可以訪問樹，並可以在「手動」改變它。我覺得你的平衡問題可以解決這樣的（僞）：

depth(node) 
{ 
    if node is null, return 0; 
    l = depth(left child); 
    r = depth(right child); 
    diff = (r - l); 
    if (diff < -1) rotate right (as often as you need); 
    else if (diff > 1) rotate left (as often as you need); 
    return the new maximum depth of both subtrees +1; 
} 

我必須承認，我不是很確信這一點，但這個想法是，你並不需要臨時數組，因爲遍歷樹和應用正確的旋轉應該做的。