java - 两个 AVL 树的替代方案

Question

我目前有我需要以两种不同方式排序的数据，从时间和空间复杂性 PoV，是否有任何替代方法来维护两棵树，一棵按日期排序，一棵按 ID 号排序？我需要能够按数据顺序返回列表，并按 ID 返回单个用户，我宁愿不必遍历，甚至更糟，遍历然后对数组返回进行排序。

非常感谢任何见解或帮助，谢谢!

Answer 1

您可以在一棵树中执行此操作，但您只会获得日期的 O(logN) 性能。无论如何，ID 直接检索将是 O(N)(即遍历整个树以找到完全匹配)，因为顺序是不确定的。

如果您的 ID 可以基于您需要的日期(我的意思是如果 ID 可以根据日期生成)——那么您可以将 O(N) 时间复杂度降低到 O(logN + M)，其中M - 是特定日期 ID 的子集。

因此，根据您的响应时间和内存要求，您可以只保留一棵树，或者将它与 ID 的 HashMap 配对。