1

Insert新しい要素をAVLツリーに挿入しながらアクションを更新しようとしています。アクションを更新するとinsert、ルートツリーのサイズが各ノードに追加されます。

ここで、要素をボトムアップで挿入するので、+1ツアー中に通過するすべてのノードにを追加すると、たとえば、新しいツリーの後にツリーのバランスをとる必要がある場合など、これが機能しない場合があります。ポインタを変更するため、バランスが取れていないため、計算が正しくありません。

どうすればそれを正しく行うことができるかというアイデアやヒントはありますか？

4

1 に答える 1

1

簡単な解決策は、サイズの定義で単純に変更することです。

size = 1ルートへのツアーの一部である、またはロール (下から上へ) セットの一部であった各ノードに対して、 leafs を指定します。

size(v) = size(v.left) + size(v.right) + 1
            ^                 ^          ^
        size of left     size of right   size of "root"
           subtree        subtree

各ステップで変更されたすべての頂点を修正するため、これは正しいでしょう。また、ボトムアップで行うため、修正する各ノードのサイズを正しく計算できます。

そのような頂点ごとに-一定数のOPを実行しているため、複雑さには影響しないことに注意してください。とにかくトラバースした頂点に対してのみ実行しています。

于 2012-05-29T07:14:38.520 に答える