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 и А принадлежат к одному набору, неважно, что такое ели t, это может быть D или это может быть A. Аналогично, потому что B и C принадлежат к одному и тому же набору, не имеет значения, что такое второй аргумент, он может быть B или может быть C, результат будет таким же.

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

D 
/\ 
A B 
     \ 
     C 

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

D 
    /|\ 
A B C 

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

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

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

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