我試圖解決以下問題：「給定一個具有唯一整數元素的排序（遞增順序）數組，寫一個算法來創建一個具有最小高度的BST。最小高度的BST
給定的答案將根節點作爲數組的中間。雖然這樣做對我來說很直觀，但我試圖嚴格證明，最好將根節點設置在數組中間。
本書給出的理由是：「爲了創建最小高度的樹，我們需要儘可能地將左子樹中的節點數量與右子樹中的節點數量相匹配，這意味着我們希望根節點是數組的中間部分，因爲這意味着一半的元素會少於根，另一半會更大。「
我想問：
爲什麼會最小高度的任何樹是其中的左子樹的節點數目儘可能在右子樹爲等於節點的數目？ （或者，您有任何其他方式可以證明最好將根節點設置在陣列的中間位置嗎？）
樹是否與平衡的樹相同？從上一個關於SO的問題來看，這是我得到的印象，（Visualizing a balanced tree），但我很困惑，因爲這本書明確指出「BST具有最小的高度」並且從未「平衡BST」。
謝謝。
來源：破解編碼採訪
我喜歡去想它，如果你使用樹旋轉（鋸齒鋸齒和曲折旋轉）平衡樹的方式，你最終會達到一個狀態其中左邊和右邊的子樹至多相差一個高度。並不總是這樣一棵平衡的樹必須在右邊和左邊具有相同數量的孩子;然而，如果你有那個不變量（每邊有相同數量的孩子），你可以到達一棵使用樹輪平衡的樹）
平衡是任意定義的。 AVL樹定義它的方式是樹的子樹沒有一個高度相差超過一個的子樹。其他樹木以不同的方式定義平衡，所以它們不是同一個區別。它們本質上相關但不完全相同。這就是說，在任何定義下，一個最小高度的樹將總是平衡的，因爲平衡是爲了保持BST的O（log（n））查找時間。
如果我錯過了任何東西或說錯了什麼，請隨時編輯/糾正我。 希望這有助於
最小高度的任何樹爲何將是其中的左子樹節點 的數量儘可能在 右子樹爲等於節點的數目？
可能會出現這樣一種情況，即在最小高度的樹中，當前平衡的樹可以在左側和右側具有不同數量的節點數。 BST最壞情況遍歷是O（n），如果它是排序的，並且在最小高度樹中，最壞情況的複雜度是O（log n）。
*
/\
* *
/
*
在這裏，您可以清楚地看到左節點數和右節點並不相等，儘管它是最小高度樹。
樹的高度是否與平衡的樹相同？從上一個關於SO的問題來看，這就是我得到的印象（可視化一棵平衡的樹），但我很困惑，因爲這本書明確指出「BST具有最小高度」，並且從來沒有「平衡BST」。
最小高度樹是平衡的一個，更多的細節，你可以看看AVL樹，也被稱爲高度平衡樹。使BST成爲高度平衡的樹時，您必須執行旋轉（LR，RR，LL，RL）。