Структуры данных и модели вычислений
Представление разделенных множеств с использованием рангов вершин и сжатия путей
Предыдущий способ реализации разделенных множеств можно еще улучшить за счет усовершенствования реализации операции НАЙТИ,(). Она теперь будет выполняться в два прохода. При первом проходе находится кореньтого дерева, которому принадлежит . При втором проходе из в все встреченные узлы делаются непосредственными потомками узла. Этот прием, как мы увидим ниже, намного уменьшает время выполнения последующих операций НАЙТИ.
Реализация операций. Рассматриваемая реализация не требует новых полей данных по сравнению с предыдущим случаем. Как и прежде, для каждого узлабудем хранить указательна его родителя и ранг, который теперь не обязательно будет равен высоте дерева с корнем . Он будет равен этой высоте, если не использовать операцию НАЙТИ.
Операция СОЗДАТЬ () выполняется с помощью операторов
В качестве родителя узлаберется тот же самый, а его рангом считаем . Таким образом, время выполнения операции есть константа.
Операция ОБЪЕДИНИТЬ () выполняется как и прежде, разница лишь в том, что вместо массива используется массив . Время выполнения операции — константа.
Операция НАЙТИ, как уже говорилось, выполняется в два прохода. При первом проходе мы идем от узлак его родителю, потом к родителю его родителя и так далее, пока не достигнем корня у дерева, содержащего узел. При втором проходе из в все встреченные на этом пути узлы делаются непосредственными потомками узла . Будем называть это "сжатием путей". Очевидно, как и раньше, время выполнения одной такой операции есть. Но ниже будет доказано, что время выполнения таких операций на самом деле меньше, чем. Заметим, что при выполнении этой операции ранги узлов не изменяются.
