两个 AVL 树的替代方案
An alternative to two AVL trees
我目前有我需要以两种不同方式排序的数据，从时间和 space 复杂性 PoV，是否有任何替代方法来维护两棵树，一棵按日期排序，一棵按 ID 号排序？我需要能够 return 按数据顺序列出，并按 ID 列出单个用户，我宁愿不必遍历，甚至更糟，遍历然后对数组 return 进行排序。
非常感谢任何见解或帮助，谢谢！
TreeMap implements Red-Black tree 是 AVL 的替代品。
你可以在一棵树中做到这一点，但你只会在日期上获得 O(logN) 的性能。无论如何，ID 直接检索将是 O(N)（即遍历整棵树以找到完全匹配），因为顺序是不确定的。
如果您的 ID 可以基于您需要的日期（我的意思是如果 ID 可以根据日期生成）-那么您可以将 O(N) 时间复杂度降低到 O(logN + M) ，其中 M - 是特定日期 ID 的子集。
因此，根据您的响应时间和内存要求，您可以只保留一棵树，或者将其与 HashMap 个 ID 配对。
我目前有我需要以两种不同方式排序的数据，从时间和 space 复杂性 PoV，是否有任何替代方法来维护两棵树，一棵按日期排序，一棵按 ID 号排序？我需要能够 return 按数据顺序列出，并按 ID 列出单个用户，我宁愿不必遍历，甚至更糟，遍历然后对数组 return 进行排序。
非常感谢任何见解或帮助，谢谢！
TreeMap implements Red-Black tree 是 AVL 的替代品。
你可以在一棵树中做到这一点，但你只会在日期上获得 O(logN) 的性能。无论如何，ID 直接检索将是 O(N)（即遍历整棵树以找到完全匹配），因为顺序是不确定的。
如果您的 ID 可以基于您需要的日期（我的意思是如果 ID 可以根据日期生成）-那么您可以将 O(N) 时间复杂度降低到 O(logN + M) ，其中 M - 是特定日期 ID 的子集。
因此，根据您的响应时间和内存要求，您可以只保留一棵树，或者将其与 HashMap 个 ID 配对。