我正在尋找一個數據結構（或結構），可以讓我保持一個有序的整數列表，沒有重複索引和值相同的整數範圍。快速隨機訪問，搜索，插入和刪除的高效數據結構
我需要四個主要的業務是高效的，在重要性的粗糙順序：
在刪除的值使用在O（1）的陣列我有1個，但圖2是O（N）和插入和刪除很昂貴（我相信O（N））。
鏈接列表有O（1）插入和刪除（一旦你有節點），但1和2是O（N），從而否定增益。
我試着保留兩個數組a [index] = value和b [value] = index，將1和2變成O（1），但將3和4變成更昂貴的操作。
有更好的數據結構嗎？
我會使用red-black tree將鍵映射到值。這給你O（log（n））1,3,4。它還按照排序順序維護鍵。
對於2，我將使用散列表將值映射到鍵，從而爲您提供O（1）性能。它還添加了O（1）開銷，用於在添加和刪除紅黑樹中的密鑰時更新哈希表。
如何使用二叉搜索排序數組？
插入和刪除很慢。但考慮到數據是純數據，如果您使用C或C++，可以使用memcpy（）調用來優化整數。如果知道數組的最大大小，則可以避免在使用數組期間分配任何內存，因爲您可以將其預分配給最大大小。
「最佳」方法取決於您需要存儲多少個項目以及您需要插入/刪除的頻率與查找的頻率。如果你很少插入或刪除一個帶有O（1）的排序數組，那麼訪問值肯定會更好，但是如果你經常插入和刪除東西，二叉樹可能比數組好。對於一個足夠小的陣列來說，在任何情況下陣列都最有可能擊敗樹。
如果存儲大小值得關注，那麼該數組也比樹更好。樹還需要爲它們存儲的每個項目分配內存，因爲只存儲小值（整數），所以內存分配的開銷可能很大。
您可能想要簡介什麼是更快，如果您從排序的數組中插入/刪除或與它的內存（德）分配樹的複製整數的複製。
在這種情況下的插入是可怕的... – 2009-05-20 21:35:44
插入和刪除是OP的列表中的最後一個，並且整數可以通過調用memcpy（） 。 – lothar 2009-05-20 21:37:51
樹形圖怎麼樣？日誌（n）描述的操作。
我很喜歡平衡的二叉樹。它們有時比散列表或其他結構慢，但它們更容易預測;對於所有操作他們通常是O(log n)。我建議使用Red-black tree或AVL tree。
我不知道你在用什麼語言，但是如果是Java，你可以利用LinkedHashMap或者類似的Collection。它具有列表和地圖的所有優點，爲大多數操作提供了持續時間，並且具有大象的內存佔用空間。 :)
如果您不使用Java，LinkedHashMap的想法可能仍然適用於您的問題的可用數據結構。
如果您在.NET正在工作，然後根據MS文檔http://msdn.microsoft.com/en-us/library/f7fta44c.aspx
這兩者因內存使用情況和插入/移除速度而異。 SortedList使用的內存少於SortedDictionary。如果SortedList從已排序的數據一次全部填充，則它比SortedDictionary快。所以這取決於哪種情況對你來說是最好的。
此外，您的鏈接列表的參數並不是真正有效的，因爲它可能是O（1）的插入，但您必須遍歷列表才能找到插入點，所以實際上並非如此。
如何用RB樹實現2？我們可以讓他們對每個插入/刪除操作的孩子進行計數。這並不會使這些操作持續更長時間。然後在日誌中找到第i個元素是可能的。但是我看不到在java和stl中實現這個方法。
使用向量來訪問數組。
使用地圖作爲下標到搜索引擎中的搜索索引。
您使用哪種語言？ – 2009-05-20 21:36:04
應該不是很重要，但它是C++ – Leonel 2009-05-21 03:48:11
它確實很重要;並非所有的語言都提供相同的數據結構。例如，這個特定問題可以通過C Judy數組或C＃CPTrie非常有效地解決。 （或者，當然，Ayman建議的某種平衡二叉樹。） – Qwertie 2011-04-11 19:55:35