2

私は自分のコードに AVL ツリーを C++ で実装していますが、この問題はコード自体よりも AVL ツリーを理解することに関係しています。ここに収まらない場合は申し訳ありませんが、インターネットをクロールしましたが、まだ問題の解決策が見つかりません.

私のコードは、比較的小さな入力 (~25-30 桁) で期待どおりに動作するので、それ以上の入力でも動作するはずです。挿入中にアクセスしたノードを保持する配列を使用してから、while ループを使用して、必要に応じて各ノードの高さを上げています。高さが等しいノードが見つかったら、この手順を終了する必要があることを知っています。 (それらの減算結果は 0 です)。

問題は、バランスをとるときです。各ノードのバランス係数を見つけて、ツリーのバランスを正しくとることはできますが、バランスを取った後に高さの調整をやめて、挿入ループを終了するか、条件が意図されるまで続行するかはわかりません。今それを出します。ノードの削除とツリーの再バランスの間、チェックを続ける必要があることはわかっていますが、挿入とバランスについてはよくわかりません。

誰でもこれについての洞察と、おそらくいくつかのドキュメントを提供できますか?

4

2 に答える 2

0

将来の読者のために、私の例のようにバイナリツリーを実装している場合は、バランスをとったノードの上のノードの高さを編集する必要はありません。

           10
        (1)/ \(2)
         8   16
          (1)/ \(0)
            11 

(Numbers in parenthesis are the height of each sub tree)

上記のツリーよりも、次のノードを挿入するとしますdata=15。結果のサブツリーは次のようになります。

           10
        (1)/ \(2)
         8   16
          (1)/ \(0)
            11
        (0)/  \(1)
              15

サブツリーの以前の高さがまだ編集されていないことに注意してください。挿入が成功した後、挿入パス（この場合は。）を実行します(11, 16, 10)。このパスを実行した後、必要に応じて高さを編集します。つまり、16のサブツリーの左側の高さは2になり、サブツリーの右側の高さは0になり、AVLツリーのバランスが崩れます。2回転でツリーのバランスをとった後、サブツリーは次のようになります。

             15
         (1)/  \(1)
           11  16

したがって、サブツリーの高さは以前と同様に最大1です。したがって、このサブツリーのルートより上の高さは変更されておらず、高さを変更する関数が変更されている必要がありreturnます。

于 2013-01-11T16:07:55.043 に答える
0

一度に 1 つの項目のみを挿入する場合: 挿入によってバランスが崩れた後、AVL ツリーを再調整するために必要な回転は 1 回 (1 回または 2 回) だけです。http://cis.stvincent.edu/html/tutorials/swd/avltrees/avltrees.html結論がわかれば、おそらく自分で証明できます。

于 2012-11-30T09:07:48.213 に答える