兩種AVL樹的替代

Question

我目前有數據需要按照兩種不同的方式進行排序，從時間和空間複雜度PoV開始，有沒有其他方法可以維護兩棵樹，一棵按日期排序，一棵按ID碼排序？我需要能夠按照數據的順序返回列表，並通過ID返回單個用戶，並且我寧願不必遍歷或者更糟，遍歷並對數組返回進行排序。

任何見解或幫助非常感謝，謝謝！

Answer 1

你可以在一棵樹上做到這一點，但你只會得到O（logN）性能的日期。無論如何，ID直接檢索將是O（N）（即遍歷整棵樹以找到完全匹配），因爲順序將是不確定的。

如果您的ID可以基於您需要的日期（我的意思是如果ID可以基於日期生成） - 那麼您可以將O（N）時間複雜度降低到O（logN + M），其中M - 是特定日期的ID的子集。

因此，根據您的響應時間和內存要求，您可以保留一棵樹，或將其與ID的HashMap配對。

Answer 2

TreeMap implements Red-Black tree這是AVL的替代方案。

Answer 3

你可以使用一個LinkedHashMap（按照添加順序存儲和檢索對象或者具有O（1）複雜性的所有標準HashMap操作）。

如果您需要更復雜的日期訪問模式（範圍，點查詢），您可以使用相同的想法，但使用skip list而不是鏈接列表。在這種情況下，按日期訪問將是O（logN）。

然後還有一個選項可以在通過id放置值的樹上構建相同的（鏈接列表或跳過列表）。