是否有可能有一个AVL树按两个属性排序

Question

我正在实现我自己的数据结构来存储对象，这些对象有一个ID和附加日期。我必须执行的操作要求我有时按日期顺序返回一个数组，或者通过其ID来查找对象。我只是在考虑这个问题，当我坐下来编写代码时，它可能会变得明显不可能，但是我想知道，是否有可能说Node，节点left1，节点left2，节点right1，节点right2，然后实现两个同时添加函数某种双树，其中链接导致按日期排序的树和按ID排序的树？

我正在考虑这样做，尽量减少我的操作时间和空间的复杂性。

任何指导和帮助表示赞赏，谢谢！

Answer 1

这是可能的，但没有用，也很混乱（因为—例如—您需要单独的方法来重新平衡一棵树相对于另一棵树的节点，因此您基本上必须编写两个副本你的AVL树实现）。相反，你应该有两个独立的树，但是它们的节点可以（也应该）包含指向相同对象的指针（引用）。你可以（也应该）仍然把它包装在一个单一的对象中，这样客户端代码就不用担心两棵底层树的存在。

请注意，顺便说一下，一对树具有与单一树相同的渐近复杂度，因为2只是一个常数因子（并且不存在多于多项式的复杂性）。