12

二分木のすべてのノードを削除するための標準的なアルゴリズムは、これらの線に沿ったノードのポストオーダートラバーサルを使用します。

if (root is not null) {
   recursively delete left subtree
   recursively delete right subtree
   delete root
}

このアルゴリズムは、再帰呼び出し中にスタックフレームを格納するために必要なスペースのため、O（h）補助記憶スペースを使用します。hはツリーの高さです。ただし、すべてのノードが1回だけアクセスされるため、時間O（n）で実行されます。

ランタイムを犠牲にすることなく、O（1）補助記憶域のみを使用してバイナリツリー内のすべてのノードを削除するアルゴリズムはありますか？

4

4 に答える 4

18

ツリーの回転に基づくアルゴリズムを使用して、O(n) および O(1) の補助記憶領域を使用して、バイナリ ツリー内のすべてのノードを削除することは実際に可能です。

次の形状の二分木があるとします。

           u
          / \
         v   C
        / \
       A   B

このツリーを右に回転すると、ノード v がノード u の上に引っ張られ、次のツリーになります。

        v
       / \
      A   u
         / \
        B   C

ツリーの回転は、ツリーのルートを v に変更し、u の左の子を v の前の右の子に設定し、v の右の子を u に設定するだけで、O(1) 時間と空間で実行できることに注意してください。

右回転は常にツリーの左サブツリーの高さを 1 つ減らすため、ツリー回転はこのコンテキストで役立ちます。これは、巧妙な観察のために役立ちます。ツリーのルートに左のサブチャイルドがない場合、ルートを削除するのは非常に簡単です。特に、ツリーが次のような形状の場合:

     v
      \
       A

次に、ノード v を削除してから、そのサブツリー A のすべてのノードを削除することで、ツリー内のすべてのノードを削除できます。これにより、ツリー内のすべてのノードを削除するための非常に単純なアルゴリズムが得られます。

while (root is not null) {
    if (root has a left child) {
        perform a right rotation
    } else {
        delete the root, and make the root's right child the new root.
    }
}

このアルゴリズムは明らかに O(1) ストレージ スペースのみを使用します。ローテーションを実行したり、ルートを変更したりするために必要なポインターの数は最大でも一定であり、これらのポインターのスペースはループのすべての反復で再利用できるからです。

さらに、このアルゴリズムも O(n) 時間で実行されることを示すことができます。直感的に、特定のエッジを何回回転できるかを見ることで、これを確認できます。最初に、右回転が実行されるたびに、ノードからその左の子に向かうエッジが、前の子からその親に戻る右エッジに変換されることに注意してください。次に、ノード u をノード v の右の子に移動するローテーションを実行すると、ノード v と v のすべての左サブツリーを削除するまで、ノード u に二度と触れないことに注意してください。その結果、ツリー内のすべてのエッジがその親と一緒に最大 1 回回転することに注意することで、これまでに実行される合計回転数を制限できます。その結果、最大で O(n) 回のローテーションが行われ、それぞれに O(1) の時間がかかり、正確に n 回の削除が行われます。

それが役立つ場合は、アルゴリズムの動作のより詳細な分析とともに、このアルゴリズムの C++ 実装があります。また、アルゴリズムのすべてのステップの正しさの正式な証明も含まれています。

お役に立てれば！

于 2012-12-24T23:07:48.787 に答える
3

真面目な冗談から始めましょう。BST のルートを null に設定すると、ツリー内のすべてのノードが効果的に削除されます (ガベージ コレクターによってスペースが使用可能になります)。言葉遣いは Java 固有のものですが、考え方は他のプログラミング言語にも当てはまります。あなたが就職の面接や試験を受けていた場合に備えて、これについて言及します.

それ以外の場合は、変更されたバージョンの を使用するだけですDSW algorithm。基本的に、ツリーをバックボーンに変えてから、linked list. 空間 O(1) と時間 O(n)。教科書やオンラインで DSW の話が見つかるはずです。

基本的に DSW は BST のバランスをとるために使用されます。しかし、あなたの場合、バックボーンを取得したら、バランスをとるのではなく、リンクされたリストのように削除します。

于 2012-12-24T23:36:05.533 に答える