6

私は現在、アプリケーションのいくつかの最適化を実行するために赤黒木データ構造を実装しています。

私のアプリケーションでは、特定の時点で、特定の値以下のすべての要素（要素は整数であると見なすことができます）をツリーから削除する必要があります。

要素を1つずつ削除することもできますが、もっと速くしたいのですが。したがって、私の質問は、赤黒木のサブツリー全体を削除した場合、高さと色の不変量を回復するためにツリーを修正するにはどうすればよいですか？

4

3 に答える 3

8

赤黒木から1つの要素を削除すると、O（log n）時間がかかります。ここで、nは現在ツリーにある要素の数です。

少数の要素のみを削除する場合は、要素を1つずつ削除するのが最善であり、最終的にはO（k log n）操作になります（k =削除された要素、n =削除前のツリー内の要素）。

ただし、多数のノード（たとえば、ツリーの50％以上）を削除することがわかっている場合は、保持する要素を反復処理することをお勧めします（O（k'）操作（k' =要素）何が保持されるか）、次にツリーをスクラップし（メモリ管理スキームに応じてO（1）またはO（n））、ツリー（O（k'log k'））操作を再構築します。全体の複雑さはO（k'）+ O（k' log k'）= O（k' log k'）であり、k' <kの場合は明らかにO（k log n）よりも小さくなります（50未満を維持します）。ツリーの％）。

とにかく、ほとんどの要素を削除するときは、保持したい要素を列挙してからツリーを再構築する方が実際には良いというのがポイントです。

于 2011-04-14T15:36:52.507 に答える
7

編集：以下は一般的なサブツリーの削除用です。必要なのは、Split（実際の質問の内容に基づいて）1回の操作だけです。

最悪の場合、赤黒木のサブツリー全体を削除することができO(log n)ます。

赤黒木の操作は時間内に実行できることSplitが知られています。JoinO(log n)

分割：値kと赤黒木Tが与えられた場合、T1<kのすべての値とT2>=kのすべての値になるように、Tを2つの赤黒木T1とT2に分割します。

結合：2つの赤黒木T1とT2を1つの赤黒木Tに結合します。T1とT2は、T1の最大値<=T2の最小値（または略してT1 <= T2）を満たします。

必要なのは2Splitsつと1つJoinです。

あなたの場合、削除する必要のあるサブツリーは、値の範囲に対応しますL <= v <= U。

したがって、最初SplitにLを使用して、T1<=T2でT1とT2を取得します。SplitU上のT2は、T3<=T4でT3とT4を取得します。今Join、木T1とT4。

pseudoCodeでは、コードは次のようになります。

Tree DeleteSubTree( Tree tree, Tree subTree) {

    Key L = subTree.Min();
    Key U = subTree.Max();

    Pair <Tree> splitOnL = tree.Split(L);
    Pair <Tree> splitOnU = splitOnL.Right.Split(U);

    Tree newTree = splitOnL.Left.Join(splitOnU.Right);

    return newTree;
}

詳細については、こちらをご覧ください：https ://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

于 2011-04-14T19:02:02.837 に答える
2

赤黒木からの一括削除は、黒の高さの不変条件がかなりひどく台無しになるため、困難です。あなたが（ソフトな）リアルタイムをやっていないと仮定すると、私は1つずつ削除するか（1つずつ挿入する必要があるため、ここではより小さな定数係数について話します）、スプレーツリーに切り替えます。 。

于 2011-04-14T15:08:22.277 に答える