數組和二叉搜索樹的效率有什麼區別？

我想知道什麼是最好的：數組或二進制搜索樹（插入，刪除，查找最大值和最小值）以及如何改進它們？數組和二叉搜索樹的效率有什麼區別？

2011-12-27 Totoo Boo

你有沒有嘗試搜索這些信息？應該很容易找到。 – Howard 2011-12-27 16:40:12

你的意思是抽象數據結構[鏈表]（http://en.wikipedia.org/wiki/Linked_list）和[二叉搜索樹]（http://en.wikipedia.org/wiki/Binary_search_tree）？ – Gumbo 2011-12-27 16:46:23

以什麼方式改進？最適合什麼？那些是完全不同的數據結構，並且它們中的每一個都可能對某個應用程序來說是「最好的」。 – amit 2011-12-27 16:52:03

array允許random access給它中的每個元素。因此您可以插入，刪除並查找O(1)中的特定元素，並在O(n)中刪除最大/最小值，刪除。 [你也可以改變最大/最小值O(1)並刪除O(n)]。如果你保持你的數組排序，它會導致插入/刪除O(n)，但你會獲得O(logn)查找，和O(1)分鐘/最大。

A BST按定義排序，對於常規[非平衡] BST，您會得到O(n)最壞情況的行爲。對於均衡BST，您將獲得O(logn)插入/刪除/查找。你可以得到O(1)分鐘/最大任何如何兩個。

陣列通常也會更快到iterate [假設迭代順序並不重要]，因爲您獲得更好的性能。另外，與BST不同的是，數組需要重新分配並在數組滿了時複製數據。像AVL或red-black-trees -

提高一個BST可以使其balanced來完成。

哪個更好？這取決於應用程序。通常，當您計劃插入數據並將其保存時，BST將是首選。如果隨機訪問或迭代是主要目的：您通常使用數組。數組和二叉搜索樹的

來源

2011-12-27 16:55:20 amit

爲什麼'findMin/findMax'常量操作'O（1）'爲平衡BST？ – Cratylus 2012-02-19 10:02:53

@ user384706：無論何時從平衡BST中插入/移除元素，對於非平衡BST都是「O（logn）」和「O（n）」。您可以維護額外的指針'min'和'max'，只有在您從BST插入/移除元素時纔會修改這些指針。找到新的最大值/最小值爲平衡BST的「O（logn）」和非平衡的「O（n）」 - 因此在該操作中沒有性能損失[大O項]，並且對於大O可以維護這些指針爲「免費」 – amit 2012-02-19 10:05:44

啊，所以你的意思是使用額外的指針。但在這種情況下，這是一個與BST算法沒有直接關係的優化。所以與它的比較聲稱有點不一致/誤導另一個數據結構（在這種情況下是一個數組），由於它不是默認的，所以'max/min'是'O（1）'必須實現它，使得它是 – Cratylus 2012-02-19 14:18:35

性能比較：

    Array      Binary search tree 
      Unsorted Sorted   Average   Worst case 
Space  O(n)  O(n)    O(n)    O(n) 
Search  O(n)  O(log n) *  O(log n)   O(n) 
Max/Min O(n)  O(1)    O(1) **   O(1) ** 
Insert  O(1)  O(n)    O(log n)   O(n) 
Delete  O(1)  O(n)    O(log n)   O(n)

*假設二進制搜索

**需要額外的指針MIN和MAX，否則它的O（log n）的

來源

2011-12-27 17:05:38 Peladao

爲什麼'O（1）'BST的查找最大/最小值？ – Cratylus 2012-02-19 10:04:18

現在你問，我不確定它是否正確。二叉搜索樹按照定義排序，但是（取決於實現？）可能無法獲取O（1）中的最小值/最大值。在這種情況下，它會是O（log n）。 – Peladao 2012-03-26 11:58:21

它不是'O（1）'，除非你的實現保持了一個指向'min'和'max'的值。查看amit的答案 – Cratylus 2012-03-26 15:38:55

數組和二叉搜索樹的效率有什麼區別？

回答

相關問題