誰かが素集合データ構造とは何かを説明できますか？あるいは、それをうまく説明しているYouTubeビデオまたは記事に私をリンクできますか？
数分前に検索したところ、ベン図のような画像を使った数学のレッスンしか受けられませんでした。たぶんそれだけですが、よくわかりませんので、よろしくお願いします。
簡単に言うと、「バイナリツリーを使用して二項キュー内の各二項ツリーを表す方法」と尋ねられたとき、これは互いに積み重ねる必要のある二項ツリーを指します。B1がB1に接続してB2になるように、2つのB2がB3になり、以下同様に続きます。
互いに素な集合データ構造は、集合Sの分割を表すためのデータ構造です。まず、それぞれが独自のグループに属する要素の集合Sから始めます。例えば：
{1} {2} {3} {4} {5} {6}
素集合データ構造に対する1つの演算は、与えられた要素を含む2つの集合を結合する和集合演算です。たとえば、1と2を結合すると、パーティションが返されます。
{1, 2} {3} {4} {5} {6}
3と5を結合すると
{1, 2}, {3, 5}, {4}, {6}
ここで、1と3を結合すると、パーティションが生成されます
{1, 2, 3, 5}, {4}, {6}
検索操作は、特定の要素がどのセットに属しているかを示します。通常、これは、findが属する要素の代表的な要素を返すことによって行われます。これは通常、次のように行われます。
find(x) == find(y) if and only if x and y are in the same set.
たとえば、find（1）は2を返す可能性があるため、find（2）= 2、find（3）= 2、find（5）=2です。
素集合データ構造は、クラスカルの最小スパニングツリーアルゴリズムのサブルーチンとしてよく使用されます。これは、グラフ内の2つのノードが接続されているかどうかを非常に高速にチェックし、2つの接続されたコンポーネントのすべてのノードが接続されていることを簡単にマークできるためです。エッジが追加されると互いに。ランクごとの和集合とパス圧縮を使用した素集合フォレストの実装を使用すると、素集合フォレストでのn回の演算をO（nα（n））時間で実行できます。ここで、α（n）は逆アッカーマン関数です。非常にゆっくりと成長する関数は、事実上一定です（ユニバースのサイズよりも小さい入力の場合、最大で4つです）。
二項木と二分木について：あなたが求めているのは、多くても2つの子を持つ二分木を使用して、多方向の木である二項木をどのように表現するかということだと思います。すべての二項ツリーが二分木であるとは限らないため、適切なエンコーディングを使用する必要があります。
これを行う1つの方法は、左子右兄弟表現と呼ばれるものを使用することです。これは、次の設定に従って、多分木を二分木として表します。
たとえば、次の二項ツリーがあるとします。
a
/ | \
b c d
/| |
e f g
|
h
左子右兄弟表現は次のようになります
a
/
b
/ \
e c
\ / \
f g d
/
h
ちなみに、これを二項ツリーで行うと、二項ツリーは、次のプロパティを持つ二分ツリーである、半順序半ツリーと呼ばれるものとして表現されることになります。
これらの定義は、二項ツリーがヒープ順に並べられてから、左子の右兄弟表現に変換されるという事実に基づいています。この表現を使用すると、二項ツリーにリンクするのが非常に高速になります。それは読者の練習問題として残しておきます。:-)
お役に立てれば！
素集合は基本的にunion-findデータ構造です。
元々はnノードのセットがあり、それに対する操作がfind(node)ありunion(node1,node2)ます。
union(node1,node2)ノードを1つのセットに「結合」することですfind(node)のカノニック表現を見つけることですnode（たとえば、後で説明するように、ルートを与えることによって）たとえば、元々はを持っていて、次の{1},{2},{3},{4},{5}ようにします。
union(1,2)
union(3,4)
その後、あなたは持っていることになり{1,2},{3,4},{5}ます。
これは、この時点でfind(1) == find(2)（同じセットです！）も意味します。
後で-2を含むセットと3を含むセットunion(2,3)を結合することになり、最終的には{1,2,3,4},{5}
ビデオリクエストについて：バークレーからのこの講義は、資料をかなりうまくカバーしているようです。
二分木に関しては、これは実装の1つの方法であり、各「ルート」には息子がいますが、ツリーは実際には「逆さま」であり、父親から息子へのポインターではなく、息子から父親へのポインターがあります。
このように、各ノードの標準表現は、ノードがつながるルートであり、これにより、同じルートを持っているため、ユニオンaを実行した場合に、が確実になります。bfind(a) = find(b)
このDSが何であるかについてのいくつかの手がかりが得られることを願っています。
幸運を！
私が大学で学んだ互いに素な集合は、3つの重要な機能を中心に展開しました。
make_set(x) - makes a new disjoint contains only the element x
find_set(x) - gives you the set that contains element x
union(x,y) - unions the sets that contain x and y
彼らが言及した実装は、リンクリストを使用したものでした。つまり、各セットには、セットを作成した要素の代表が含まれています。（make_set(x)）次に、を使用するとunions(x,y)、の終了ポインタがxを指すように移動しyます。Union速いですが、make_setこれはかなり遅かったですfind_set（実際にはO（最大のセット））
より良い実装では、パス圧縮と呼ばれる2つのメソッドを使用しました。これは、要素がwithunionおよび/またはfind_setで渡されたため、セットの代表を指すようになりました。
もう1つのランクごとのユニオンは、セットの最大の「深さ」を与える各セットのランクを維持しました。結合すると、各セットのランクが同じである場合、ランクに1つ追加され、一方の代表がもう一方を指すように変更されました。それらが異なる場合は、小さい方のセットが大きい方の代表を指すように変更され、ランクは変更されません。この漸近的な上限は、関数の使用回数に非常に近いものです。
お役に立てば幸いです。