排序二分查找樹

Question

當試圖將一組數字排序到二叉查找樹中時，是否總是有一種方法來排序它們，使樹具有最短高度，換句話說最有效？

Answer 1

一組數字可以通過將一個元素作爲樹的根並將其排列在其周圍的所有其他數字來轉換爲BST。我可以看到下面的情況與這個理論相矛盾：

選取一個根導致高度爲h的樹，其中左子樹比右子樹'高'。 挑選另一根導致另一棵樹，也是高度h，右側子樹比左側子樹'高'。

另一個簡單的例子包括交換兩個連續元素的插入順序，這兩個連續元素不直接相關，因此不會影響樹中每個其他元素的位置。

通過反例來防範。

讓集合S = {0, 1, 2, 3}。 插入元素融入到二叉搜索樹按以下順序：1, 0, 2, 3

1 
/\ 
0 2 
    \ 
     3 

插入元素融入到二叉搜索樹按以下順序：1, 2, 0, 3

1 
/\ 
0 2 
    \ 
     3 

由於這兩個樹有不同的順序的插入，但兩者都有最小高度，聲明只有一個插入順序提供了一個最小高度的二叉搜索樹是錯誤的。

如果在樹中的元素的實際順序是你很在意，在插入按以下順序集合中的元素：2, 1, 0, 3

2 
/\ 
    1 3 
/
0 

同樣，這棵樹有相同的高度因此表明樹中不同的項目排序也可以生成最小高度的樹。

---

（旁白）

你總是可以通過第一排序集合的元素，然後不斷地細分有序集合，以確保每一行的平衡和完整的灌裝建立一個最小高度樹。

• 取集合的中值元素。在偶數個元素的情況下，取兩個「中間」元素中較大的元素。這將成爲樹的根。
• 取中位數以下的所有元素。這將成爲根的左子樹。
• 取中位數以上的所有元素。這將成爲根的右側子樹。
• 從這些集合中遞歸地創建左右子樹。

這應該確保你有一個完整的二叉樹，它總是最小的高度。