merge - 素集合の和集合

Question

Union の機能をサポートするばらばらのセットを検討しています。

木の高さを減らすテクニック：

常に小さいツリーを大きいツリーにマージします。つまり、小さいツリーのルートが大きいツリーのルートを指すようにします。

より多くのノードがある場合、ツリーは他のツリーよりも大きくなります。

各ノードは、フィールドを持つ構造体です。要素に関する情報、親ノードへのポインタ「親」、およびノー​​ドがルートである場合にのみ使用され、ノードの数を含むカウンター「カウント」です。アップツリー。

次のアルゴリズムは、2 つのアップ ツリーをマージします。

pointer UpTreeUnion(pointer S,T) {
   if (S == NULL OR P == NULL) return;
   if (S->count >= T->count) {
       S->count = S->count + T->count;
       T->parent = S;
       return S;
   }
   else {
       T->count = T->count + S->count;
       S->parent = T;
       return T;
   }
}

最大で k 個の素集合が存在する可能性がある、和集合を使用した素集合の実装を考えてみましょう。この実装では、ハッシュ テーブル A[0.. max-1] を使用します。このテーブルには、順序付けられた二重ハッシュ法に基づいてキーが格納されます。h1 と h2 をそれぞれ 1 次ハッシュ関数と 2 次ハッシュ関数とします。A には、上記のすべてのツリーのノードのキーと、それぞれに対応するノードへのポインターが含まれています。パラメータとして 2 つのノードのキーを取り、ノードが属するアップ ツリーをマージするアルゴリズムを書きたいです (ノードは任意のアップ ツリーに属することができますが、同時にその場合は適切なメッセージが表示されます)。 . 合流時には、パスの圧縮と高さの削減の手法を適用する必要があります。

どうすればこれを行うことができるか、ヒントを教えていただけますか?

次の配列があるとします。

最初は、ノードは次のようになります。

次に、k1=100、k2=5 の場合、アルゴリズムを適用した後、これが得られるでしょうか?

次に、k1=59、k2=5 の場合、次のようになります。

右？次に、パス圧縮を適用して、これを開始します。

tmp=B
while (B->parent!=B)
      parent=B->parent;
      tmp->parent=B;
      tmp=parent;
}

したがって、parent=F、tmp->parent=B、tmp=F となります。

どうやって続けますか？

k1=14、k2=59 とすると、次のようになります。

Answer 1

まず、キーを取得したら、ハッシュ テーブルでキーを見つける必要があります。
ハッシュ テーブルにはエントリが含まれています: (key, pointer-to-node).
key を見つけたいとしましょうk。チェックします:
A[h1(k) + 0*h2(k) mod size(A)]- key が含まれている場合はk、対応するノードへのポインターを読み取ります。
以外のものがある場合は、 、、... が見つかるまでkチェックします。
A[h1(k) + 1*h2(k) mod size(A)]
A[h1(k) + 2*h2(k) mod size(A)]
A[h1(k) + i*h2(k) mod size(A)]k

2 つのノードへのポインターを取得したので、それらのノードが属するツリーのルートを見つける必要があります。ルートを見つけるには、ルート ノードに到達するまでツリーを上ります。各ノードのポインターを使用し、たとえばルートのポインターがそれ自体を指してparentいると想定できます。parent

2 つのルートができたので、 を使用してそれらをマージできますupTreeUnion。

パス圧縮は次のように機能します。

node のツリーのルートを見つけたら、 からルートへsのパスをsもう一度たどり、パスparent上のすべてのノードのポインターをルートに設定します。

アップデート：

Algorithm(k1,k2){
   int i=0,j=0;
   int i1,i2;
   while (i<max and A[i1 = h1(k1)+i*h2(k1) mod size(A)]->key!=k1){
          i++;
   }
   while (j<max and A[i2 = h1(k2)+j*h2(k2) mod size(A)]->key!=k2){
          j++;
   }
   if (A[i1]->key!=k1) return;
   if (A[i2]->key!=k2) return;

   pointer node1,node2,root1,root2;
   node1=A[i1]->node;
   node2=A[i2]->node;
   root1=UpTreeFind(node1);
   root2=UpTreeFind(node2);
   if (root1==root2){
      printf("The nodes belong to the same up tree");
      return;
   }

   // path compression
   pointer tmp,tmpParent;

   tmp = node1;
   while (tmp->parent!=root1) {
       tmpParent=tmp->parent;
       tmp->parent=root1;
       tmp=tmpParent;
   }

   tmp = node2;
   while (tmp->parent!=root2) {
       tmpParent=tmp->parent;
       tmp->parent=root2;
       tmp=tmpParent;
   }

   UpTreeUnion(root1,root2);
}