Вы всегда могли бы решить эту проблему, визуализируя ее в виде дерева и его узлов, соединяющей друг с другом с помощью корня, а затем смотрит на дерево, если вы хотите знать, если подключены два узла. Если два узла, которые вы сравниваете, имеют один и тот же корень (они находятся в одном и том же дереве), чем они связаны.
Чтобы подключить два узла, просто перейдите к корню каждого дерева, в котором они находятся, и сделайте один корень родителем другого.
Это видео даст вам большую интуицию об этом: https://www.youtube.com/watch?v=YIFWCpquoS8&list=PLUX6FBiUa2g4YWs6HkkCpXL6ru02i7y3Q&index=1
Связь между узлами дерева можно сделать с помощью указателей на языке, который поддерживает его, но если ваш язык Dont (питон), чем вы может создавать ваши собственные указатели, сохраняя позиции и ссылки через массив.
Массив будет таким, чтобы его позиции представляли ваши узлы, а значения внутри него представляют собой соединение конкретного узла с его корнем. В начале позиция в массиве заполняется номером узла, потому что узлы изначально не имеют родительского элемента, но при подключении узлов корни меняются, и массив должен представлять это. Фактически, значение, хранящееся там, является идентификатором корня.
Но попробуйте визуализировать проблему визуально сначала, а не думать о массивах и слишком много математических искусств. Визуальное обращение с ним делает решение звучным банальным и может быть хорошим руководством при написании кода.
Я говорю это, потому что я смотрел видео от Роберта Седжуика, которое я только что опубликовал, с графическим моделированием решения и реализовал себя, не обращая слишком много внимания на код своей книги. Интуиция, которую предоставила мне видео, гораздо более ценна, чем любая математика.
Это поможет вам инкапсулировать узлы в класс со следующими методами:
- climbTreeFromNodeUpToRoot
- setNewParentToThisNodeAndUpdateHeights
Первый метод, как говорит название, берет Вас от узел и идет вверх по дереву, пока не найдет его корень, который затем возвращается.
Если вы сравниваете два узла с этим методом (на самом деле, корни, возвращаемые им), вы легко знаете, если они связаны, просто сравнивая их корни.
Как только вы хотите связать их, вы поднимаетесь по деревьям обоих узлов и просите один корень взять другой в качестве своего родителя.
Деревья могут расти очень большими по высоте (извините, я не использую официальную номенклатуру, но это тот, который имеет для меня смысл), поэтому этот простой подход будет очень медленным, когда вам нужно подняться по дереву на позднее время.
Чтобы предотвратить рост деревьев, не устанавливайте один корень в качестве родительского для другого без критерия, но приложите самое маленькое дерево (с точки зрения высоты, а не количества элементов) до самого высокого.
Для этого вам необходимо знать высоты каждого дерева и эту информацию, которую вы можете сохранить в своем корне (через дополнительный массив в вашем случае или дополнительный указатель с каждого узла на других языках). Эта информация должна обновляться каждый раз, когда к ней подключается другое дерево.
Невозможно, чтобы дерево узнало, что у нее только что появилось новое дерево, поэтому важно, чтобы каждое дерево, прикрепленное ко второму, информировало второе, чтобы обновить его высоту.
Эта информация может быть отправлена в корень второго дерева, а затем использована для оценки (как описано ранее), какое дерево является наименьшим. Помните, что прикрепление маленького дерева к большому, а не наоборот, избавит вас от невероятного количества времени.