2

順序付けられていないセットs{3,6,5,1,2,4}があり、AVLツリーを構築する必要があるとします。
これで問題ありません...基本的な回転を理解し、ここでこのポイントに到達します。

                               5 
                             /   \
                            2      6
                           / \
                         1     3

しかし、4を挿入しようとすると、すべてがバラバラになり、最終的な答えは（左の）として得られます。

             4      But the actual answer is:      3
           /   \                                 /   \
          2     5                               2     5
         / \     \                             /     / \
        1   3     6                           1     4   6

そして、それを分解すると、同じローテーションを実行してスタックする
ので、このAVLに有効な親とローテーションを実行するにはどうすればよいですか？

そして私の解決策は有効ですか？

4

1 に答える 1

2

私が理解しているように、最初に 4 を追加すると、次のツリーが得られます。

    5
   / \
  2   6
 / \
1   3
     \
      4

先に進むには、Wikipedia の AVL ツリーに関する記事を参照してください。ノード 5のバランス係数(これは記事で定義されていることに注意してください) は +2 で、ノード 2 のバランス係数は -1 であるため、最初にノード 2 サブツリーを左にローテーションする必要があります。

      5
     / \
    3   6
   / \
  2   4
 /
1

次に、ツリー全体を右に回転させる必要があります (ノード 5 について)。

    3
   / \
  2   5
 /   / \
1   4   6

それは理にかなっていますか？

于 2011-06-12T19:06:01.053 に答える