插入元素的順序將導致完美平衡的二叉搜索樹？

Question

我想通過這個問題在教科書工作似乎並不能完全理解它：

• 確定插入的這些元素的次序： 將導致一個完全平衡的二叉搜索樹。

• 的要素是：{10，11，15，19，23，78，42，56，18，13，12，38， 47}

我能夠構建BST並正確平衡它，但我不知道如何在構建樹之前對元素進行排序以保證樹狀結構均衡。

Answer 1

首先，我們對這些元素進行排序，然後開始構建平衡BST。現在我們需要選擇一個元素作爲樹的根，以保證樹平衡，所以我們從已排序的元素中選擇中間元素。那麼我們需要做出選擇哪一個是左邊的孩子。有兩個已排序的子陣列 - 左側和右側。這是分而治之，這兩個陣列是原始問題的子問題。然後，我們從左排序子數組中選擇中間元素作爲左子節點，從右排序子數組中選擇中間元素作爲右子節點，依此類推。

所以構造樹，以保證平衡樹之前元素的順序如下決定：元素

• 排序。
• 第一個元素是來自排序元素的中間元素。
• 第二個元素是左排序數組中的中間元素。
• 第三個元素是來自正確排序數組的中間元素。
• 等等。

爲你給元件，順序是：
19，12，42，10，15，23，56，11，13，18，38，47，78