は、AVLツリー

Question

私はバランス-AVL木の質問とのトラブルを抱えているのバランスをとります。私はAVLツリーのオンライン視覚化を見てきました。そして、私は正しいことを示唆しています。私の教科書は間違っていますか？

これは木である：

私は、このAVLツリーに65を挿入する必要があります。これは不均衡の原因となり、私の理解からは、右回りの回転が必要です。ここで

は、私が思い付くものです、そしてhttp://robinsswei.github.io/VisGraphs/avltree.htmlを経由して確認しました：

そして、ここでは私の教科書は述べて何か正しい答えている：

1が正しい

回答？

Answer 1

ちょっとそこ、 は、私は実際に両方のソリューションが正しいことだと思います。あなたの本が違うかもしれないいくつかの理由があると思います。ノードを挿入すると、2つの異なるノードのバランス係数が2になります。それはノード34とノード45でした。そのアルゴリズムがどのように機能するかは、挿入後です。それは、そのノードの高さを更新するとともに、バランス要素をチェックするルートノードに戻るパスに従います。私は根が最後にアクセスされ、回転のためにフラグが立てられていたので、それはそれがそうした理由です。別の潜在的な理由は、ルートノードの場合、回転は単純な回転を必要とし、一方、回転ノードは二重回転を必要とするということです。どちらにせよ、私は両方の答えが適切だと感じています。

私はAVLの木が何であるかを知らないかもしれない人のために、この問題を説明しようとするでしょう。私はこれのイラストにもラベルを貼ろうとしました。最初に行うことは、新しいノードを挿入する前に、開始するAVLツリーが要件を満たしていることを確認することです。各ノードの高さにラベルを付け、親ごとに子ノードの高さの違いを取得するだけです。

AVLの木は、すべてのノードの左と右の子供の高さは、せいぜい1または-1によって異なることが必要です。下から上へと、ID開始を挿入する前に、最初の図の例では（-1,0,1）

、。ノード87にはこれに対する子がありません。ノード45には子が1つしかないので、87の0の高さを計算します。ノード3には子がないので、これも0になります。ノード34には2つの子、3と45があります。その違いは1だけです。すべてのノードがAVLツリーテストに合格しています。

次ちょうどちょうどバイナリ検索ツリーのようにそれを横断してノードを挿入します。

ノードの高さを挿入後に変更し、ノードごとに再度比較します。今回は、ノード34（ルートノード）が子ども（2-0）に「2」の違いがあることがわかります。ノード34に回転が必要であることがわかりました。
単純な左回転を実行し、AVLプロパティが満たされました。

Answer 2

45のルートと第二の一方が正解です。平衡型AVLツリーは、子の長さ（深度）を同じにする必要があります。だから65歳になったら、あなたの木はバランスが取れません。したがって、ノードを左にシフトする必要があります。