Поиск объединения - почему мы проверяем размер для взвешенного быстрого объединения

#algorithm #data-structures #tree #union-find

#алгоритм #структуры данных #дерево #объединение-поиск

Вопрос:

Я проходил курс алгоритмов Принстона на Coursera.

В разделе поиска объединения для взвешенного быстрого объединения мы объединяем деревья в зависимости от того, какое дерево меньше по размеру.

Однако я не понимаю, почему мы используем размер, а не глубину, чтобы решить, какое дерево больше, а какое меньше.

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

В приведенном выше примере, если мы объединим 2 дерева, проверив размер, глубина результирующего дерева равна 4, тогда как при проверке по глубине мы получаем меньшую результирующую глубину дерева.

Ответ №1:

Очень часто для взвешивания используется «ранг» вместо размера. Высота не используется, потому что высота дерева может быть изменена путем сжатия пути способами, которые трудно отследить. Ранг дерева — это то, какой была бы высота, если бы сжатие пути не использовалось.

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

1. Я не понимаю, как они могут быть одинаковой сложности по времени. Разве мы не пытаемся сократить время нахождения корня, избегая высоких деревьев. Как я объяснил на изображении выше, объединение по размеру приводит к более высоким деревьям. Более того, размер здесь ни на что не влияет. У нас могли бы быть деревья размером 1000, но глубиной 2, которые имели бы очень хорошую временную сложность.

2. Не существует последовательности операций объединения по размеру, которые могли бы привести к вашему примеру цепочки из 3. «Высоких деревьев» не будет