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