什麼數據結構在時間和空間上都支持以下集合操作？集合操作的數據結構
我能想到的3點不同的方式來執行這些操作，假設我們有兩套，它們的大小都是N：
位陣列：
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
哈希表：
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
有序樹：
1. O(NlogN) 2.O(NlogN) 3.O(logN) 4.O(logN) 5.O(logN)
位陣列和Hashtable的速度快，但他們使用了太多的內存，有序樹是速度慢，但消耗的內存更少。
請注意：集可以包含其他類型的除了整數，如浮點數或字符串
哪些數據結構是快速和普通，和空間效率？
一個選項是用布隆過濾器來擴充您的有序樹，以加速ismemberof型號測試。
我認爲的整體行爲會是這樣的：
1. O(N log(N)) 2. O(?) 3.O(1) 4.O(log(N)) 5.O(log(N))
但是具體細節將取決於過濾器的大小，您集的大小和你的域的大小。
另一個選項可能是Judy Arrays。我聽說過這種用途的好處，但沒有親身經歷。
還有一種選擇是forrest approach（而不是純二叉樹）。
我建議Binary Heap（最簡單的一個），Binomial Heap（加快聯盟）和Fibonacci Heap（最難實施，但具有最知名的標準操作攤銷時間）。
操作 二元堆 二項式堆 斐波那契堆（攤銷）
1.聯合 爲O（n） O（logn）時間 O（1）
2。差 O（nlogn） O（nlogn） O（nlogn）
3.查找（ismemberof） 爲O（n） 爲O（n） 爲O（n）
4。添加 O（LGN） O（LGN） O（1）
5。刪除 O（LGN） O（LGN） O（LGN）
然而，這些結構大多使用時插入，查找/解壓分鐘（最大），工會和刪除需要操作。 找到和差異操作仍然有運行時間差。
什麼是你正在嘗試使用這種數據結構的應用程序？ – 2012-08-01 06:14:52
爲什麼不能哈希表（散集）保存任意（但可比）對象就像一個有序的樹？ – 2012-08-01 06:16:19
對於日誌分析，不是所有的操作都需要，但我很好奇。 – outlaw 2012-08-01 06:16:37