c++ - ポインターの変化を追跡する

Question

私は正常に動作している赤黒木アルゴリズムを持っています。ノードがツリーに挿入されると、insert() メソッドは、挿入されたノードへのポインターを呼び出し元に返します。そのようなすべてのポインターを STL ベクトルに格納します。

問題は、RB ツリーの操作内で、これらのポインターが無効になる場合があることです。たとえば、ノード A の値を現在のノードにコピーしてからノード A を削除する、rotateleft/right 中に呼び出されるメソッドがあります。そのベクトルにノード A へのポインターがありましたが、これは現在無効です。

次のようにベクター内のポインターを更新する方法を考えました。

1) ノード ポインタをそれらのポインタを保持するベクトル インデックスにマップするマルチマップを保持します。

2) ノードを削除する前に、このマルチマップをチェックして、影響を受けるベクトル内のすべてのスポットを見つけます

3) ベクトルを反復処理し、古いポインターを新しいポインターに変更します。

4) マルチマップのキー値を更新して、新しいポインタも反映させます。

問題は、明らかな理由でマップ コレクションのキー値を更新できないことです。また、これは複雑さと実装の両方の理由から、恐ろしい解決策のようです。このポインターの動的更新をどのように達成できるかについてのアイデアはありますか?

Answer 1

これがまさにあなたがやろうとしていることかどうかはわかりませんが、ツリー/ヒープデータ構造に追加されたアイテムを追跡するために、過去に次のことがうまくいきました:

基になるツリー データに加えて、2 つの「インデックス」ベクトルを格納します。

std::vector<int> item_to_tree;
std::vector<int> tree_to_item;

したがって、i 番目のアイテムのツリーでインデックスを見つけるには、 を使用しますitem_to_tree[i]。特定の j 番目のツリー インデックスでアイテムを検索するには、 を使用しますtree_to_item[j]。これは、これまで行ってきたように明示的なポインターを格納するのと似ていますが、インデックスを利用することで、基本的に O(1) ルックアップで双方向マップを取得できます。

明らかに、ツリー操作内では、マッピングが一貫していることを確認する必要があります。RB ツリーについては考えたことはありませんが、他のツリーのような構造の場合、これは各操作に O(1) の複雑さを追加するだけです。

ツリーから「削除」された i 番目のアイテムの場合、tree_to_itemi 番目のアイテム インデックスが含まれなくなり、通常は item_to_tree[i] = -1、または何らかの「空」フラグを設定します。

お役に立てれば。

Answer 2

ノードが指す不透明なデータ構造にデータを保持し、ノードの代わりにこの構造への外部ポインターを保持する方が合理的です。

基本的には、ツリーと実際のデータの間に一定レベルの間接性を追加することを意味します。