Disjoint Set особым образом?

Question

Мы реализуем структуру несвязанных данных с деревом. в этой структуре данных makeset() создать набор с одним элементом, merge(i, j) объединить два дерева набора i и j таким образом, чтобы дерево с более низкой высотой стало потомком корня второго дерева. если мы делаем nmakeset() операции и n-1 merge() операции случайным образом, а затем выполните операцию поиска. какова стоимость этой операции поиска в худшем случае?

I) O(n) 
II) O(1) 
III) O(n log n) 
IV) O(log n) 

Ответ: IV.

Любой мог бы упомянуть хорошие советы, которые автор получил от этого решения?

Answer 1

The O (журнал N) найти только справедливо, когда вы используете союз ранга (также известный как взвешенный союз). Когда мы используем эту оптимизацию, мы всегда ставим дерево с более низким рангом под корень дерева с более высоким рангом. Если оба имеют одинаковый ранг, мы выбираем произвольно, но увеличиваем ранг полученного дерева на единицу. Это дает оценку O (log n) на глубине дерева. Мы можем доказать это, показывая, что узел, который является I уровни ниже корня (что эквивалентно, чтобы быть в дереве ранга> = я) находится в дереве, по крайней мере, 2 ^я узлов (это так же, как показано дерево размером n имеет журнал n глубина). Это легко сделать с индукцией.

Induction hypothesis: tree size is >= 2^j for j < i. 
Case i == 0: the node is the root, size is 1 = 2^0. 
Case i + 1: the length of a path is i + 1 if it was i and the tree was then placed underneath 
      another tree. By the induction hypothesis, it was in a tree of size >= 2^i at 
      that time. It is being placed under another tree, which by our merge rules means 
      it has at least rank i as well, and therefore also had >= 2^i nodes. The new tree 
      therefor has >= 2^i + 2^i = 2^(i + 1) nodes.