Леса с непересекающимися множествами - почему ранг должен быть увеличен на единицу, если находка двух узлов одного ранга?
Я реализую структуру данных с несвязным множеством, чтобы найти объединение. Я наткнулся на следующее утверждение в Википедии:
... если два дерева одного ранга r объединены, ранг результата равен r+1.
Почему ранг соединенного дерева должен быть увеличен только на один, если деревья одного ранга? Что произойдет, если я просто добавлю два ранга (т.е. 2*r)?
4 ответа
Потому что в этом случае - вы добавляете одно дерево как "поддерево" другого - что заставляет исходное поддерево увеличивать его размер.
Посмотрите на следующий пример:
1 3
| |
2 4
В приведенном выше "ранг" каждого дерева равен 2.
Теперь предположим, что 1 будет новым унифицированным корнем, вы получите следующее дерево:
1
/ \
/ \
3 2
|
4
после объединения ранг "1" равен 3, rank_old(1) + 1 - как и ожидалось.1
Что касается вашего второго вопроса, потому что он даст ложную высоту для деревьев.
Если мы возьмем приведенный выше пример и объединим деревья, чтобы получить дерево ранга 3. Что произойдет, если мы затем захотим объединить его с этим деревом2:
9
/ \
10 11
|
13
|
14
Мы обнаружим, что оба ранга равны 4, и попробуем объединить их так же, как мы делали это раньше, не отдавая предпочтение "более короткому" дереву, что приведет к деревьям с более высокой высотой и, в конечном итоге, к ухудшению временной сложности.
(1) Отказ от ответственности: первая часть этого ответа взята из моего ответа на аналогичный вопрос (хотя и не совпадает с вашей последней частью вопроса)
(2) Обратите внимание, что вышеприведенное дерево создано синтетически, оно не может быть создано в алгоритмах оптимизированных непересекающихся лесов, но оно все же демонстрирует проблемы, необходимые для ответа.
Во-первых, что такое ранг? Это почти так же, как высота дерева. На самом деле, пока притворитесь, что он такой же, как высота.
Мы хотим, чтобы деревья были короткими, поэтому отслеживание высоты каждого дерева помогает нам в этом. При объединении двух деревьев разной высоты мы делаем корень более короткого дерева дочерним по отношению к корню более высокого дерева. Важно отметить, что это не меняет высоту более высокого дерева. То есть ранг более высокого дерева не меняется.
Однако при объединении двух деревьев одинаковой высоты мы делаем один корень дочерним для другого, и это увеличивает высоту этого общего дерева на единицу, поэтому мы увеличиваем ранг этого корня на единицу.
Теперь я сказал, что ранг был почти таким же, как высота дерева. Почему почти? Из-за сжатия пути, второй метод, используемый структурой данных union-find для сохранения деревьев коротким. Сжатие пути может изменить существующее дерево, чтобы сделать его короче, чем указано его рангом. В принципе, может быть лучше принимать решения, основываясь на фактической высоте, чем использовать ранг в качестве прокси для высоты, но на практике слишком сложно / слишком медленно отслеживать истинную информацию о высоте, тогда как это очень легко / быстро отслеживать ранг.
Вы также спросили: "Что произойдет, если я просто добавлю два ранга (т.е. 2*r)?" Это интересный вопрос. Ответ, вероятно, ничего не значит, что все будет работать нормально, с той же эффективностью, что и раньше. (Ну, при условии, что вы используете 1 в качестве начального ранга, а не 0.) Почему? Поскольку используется способ ранга, важен относительный порядок рангов, а не их абсолютные величины. Если вы добавите их, то ваши ранги будут 1,2,4,8 вместо 1,2,3,4 (или, более вероятно, 0,1,2,3), но они все равно будут иметь точно такой же относительный порядок, поэтому все хорошо. Ваш ранг просто 2^(старый ранг). Самая большая опасность состоит в том, что вы рискуете переполнить целое число, используемое для представления ранга при работе с очень большими наборами (или, другими словами, вам потребуется больше места для хранения рангов).
С другой стороны, обратите внимание, что, добавляя два ранга, вы приближаете размер деревьев, а не их высоту. Всегда добавляя два ранга, независимо от того, равны они или нет, вы точно отслеживаете размеры деревьев. Опять же, все работает просто отлично, с теми же предостережениями о возможности переполнения целых чисел, если ваши деревья очень большие.
На самом деле, объединение по размерам широко признано в качестве законной альтернативы объединению по рангу. Для некоторых приложений вы на самом деле хотите знать размеры наборов, а для этих приложений объединение по размеру фактически предпочтительнее объединения по рангу.
Если вы прочтете этот абзац немного глубже, вы поймете, что rank больше похоже на глубину, а не на размер:
Поскольку именно глубина дерева влияет на время выполнения, дерево с меньшей глубиной добавляется под корень более глубокого дерева, что увеличивает глубину только в том случае, если глубины равны. В контексте этого алгоритма термин "ранг" используется вместо "глубина" ...
и слияние деревьев равной глубины только увеличивает глубину дерева на единицу, поскольку корень одного добавляется к корню другого.
Рассматривать:
A D
/ \ merged with / \
B C E F
является:
A
/|\
B C D
/ \
E F
Глубина была 2 для обоих, и это 3 для объединенного.
Ранг представляет глубину дерева, а не количество узлов в нем. Когда вы соединяете дерево с меньшим рангом с деревом с большим рангом, общий ранг остается прежним.
Рассмотрите возможность добавления дерева с рангом 4 к корню дерева с рангом 6: поскольку мы добавили узел выше корня дерева глубины 4, это поддерево теперь имеет ранг 5. Поддерево, к которому мы добавили Дерево глубины 4, однако, равно 6, поэтому ранг не меняется.
Теперь рассмотрим добавление дерева с рангом 6 к корню второго дерева с рангом 6: поскольку корень первого дерева глубины 6 теперь имеет дополнительный узел над ним, ранг этого поддерева (и дерева в целом) изменяется на 7.
Поскольку ранг дерева определяет скорость обработки, алгоритм старается поддерживать ранг как можно ниже, всегда прикрепляя более короткое дерево к более высокому, оставляя общий ранг неизменным. Ранг изменяется только тогда, когда деревья имеют одинаковые ранги, и в этом случае одно из них привязывается к корню другого, увеличивая ранг на единицу.
На самом деле, здесь нам следует очень хорошо знать два важных свойства....
1) Что такое ранг? 2) Почему используется ранг???
Ранг - это не что иное, как глубина дерева. Вы можете сказать ранг как глубину (уровень) дерева. Когда мы создаем объединяемые узлы, эти (узлы графа) будут сформированы как дерево с конечным корневым узлом. Ранг выражается только для этих корневых узлов.
A merged with D
Первоначально A имеет ранг (уровень) 0, а D имеет ранг (уровень) 0 . Таким образом, вы можете объединить их, сделав любого из них корневым. Потому что, если вы сделаете A как корень, ранг (уровень) будет 1, и если вы сделаете D как корень, то ранг также будет 1
A
`D
Здесь ранг (уровень) равен 1, когда корень равен A.
Теперь подумай о другом,
A merge B -----> A
`D `C / \
D B
\
C
Таким образом, уровень будет увеличен на 1, смотрите точно без корня (A) максимум высота / глубина / ранг 2 . ранг [ 1] -> {D,B} и ранг [2] -> {C} ................
Теперь наша основная задача - сделать дерево с минимально возможным рангом (глубиной) при слиянии..
Теперь, когда сливаются два разных ранговых дерева, тогда
A(rank 0) merge B(rank 1)---> B Here merged tree rank is 1 same as high rank (1)
`C / \
A C
Когда маленький ранг переходит в высокий ранг. Тогда ранг объединенного дерева (высота / глубина) будет таким же, как и ранг, связанный с деревом более высокого ранга. Это означает, что ранг не будет увеличиваться, ранг объединенного дерева будет таким же, как ранг более высокого ранга до...
Но если мы проделаем обратную работу, то есть дерево высокого ранга уходит под дерево низкого ранга, тогда увидим,
A ( rank 0 ) merge B (rank 1 ) --> A ( merged tree rank 2 greater than both )
`C `B
`C
Итак, из следующего наблюдения видно, что если мы попытаемся сохранить ранг (высоту) объединенного дерева на минимально возможном уровне, тогда мы должны выбрать первый процесс. я думаю, что эта часть ясна!!
Теперь вы должны понять, какова наша цель - сохранить минимальную высоту дерева..........
когда мы используем объединение непересекающихся множеств, то для сжатия пути (нахождение конечного корня, с которым связан узел), когда мы переходим от узла к его корневому узлу, тогда, если его высота (ранг) длинная, обработка времени будет медленной. Вот почему, когда мы пытаемся объединить два дерева, а затем стараемся сохранить как можно минимум высоту / глубину / ранг