從分類列表中生成多個AVL樹？

Question

我正在研究一個AVL樹的任務，我對他們的定義有個疑問 - 我們給出了一個排序列表，我們必須在O（n）時間內從它生成一個AVL樹。我已經完成了這個（感謝來自StackOverflow的其他幫助！），但是我的結果雖然是有效的AVL樹，但與提供的示例結果不同。多個AVL樹能夠從同一個排序列表中生成嗎？

謝謝！

Answer 1

是的。考慮只有兩個節點的樹的退化情況。在這種情況下，任一節點都可以是根節點，另一個節點可以是葉節點。就整體平衡而言，這兩者是相當的。

Answer 2

是，例如，這些都是< 1,2,3,4,5>兩種可能的AVL樹：

（2 1（3 4 5））

和

（4-（2 1 3）5）

其中（一個T1 T2）表示具有根，左側樹T1和左右T2的樹。