我正在閱讀二叉搜索樹，並在想爲什麼我們需要BST？據我所知，所有的事情都可以使用簡單的排序數組來實現。對於例如 - 爲了構建具有n個元素的BST，我們需要n*O(log n)時間，即O(nlog n)，並且查找時間是O(log n)。但是這個東西也可以用數組來實現。我們可以有一個排序數組（需要O(nlog n)時間），查找時間也是O(log n)，即二進制搜索算法。那麼我們爲什麼還需要另一個數據結構呢？是否有任何其他使用/應用BST使它們如此特別？爲什麼二進制搜索樹？
- Ravi
數組是巨大的，如果你談論的是一次寫入，多次讀取類型的相互作用。這是當你開始插入，交換和刪除BST真正開始閃耀的時候，與數組相比。由於它們是基於節點的，而不是基於連續的內存塊，將元素移入集合或移出集合的成本很快，同時仍然保持集合的排序性質。
認爲它，你會鏈表與陣列之間插入的差異。這是一個過於簡單化，但突出了我上面提到的優勢的一個方面。
排序插入時間如何？
好的...發現新元素的正確位置仍然是O（log n），但是移位會成爲一個問題......但只是這一個......根據我讀過的文本，似乎是他們（BST）非常特別？我想知道更多關於使他們如此特別的事情。 – 2010-10-14 15:42:53
我認爲其他答案可能會對您有所幫助。另外要記住的是BST不是最終的數據結構，而是構成更復雜和更有效結構的基礎，這就解釋了它們的普及程度。例如，你可能知道在最壞的情況下搜索BST是線性的;這個問題的答案是AVL樹。你也有紅黑樹，2-3-4樹，後綴/前綴樹和DAWG等等，它們都以不同的方式概括了BST，並且產生了高效的算法，這些算法在數組的範圍之外。 – 2010-10-15 07:28:53
在圖形編程如果已擴展對象（即它代表在每個維度上的間隔，而不是隻是一個點），則可以將它們添加到一個二進制樹（通常是八叉樹），其中它們適合在完全的最小電平。
如果你不預先計算樹/ SortedList中的O（n）的列表中隨機插入時間可能極其緩慢。另一方面，樹中的插入時間僅爲O（log（n））。
想象一下，您有一個具有一百萬個元素的數組。
您想在的位置5.
所以你插入的數組的結尾，然後排序插入元素。
假設陣列已滿;那就是O（nlog n），即1,000,000 * 6 = 6,000,000次操作。
想象一下，你有一棵平衡的樹。
這是O（log n）的，加一點爲平衡= 6 +一點，稱之爲10個操作。
所以，你剛剛花了6,000,000 ops排序你的數組。然後你想找到那個元素。你是做什麼？二進制搜索 - O（log n） - 這就是，正好是，與您在樹中搜索時要做的相同！
現在想象你想要分配-otherother元素。你的數組已滿！你是做什麼？用n個額外的元素重新分配數組，memcpy很多？你真的想要memcpy 4mbytes？
在樹中，您只需添加另一個元素...
插入/從陣列版本中刪除的效率是多少？如果它涉及到移動陣列的所有其他元素，那可能是昂貴的。 – 2010-10-14 15:31:11
好的...找到新的/現有元素的正確位置仍然是O（log n），但是移位會成爲一個問題......但僅僅是這一個......根據我讀過的文本，似乎他們（BST ）很特別？我想知道更多關於使他們如此特別的事情。 – 2010-10-14 15:40:47
[binary search vs binary search tree]可能的重複（http://stackoverflow.com/questions/5968937/binary-search-vs-binary-search-tree） – nawfal 2014-06-15 08:38:37