c++ - 赤黒木から複数の要素を削除するアルゴリズム

Question

RB で複数のノードを削除できるアルゴリズムはありますか、または RB からノードを削除する唯一のアルゴリズムは、次の方法でそれを行うことです:
1. 1 つを削除し、
2. 必要に応じてツリーを修正します。

Answer 1

半分以上のノードが削除されている場合は、挿入と削除のコストが同じであるため、既存のツリーを破棄して新しいツリーを短時間で構築できます。

Answer 2

複数のノードの削除を行っている間、ツリーのバランスを保つ必要があるという制約がない場合、複数のノードの削除を行った後にツリーを修正できるのは妥当だと思います。

各削除後にツリーのバランスを取る目的は、削除操作の計算コストが一貫していることを確認することです。この方法で削除の一貫性を保つ必要がない場合は、削除アルゴリズムを別の方法で記述できます。ただし、修正操作は、1 回の削除よりも長い計算になります。また、より複雑なものになる可能性もあります。

Answer 3

TeardownTreeと呼ばれるデータ構造に興味があるかもしれません。時間delete_range内に機能する操作をサポートします。ここで、 はツリー内のアイテムの初期数であり、は削除された (そして呼び出し元に返された) アイテムの数です。完全な開示：私は著者です。O(k + log n)nk

データ構造は操作をサポートしていませんが、 および 用に最適化されていることを強調する必要がありinsertます。アルゴリズムの非公式な説明を書き上げました。すべての最適化により、コードはそのドキュメントとは大幅に異なりますが、アイデアを理解するには十分なはずです。clonedelete_range

Answer 4

Treap v/sa Red-Black ツリーを使用すると、さまざまなシナリオでツリーのバランスを取る方が簡単に見えるため、Red-Black ツリーの代わりに Treap を使用することをお勧めします。私はあなたと同じ問題を抱えていますが、Treaps についてです。https://cstheory.stackexchange.com/questions/20495/algorithm-to-bulk-delete-nodes-from-a-treap

予想される高さの境界が一括削除後も有効であるかどうかは不明です（アルゴリズムは質問に記載されています）。

Answer 5

この問題を解決する方法は、削除するノードのリンク リストを作成し、それらに対して標準の削除方法を連続して使用することでした。一括削除のためのより良いアルゴリズムがあるかどうか知りたいです。