瞭解二進制搜索樹構建

Question

我很難理解如何構建二叉搜索樹。他們是否需要對初始數據進行排序才能找到最頂級的根？

Answer 1

一個二叉搜索樹需要的形狀取決於兩件事情：

1. 其中元素插入的順序，並
2. 什麼平衡操作，如果有的話，樹插入操作中一樣。

如果你有一個沒有任何重新平衡邏輯的純二叉搜索樹，那麼元素插入的順序將對樹的形狀產生很大的影響。例如，取值1,2,3,4,5,6,7。如果您按照順序4,2,6,1,3,5,7插入它們，您將獲得此樹：

 4 
    / \ 
    2  6 
    /\ /\ 
    1 3 5 7 

這樣做的原因是，我們通過下面一系列的樹木：

 4 

    4 
/
    2 

    4 
/ \ 
    2  6 

    4 
/ \ 
    2  6 
/
1 

    4 
/ \ 
    2  6 
/\ 
1 3 

    4 
/ \ 
    2  6 
/\ /
1 3 5 

    4 
/ \ 
    2  6 
/\ /\ 
1 3 5 7 

在另一方面，如果在順序1，2，3，4，5，6插入值，7，你得到這棵樹：

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 

有趣的是，按排序順序插入元素到BST是o 最糟糕的你可以爲樹做的事情，因爲它使樹成爲線性結構。你最好挑選元素的隨機排列插入，或對它們進行分類，並使用在排序序列中的下列遞歸算法（如果他們事先所有已知）：

• 如果沒有的元素，你完成了。
• 否則：
  • 將中位數插入BST。
  • 將前半部分元素遞歸地插入到BST中。
  • 以遞歸方式將第二部分元素插入到BST中。

希望這有助於！ 「