Что такое «ранг» в объединении по алгоритму сжатия ранга и пути?

Question

у меня есть понимание алгоритма таким образом ...

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

• Мы решаем, какой из двух является родительским узлом (во время операции объединения), смотрящим на ранг.

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

Answer 1

Параграф в https://en.wikipedia.org/wiki/Disjoint-set_data_structure, начинающийся с «Первый способ, называемый объединением по рангу, состоит в том, чтобы всегда прикреплять меньшее дерево к корню большего дерева» показывает, что даже без сжатия пути объединение по рангу является достаточно хорошим, чтобы уменьшить стоимость операции соединения в худшем случае O (log n).

Он также объясняет, что без сжатия пути ранг отражает максимальную глубину дерева, созданного до сих пор, что объясняет, почему это только увеличивается, если ранжицы одинаковы - поскольку меньшее дерево добавляется в корень большее дерево, это единственный случай, когда максимальная глубина фактически увеличивается.