Я пытаюсь реализовать структуру данных Union-Find / Disjoint-Set в C, используя взвешенное Union и сжатие пути в Find.У меня есть несколько вопросов относительно того, как следует внедрить взвешенное объединение, чтобы уменьшить сложность времени по сравнению с невзвешенным объединением.
Я уже нашел несколько решений этой проблемы в Интернете и реализовал свое собственное.В каждом решении корень каждого отдельного дерева (представляющего множество) всегда содержит количество узлов дерева.При объединении наборов двух случайных объектов, принадлежащих к другому набору, сначала определяются корни (здесь используется сжатие путей), а затем мы сравниваем размеры этих корней.Корень самого большого дерева устанавливается как родитель корня самого маленького дерева.
Однако, в моем понимании, мы пытаемся достичь с помощью взвешенного объединения, чтобы уменьшить высоту результирующегодерево (что мы также пытаемся достичь с помощью сжатия пути).Следовательно, не дерево с наименьшим числом узлов должно быть подключено к другому дереву, а дерево с наименьшей высотой.Это удерживает высоту до минимума.
Это правильно?Проверяет ли высота и размер как-то эквивалентно с учетом остальной части реализации (мы всегда начинаем с количества одиночных наборов (одного узла))?
Предположим, что нужно проверять высоту, сохраняяОтслеживание высоты дерева, если сжатие пути не используется, довольно просто.Однако я не нашел способа отслеживать высоту дерева при использовании сжатия пути (по крайней мере, без обхода всего дерева, что увеличивает временную сложность алгоритма «поиска».
Здесьпример реализации, которую я нашел, и использует то, что я описал (очень похоже на то, что я кодировал) в c ++: https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20(Disjoint%20Set)%20Data%20Structure.cpp