使用重複鍵存儲自排序列表的正確數據結構是什麼？

Question

我需要能夠在O（log（n））複雜度下工作的東西，並且我想到了AVL樹，但問題是有些鍵可能會重複自己（例如，一個人的分數），所以我想不出來如何實現它作爲一棵樹。什麼是正確的方法來做到這一點？

Answer 1

有很多選項可用。由於平衡操作（通常）純粹由旋轉組成，所以二元搜索樹的大多數風格都可以很容易地修改以允許具有重複值的節點，從而保持序列的順序。對於這樣的情況，你只需要做一個正常的BST插入，但是每當你看到一個重複的值時，你可以任意地向左或向右移動，並繼續，就好像這個值是不同的。

跳過列表特別容易更新以支持每個密鑰的多個副本，因爲他們不會對插入或刪除做任何複雜的結構更新。

如果你沒有與每個鍵關聯的輔助信息，那麼另一個更簡單的辦法是存儲標準的二叉搜索樹，但要增加一個「計數」字段說明場有多少邏輯副本的每個節點存在。每次插入時，如果密鑰不存在，則使用計數1創建它。如果它已經存在，則只需在現有節點中增加計數。刪除將類似地執行。當然，如果你不想推出你自己的數據結構，那就去找一個很好的multimap或multiset實現，這應該很好地爲你完成工作。根據您選擇的編程語言，您甚至可以在標準庫中找到它們。 :-)