最近、データ構造クラスの場合、遅延削除（つまり、削除が必要なアイテムを最初にマークした後、後でマークされたアイテムをすべて削除する）という質問が配列、リンクされたリスト、またはバイナリツリーに対して有利な/不利なものです。 、あなたは、配列にインデックスが配列を横断する必要があるアルゴリズムでが削除されるたびにシフトするために取られる時間を節約になるので、これは、配列を助ける遅延ツリーは、バイナリツリーやリンクリストに対してどのようにメリットをもたらしますか？
状況や必要条件によってすべてが異なると思います。一般的な意味では、マークをつけて後で削除するこの方法を使用すると、すべて同じような賛否両論があります。
類似点数： - 削除のマークが付いていると、データ構造の移行がなくなり、削除がずっと速くなります。 - 削除されたアイテムの上に挿入することもできます。これは、挿入のためのシフトも意味しません。また、リストの終わりを探すのではなく最初の削除を上書きできるので、挿入が速くなります。
類似した短所： - 削除されたアイテムのためのスペースの浪費 - アイテムを削除するために2回横方向に移動し、それをマークしてもう一度削除するようにしました - 削除用の多くのマークが付いたアイテムは、削除されたアイテムを検索する必要があるため、時間がかかります。
おそらく、リンクされたリストの実装を少し深く考える必要があります。検索の時間が削除を実行するのに必要な時間であるため、遅延削除は何らかの方法で役立たないことを示します。
実際にリンクされたリストからアイテムを削除するために必要なことを考えてください。 注：これはSINGLYリンクリストを仮定しています（ダブルリンクリストではありません） 1）削除するアイテムを見つけます（これはSINGLEリンクリストであるため、PREVアイテムが必要なので常に検索する必要があります） 2）Keep PREVおよびNEXT要素へのポインタ 3）NEXT要素を指すように "PREV"要素を修正してください。 - したがって、CURRENT要素を二重リンクリストで隔離してください。また、NEXT要素を指し示す必要がありますPREV要素に渡します。 4）CURRENT要素に関連付けられたメモリを解放します。
ここで、遅延削除のプロセスは何ですか？ ---もっと短く 1）削除するアイテムを探します（削除するオブジェクトへのポインタがあるので、検索を実行する必要はありません） 2）削除するアイテムにマークを付けます。
*）「ガベージコレクション」を実行し、実際にシステムが「IDLE」
各要素は、左右を持っているリンクリストとして実装された二分木されたときに残りのステップを実行するためのスレッドを待ちます - ただし、引き続き同じ手順を実行します。バイナリツリーの検索は、私が信じるO（Log（n））の方が効率的です。
しかし、より多くのポインタ（ "LEFT"と "RIGHT"の両方）を扱うため、これらを削除する方が複雑になります。特に、ツリーノードを削除する場合左と右の両方のノードへのポインタを持っています - そのうちの1つは新しいルートに昇格する必要があります - しかし、どちらも既に左と右のポインタが割り当てられている場合はどうなりますか？元の「左/右」ノードはどこに行きますか？ - この時点でツリーのバランスをとる必要があります。したがって、ユーザの観点からの削除と、メモリの詳細を処理する「アイドル」ガベージコレクション（ユーザがそれを待つ必要はない）を有するマークによって著しい節約がある。
私はさまざまな理由から「それは依存している」と答えてくれるだろうと思っていますが、あなたは正しい方向にいると思います。
1）配列に穴がないという要件があると仮定して、配列に関するあなたの答えに同意します。削除するたびに配列を移動する必要がない場合は、今すぐマークを提案し、後で削除する方法はまったく役に立たないでしょう。いずれにしても、アルゴリズムのO（n）対（2O（n）= O（n））は等しいです。本当に考えられるのは、「すべての削除を一度に並べ替えるのではなく、それぞれの削除を並べ替えることで、いつでもあなたを保存できますか？」ということです。 mが削除の数であると仮定すると、配列内の最初の削除後の各要素が並べ替えられた回数は、今すぐマークのO（1）と比較してすぐに削除するO（m）です。
2）私はリンクリストのあなたの答えに同意します。
3）バイナリツリーについては、どのような種類に依存するかと思います。ソートされたバランスの取れたバイナリツリーを使用している場合、上記の1）と同じ質問を考慮する必要がありますが、そうでない場合は、考え方が正しいのでリンクリストのように正しく動作するはずです。