建立AVL樹的二進制搜索樹

我需要建議一個算法，採取BST（二進制搜索樹），T1有2^(n + 1) - 1鍵，並建立一個具有相同鍵的AVL樹。該算法應該在最差和平均時間複雜度方面有效（作爲n的函數）。建立AVL樹的二進制搜索樹

我不知道我該如何解決這個問題。很明顯，具有2^(n + 1) - 1密鑰的BST的最小尺寸是n（並且如果它是完整/平衡的，情況就是這樣），但它對我有什麼幫助？

存在被每次加的T1根部到AVL樹，然後從T1除去它遍歷樹，所述直線前進方法：

由於T1可能會失去平衡的刪除可在最壞的情況下花費爲O（n）
插入到AVL將花費O（log n）的
有2^(n + 1) - 1

因此，總共花費O(n*logn*2^n)，這是可笑的昂貴。

但是我爲什麼要從T1中刪除？我在那裏付了很多錢，沒有什麼好的理由。所以我想，爲什麼不使用樹遍歷了T1，併爲每個節點，我拜訪，把它添加到AVL樹：

有2^(n + 1) - 1節點，以便穿越將耗資O(2^n)（訪問每個節點一次）
將當前節點每次去AVL將耗資O(logn)

因此，在總，這將花費O(logn * 2^n)。這是我能想到的最好的時間複雜性，問題是，它能以更快的速度完成嗎？像在O(2^n)？某種方式，將插入到AVL樹只需要O（1）？

我希望我很清楚，我的問題屬於這裏。

非常感謝你，

諾姆

來源

2016-07-04 Noam

存在着結餘BST和所謂Day Stout Warren Algorithm

線性時間運行的算法基本上它是所有的BST轉換成有序陣列或通過按順序遍歷（O（n））進行鏈表。然後，遞歸地取數組的中間元素，使其成爲根，並使其子元素分別爲左和右子陣列的中間元素（O（n））。下面是一個例子，

 UNBALANCED BST 
      5 
     / \ 
     3  8 
      /\ 
      7 9 
      / \ 
      6  10 


     SORTED ARRAY 
     |3|5|6|7|8|9|10|

現在，這裏是遞歸調用和結果樹，

DSW(initial array) 

      7 
7.left = DSW(left array) //|3|5|6| 
7.right = DSW(right array) //|8|9|10| 

      7 
      /\ 
      5 9 
5.left = DSW(|3|) 
5.right = DSW(|6|) 
9.left = DSW(|8|) 
9.right = DSW(|10|) 

      7 
      /\ 
      5 9 
     /\/\ 
     3 6 8 10

來源

2016-07-04 17:27:30

非常感謝你的男人 – Noam

@Noam沒問題，如果你找到了答案有幫助那麼請不要忘記將其標記爲已接受。祝你好運！ –

會做。你也可以給我的問題+1，如果它是清楚和有用的。 – Noam

建立AVL樹的二進制搜索樹

回答

相關問題