完美平衡，線性時間

Question

如何重建二進制搜索樹，使其在線性時間內完美平衡？
我想我會做旋轉找到中位數，但我不知道它的好方法。

感謝您的任何想法。

Answer 1

最起碼，你可以做的兩個步驟：

1. 提取從樹上使用中序遍歷排序後的數組。

2. 構建一個近乎完美的二叉樹。例如，只需使用h = log n來加蓋高度，其中n是元素的數量。如果n不等於2 ^k -1對於某個整數k，則只會得到完美樹的一部分，但高度仍然是最小的。

以下是構建值1，2，3的樹，... 10的說明圖像：

  8 
    4   10 
2  6  9 
1 3 5 7 

可替換地，在步驟2中，可以把的中間元件數組作爲根，將剩餘的部分分成兩個大小相等的部分，並遞歸執行。舉例：

  5 
    2    8 
1  3  7  10 
     4  6  9 

每個步驟都可以在線性時間內執行。