两种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放置值的树上构建相同的（链接列表或跳过列表）。