Реализация операций с использованием рангов вершин
Для такой реализации разделенных множеств необходимо хранить с каждым узлом дополнительно еще одну величину — высоту поддерева, корнем которого является узел . Будем называть ее высотой, или рангом, узла . Остальные операции нужно настроить на корректную работу с этим полем. Будем хранить высоту каждого узла в ячейке массива .
Операция СОЗДАТЬ () назначает в качестве родителя узлатот же самый, а высотой узласчитает 0. Таким образом, время выполнения данной операции есть. В результате выполнения операции СОЗДАТЬ () образуется новое дерево, изображенное на рис. 3.6. Число, расположенное рядом с узлом, обозначает его высоту. Описанные действия реализуются с помощью операторов
Рис. 3.6.
Операция ОБЪЕДИНИТЬ
() назначает корень большего по высоте дерева родителем корня другого дерева. Если деревья имеют одинаковую высоту, то узел назначается родителем узла , после чего значение высоты узла увеличивается на единицу. Заметим, что и должны быть до выполнения операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет имя того из объединяемых подмножеств, у которого корень имел большую высоту, а имя другого из объединяемых подмножеств перестанет быть именем какого-либо из подмножеств. Очевидно, время выполнения этой операции есть константа. Выполнить описанные действия можно с помощью следующей процедуры:
На рис. 3.7 и рис. 3.8 показано применение операции ОБЪЕДИНИТЬк коллекции, изображенной на рис. 3.3, с учетом высот объединяемых поддеревьев. Рядом с кружочками, изображающими узлы, показаны их высоты. Так как, то родителем узла 6 становится узел 3.
Операция НАЙТИ () осуществляется, как и в предыдущей реализации, продвижением по указателям на родителей от узла до корня дерева. В качестве берется найденный корень.
Рис. 3.7.
Рис. 3.8.
Очевидно, что время выполнения данной операции, как и ранее, пропорционально длине пути из узлав корень соответствующего дерева. Однако длина такого пути в данном случае может быть оценена иначе. Для оценки длины этого пути докажем следующие леммы:
Лемма 1.
В результате выполнения любой последовательности операций из набораСОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИнад пустой коллекцией разделенных множеств для любого узла выполняется неравенство, где — количество узлов в поддереве с корнем — высота узла .
Доказательство
Очевидно, перед первым применением операции ОБЪЕДИНИТЬ для любого узлаимели ,и, следовательно,. Операции СОЗДАТЬ и НАЙТИ не могут нарушить доказываемого неравенства, поэтому доказательство можно провести индукцией по количеству применений операции ОБЪЕДИНИТЬ.
Предположим, что перед очередным применением операции ОБЪЕДИНИТЬ () доказываемое неравенство все еще остается верным, тогда если высота узла меньше высоты узла , то дерево, полученное с помощью ОБЪЕДИНИТЬ (), имеет корень , а высоты узлов и не изменились. Количество узлов в дереве с корнем не изменилось, а количество узлов в дереве с корнем увеличилось. Таким образом, как для узлов,, так и для всех остальных неравенство сохраняется. Случай, когда высота узла больше высоты узла , аналогичен рассмотренному.
Если же высоты деревьев с корнями и до выполнения операции были одинаковы (, то узел становится родителем узла , высота узла увеличивается на 1, а высота узла не изменяется. Пусть после выполнения операции величины,,,становятся равными соответственно,,,, тогда имеем,,,. По предположению индукции, имеем и. Следовательно, после выполнения рассматриваемой операции для узлов и имеем соотношения Таким образом, утверждение леммы остается верным и в этом случае.
Лемма 2.
Если за время работы, начавшейся с пустой коллекции, операция СОЗДАТЬ применяласьраз, то для любогочисло узлов высоты удовлетворяет неравенству.
Доказательство
Пусть— все узлы высоты , тогда по лемме 1 присправедливы неравенства. Таким образом, откуда и следует требуемое неравенство.
Следствие 3.
В результате выполнения любой последовательности операций из набораСОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИнад пустой коллекцией разделенных множеств для любого узлаимеет место неравенство.
Доказательство
Дерево максимальной высоты образуется, очевидно, лишь тогда, когда все элементов объединяются в одно множество. Для такого дерева количество узлов максимальной высоты равно 1, по лемме 2 имеем , откуда и, следовательно,.
Следствие 4.
Время выполнения операции НАЙТИ есть.
Следствие 5.
При реализации разделенных множеств с использованием рангов время выполнения операций ОБЪЕДИНИТЬ иили НАЙТИ есть величина.
Замечание
При реализации операции объединения подмножеств в качестве ранга узла можно использовать количество узлов в поддереве с корнем в данном узле. Утверждение леммы 1 будет справедливым и в этом случае, следовательно, сохранятся и оценки времени выполнения операций.
