是否可以按两个属性对 AVL 树进行排序
Is it possible to have an AVL tree sorted by two properties
我正在实现我自己的数据结构来存储对象,这些对象有一个 ID 和一个附加的日期。我必须实现的操作要求我有时 return 按日期顺序说一个数组,或按 ID 查找一个对象。
在这种情况下如何最小化日期和 ID 的时间复杂度,最好的方法是拥有两个单独的树并接受存储复杂度成本吗?
感谢任何指导和帮助,谢谢!
这是可能的,但没有用,而且非常混乱(因为——例如——你需要单独的方法来重新平衡一个节点相对于一棵树与另一棵树的关系,所以你基本上必须写两个AVL 树实现的副本)。相反,您应该有两个单独的树,但它们的节点可以(并且应该)包含指向相同对象的指针(引用)。您仍然可以(并且应该)将其包装在一个对象中,这样客户端代码就不必担心两个底层树的存在。
注意,顺便说一句,一对树与单棵树具有相同的渐近复杂度,因为 2 只是一个常数因子(并且不涉及多项式复杂度)。
我正在实现我自己的数据结构来存储对象,这些对象有一个 ID 和一个附加的日期。我必须实现的操作要求我有时 return 按日期顺序说一个数组,或按 ID 查找一个对象。
在这种情况下如何最小化日期和 ID 的时间复杂度,最好的方法是拥有两个单独的树并接受存储复杂度成本吗?
感谢任何指导和帮助,谢谢!
这是可能的,但没有用,而且非常混乱(因为——例如——你需要单独的方法来重新平衡一个节点相对于一棵树与另一棵树的关系,所以你基本上必须写两个AVL 树实现的副本)。相反,您应该有两个单独的树,但它们的节点可以(并且应该)包含指向相同对象的指针(引用)。您仍然可以(并且应该)将其包装在一个对象中,这样客户端代码就不必担心两个底层树的存在。
注意,顺便说一句,一对树与单棵树具有相同的渐近复杂度,因为 2 只是一个常数因子(并且不涉及多项式复杂度)。