Union-Find операции на дереве?

Question

Может кто-нибудь, пожалуйста, объясните ответ жирным шрифтом? Как это сделано?

Ниже приведена последовательность из четырех операций Union-Find (с взвешенным объединением и полным сжатием), которые привели к следующему восходящему дереву. Какие были последние две операции?

Ответ: Союз (D,A), Союз (B,C), Союз (D/A,B/C), Найти (B/C).

Answer 1

Обозначение используется из-за множеств.

Давайте применим четыре операции:

Union(D,A) приводит к следующему дереву:

   D
  /
 A

Union(B,C) приводит к следующему дереву:

   B
  /
 C

Сейчас Union(D/A,B/C) означает, что, поскольку D и A принадлежат одному и тому же набору, не имеет значения, что является первым аргументом, это может быть D или это может быть A, Точно так же, поскольку B и C принадлежат одному и тому же набору, не имеет значения, что является вторым аргументом, это может быть B или это может быть C, результат будет таким же.

Результат будет после третьей операции:

   D
  / \
 A   B
      \
       C

Теперь, поскольку сжатие также разрешено, Find(C) операция приведет к созданию дерева:

   D
  /|\ 
 A B C

Если четвертая операция Find(B)дерево останется прежним, потому что когда мы применяем сжатие после операции поиска, мы делаем все узлы, найденные на пути, непосредственным дочерним элементом корня корня, но так как мы не встретимся Cмы не сможем сделать C непосредственный ребенок D, как это в конечном дереве.

Правильный ответ

Правильная последовательность четырех операций:

Union(D,A), Union(B,C), Union(D/A,B/C),Find(C).