O（1）補助記憶空間を使用してバイナリツリー内のすべてのノードを削除しますか？

Question

binary tree内のすべてのノードを削除するための標準的なアルゴリズムはこれらの線に沿ったノード上postorder traversalを使用する：

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

このアルゴリズムは、hは木の高さであるO（H）補助記憶空間を使用してこれは、再帰呼び出し中にスタックフレームを格納するために必要な領域があるためです。しかし、すべてのノードが正確に1回訪問されるので、時刻O（n）で実行されます。

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

Answer 1

tree rotationsに基づくアルゴリズムを使用して、O（n）とO（1）の補助記憶領域を使用してバイナリツリー内のすべてのノードを削除することは本当に可能です。

  u 
     /\ 
     v C 
     /\ 
     A B 

このツリーの右回転は、次のツリー内のノードuと結果上記ノードvを引っ張る：

 v 
    /\ 
     A u 
     /\ 
     B C 

留意されたい。以下の形状のバイナリツリーを考える

uの左の子をvの前の右の子に設定し、次にvの右の子をuに設定することによって、ツリーのルートをvに変更するだけで、O（1）時間と空間でツリーの回転を行うことができます。

右回転は、ツリーの左のサブツリーの高さを常に1ずつ減らすので、このコンテキストではツリーの回転が便利です。これは、賢明な観察のために役立ちます。左の子要素がない場合、ツリーのルートを削除するのは非常に簡単です。ツリーがこのような形をしている場合は特に、：

 v 
     \ 
     A 

その後、我々は、これは非常に単純につながるそのサブツリーA.内のすべてのノードを削除、ノードvを削除することで、ツリー内のすべてのノードを削除することができますツリー内のすべてのノードを削除するためのアルゴリズム：

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. 
    } 
} 

それは回転を行うのか、rootと変更することで、ほとんどのポインタの一定の数を必要とするため、このアルゴリズムは明らかに、（1）ストレージスペースのみOを使用していますこれらのポインタのスペースは、ループのすべての反復にわたって再利用できます。

また、このアルゴリズムもO（n）時間で実行されることがわかります。直感的には、所定のエッジを何回回転させることができるかを見ることでこれを見ることができます。最初に、右回転が実行されるたびに、ノードからその左の子に向かうエッジが、元の子からその親に戻る右端に変換されることに注目してください。次に、ノードvをノードvの右の子に移動するローテーションを実行すると、ノードvとすべてのvの左のサブツリーが削除されるまで、ノードuに再び触れることはありません。その結果、ツリー内のすべてのエッジが親を最大で1回回転することに注目して、これまでに行われるトータルローテーションの回数を制限することができます。その結果、多くのO（n）回の回転が行われ、各回転にはO（1）時間がかかり、正確にn回の削除が行われます。これは、アルゴリズムが時間O（n）で実行され、O（1）空間のみを使用することを意味します。

私はa C++ implementation of this algorithmを持っており、アルゴリズムの動作の詳細な分析を行っています。また、アルゴリズムのすべてのステップの正当性を正式に証明しています。

希望すると便利です。

Answer 2

深刻な冗談から始めましょう：BSTのルートをnullに設定すると、ツリー内のすべてのノードが効果的に削除されます（ガベージコレクタによって空きが確保されます）。用語はJava固有のものですが、他のプログラミング言語にも当てはまります。あなたが就職インタビューや試験を受けている場合に備えて、私はこれを言います。

それ以外の場合は、DSW algorithmの変更バージョンを使用するだけです。基本的には、ツリーをバックボーンにして、linked listのように削除します。空間O（1）および時間O（n）。あなたは教科書やオンラインでDSWの話を見つける必要があります。

基本的にDSWは、BSTのバランスをとるために使用されます。しかし、あなたのケースでは、一度あなたがリンクされているリストのように、バランスを取るのではなく、バックボーンを得る。