avl-tree - ソートされたリストからの複数の AVL ツリー?

Question

私は AVL ツリーの割り当てに取り組んでおり、それらの定義について簡単な質問があります。ソートされたリストが与えられ、そこから O(n) 時間で AVL ツリーを生成する必要があります。私はこれを完了しました (StackOverflow からの他の助けのおかげで!)、私の結果は、有効な AVL ツリーでありながら、提供された例の結果とは異なります。同じソート済みリストから複数の AVL ツリーを生成できますか?

ありがとう！

Answer 1

はい。ノードが 2 つしかないツリーの縮退のケースを考えてみましょう。この場合、どちらかのノードがルートになり、もう一方がリーフになります。全体的なバランスに関しては、この 2 つは同等です。

Answer 2

はい、たとえば、これらは <1,2,3,4,5> の 2 つの可能な AVL ツリーです。

(2 1 (3 4 5))

と

(4 (2 1 3) 5)

ここで、(a T1 T2) はルート a、左ツリー T1、左右 T2 を持つツリーを表します。