是否有可能有一個AVL樹按兩個屬性排序

Question

我正在實現我自己的數據結構來存儲對象，這些對象有一個ID和附加日期。我必須執行的操作要求我有時按日期順序返回一個數組，或者通過其ID來查找對象。我只是在考慮這個問題，當我坐下來編寫代碼時，它可能會變得明顯不可能，但是我想知道，是否有可能說Node，節點left1，節點left2，節點right1，節點right2，然後實現兩個同時添加函數某種雙樹，其中鏈接導致按日期排序的樹和按ID排序的樹？

我正在考慮這樣做，儘量減少我的操作時間和空間的複雜性。

任何指導和幫助表示讚賞，謝謝！

Answer 1

這是可能的，但沒有用，也很混亂（因爲—例如—您需要單獨的方法來重新平衡一棵樹相對於另一棵樹的節點，因此您基本上必須編寫兩個副本你的AVL樹實現）。相反，你應該有兩個獨立的樹，但是它們的節點可以（也應該）包含指向相同對象的指針（引用）。你可以（也應該）仍然把它包裝在一個單一的對象中，這樣客戶端代碼就不用擔心兩棵底層樹的存在。

請注意，順便說一下，一對樹具有與單一樹相同的漸近複雜度，因爲2只是一個常數因子（並且不存在多於多項式的複雜性）。