Несвязанные множества структур данных и биномиальных деревьев?

Question

Может ли кто-нибудь объяснить, что такое структура данных Disjoint Sets, или, в качестве альтернативы, связать меня с видео YouTube или статьей, которая это хорошо объясняет.

Я искал его несколько минут назад, и все, что я получил, было несколько уроков по математике с изображением, похожим на диаграмму Венна. Может быть, это так, но я не уверен, поэтому любая помощь приветствуется.

Вкратце отметим, что когда меня спрашивают "Как использовать двоичное дерево для представления каждого биномиального дерева в биномиальной очереди", относится ли это к биномиальным деревьям, которые вы должны накладывать друг на друга. Как B1 присоединяется с B1, чтобы стать B2, то два B2 становятся B3, и так далее, и так далее.

Answer 1

Несвязанные структуры данных набора являются структурами данных для представления раздела набора S. Вы начинаете с набора элементов S, каждый из которых принадлежит своей собственной группе. Например:

{1} {2} {3} {4} {5} {6}

Одной операцией над структурой данных с несвязным множеством является операция объединения, которая объединяет два набора, содержащих заданные элементы. Например, объединение 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.

Несвязанные структуры данных часто используются в качестве подпрограммы в алгоритме минимального связующего дерева Крускала, поскольку они обеспечивают очень быстрый способ проверки того, соединены ли два узла в графе, и простой способ пометить, что все узлы в двух соединенных компонентах связаны с друг друга, когда добавляется ребро. Используя реализацию леса с несвязным множеством с объединением по рангу и сжатием пути, n операций над лесом с несвязным множеством можно выполнить за время O(n α(n)), где α (n) - обратная функция Аккермана, функция, которая растет настолько медленно, что фактически является константой (это максимум четыре для любого входа, меньшего, чем размер вселенной).

---

Что касается биномиальных деревьев и бинарных деревьев: я думаю, что вы спрашиваете о том, как представлять биномиальные деревья, которые являются многогранными деревьями, с использованием бинарных деревьев, которые имеют не более двух дочерних элементов. Не все биномиальные деревья являются бинарными деревьями, поэтому необходимо использовать подходящую кодировку.

Один из способов сделать это - использовать то, что называется представлением правого брата левого ребенка. Это представляет многогранное дерево в виде двоичного дерева согласно следующей настройке:

• Левый дочерний элемент каждого узла указывает на первого дочернего узла.
• Правый потомок каждого узла указывает на своего следующего брата (узел в том же слое с тем же родителем).

Например, учитывая это биномиальное дерево:

     a
   / | \
  b  c  d
 /|  |
e f  g
  |
  h

Представление правообладателя левого ребенка будет

                 a
                /
               b
            /    \
           e      c
            \    / \
             f  g   d
            /
           h   

Кстати, если вы сделаете это на биномиальных деревьях, вы получите представление о биномиальном дереве как о так называемом полуупорядоченном полудереве, представляющем собой бинарное дерево со следующими свойствами:

• Каждый узел в дереве больше или равен (или меньше или равен, в зависимости от того, является ли это минимальной кучей или максимальной кучей) каждого узла в его левом поддереве.
• Корневой узел не имеет правого потомка.

Эти определения следуют из того факта, что биномиальное дерево упорядочено в куче, а затем преобразуется в представление левого и правого братьев и сестер. Используя это представление, очень быстро связать вместе с биномиальными деревьями. Я оставлю это в качестве упражнения для читателя.:-)

Надеюсь это поможет!

Answer 2

Непересекающиеся множества, которые я изучал в универе, вращались вокруг трех основных функций.

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(самый большой набор))

В лучшей реализации использовались два метода, называемые сжатием пути, которые в качестве элемента передавались с помощью union и / или find_set, он указал на представителя набора

Другой, объединяющий по рангу, который поддерживал ранг для каждого набора, который дал наибольшую "глубину" набора. При объединении, если ранг каждого набора был одинаковым, он добавлял один к рангу, и один представитель изменялся, чтобы указывать на другой. Если они отличались, то меньший набор был изменен, чтобы указать на представителя большего, и ранг остался без изменений. Эта асимптотическая верхняя граница действительно близка к количеству использований функций.

Надеюсь, это поможет.

Answer 3

Несвязное множество - это в основном структура данных с поиском объединения.

У вас изначально есть набор n узлы, и у вас есть find(node) а также union(node1,node2) операции на нем.

• union(node1,node2) делает "объединение" узлов, чтобы быть в одном наборе
• find(node) находит каноническое представление node (путем предоставления рута, например, как будет объяснено позже)

Например, у вас изначально есть {1},{2},{3},{4},{5} и вы делаете:

union(1,2)
union(3,4)

Тогда вы в конечном итоге {1,2},{3,4},{5},
Это также означает, что на данный момент find(1) == find(2) (Это тот же набор!)

Если ты позже union(2,3) - это приведет к объединению набора, содержащего 2, с набором, содержащим 3, и вы получите {1,2,3,4},{5}

Относительно видео-запроса: эта лекция из Беркли, кажется, покрывает материал довольно хорошо.

---

Что касается бинарных деревьев - это один из способов реализации, у каждого "корня" есть свои сыновья, но дерево на самом деле "вверх ногами", вместо указателей от отца к сыновьям, у вас есть указатели от сыновей к отцу.
Таким образом, каноническое представление каждого узла является корнем, к которому ведет узел, и это гарантирует нам, что если бы мы сделали объединение на a а также b - затем find(a) = find(b) потому что они имеют одинаковый корень.

Я надеюсь, что это даст вам некоторые сведения о том, что это за DS.
Удачи!