Структуры данных и модели вычислений
Реализация операций с помощью древовидной структуры
Операция СОЗДАТЬ
() назначает в качестве родителя узла сам узел с помощью присваивания . Таким образом, время выполнения операции есть . В результате выполнения операции СОЗДАТЬ() образуется новое одновершинное дерево с петлей в корне, изображенное на рис. 3.2.
Рис. 3.2.
Если к коллекции подмножеств, изображенных на рис. 3.1, применить операцию СОЗДАТЬ (5), то получим коллекцию, изображенную на рис. 3.3.
Рис. 3.3.
Операция ОБЪЕДИНИТЬ
() назначает узел
родителем узла с помощью присваивания . Заметим, что и должны быть до выполнения рассматриваемой операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет , а перестанет быть именем какого-либо множества. Время выполнения этой операции есть .
Рис. 3.4.
Если применить операцию ОБЪЕДИНИТЬ к коллекции, представленной на рис. 3.3, то получим коллекцию, состоящую из двух подмножеств и , — изображенную на рис. 3.4. Именем первого из этих подмножеств будет 6, второго — 5.
Операция НАЙТИ() осуществляется продвижением по указателям на родителей от узла до корня дерева. В качестве берется этот корень. Описанные действия можно реализовать с помощью операторов
Очевидно, что время выполнения данной операции есть , где — длина пути из узла в корень соответствующего дерева. Но заметим, что при выполнении операций СОЗДАТЬ и ОБЪЕДИНИТЬ возможно образование дерева в виде линейной цепочки из узлов, изображенной на рис. 3.5.
Рис. 3.5.
К такой цепочке может привести, например, следующая последовательность операций
СОЗДАТЬ ();
СОЗДАТЬ ();
… … …
СОЗДАТЬ ();
ОБЪЕДИНИТЬ ();
ОБЪЕДИНИТЬ ();
… … …
ОБЪЕДИНИТЬ ();
Как видим,может достигать величины, поэтому трудоемкость операции НАЙТИ является величиной.
Худший случай применения операции НАЙТИ в данной ситуации — это НАЙТИ (). В этом случае необходимо сделатьпереход по ссылкам на родителей, чтобы дойти от узла к корню дерева , и один переход, чтобы узнать, что родитель узла есть сам узел .
Если операция СОЗДАТЬ выполняетсяраз, то время выполнения последовательности, составленной изопераций ОБЪЕДИНИТЬ иили НАЙТИ, при рассматриваемой реализации разделенных множеств есть величина . Действительно, время выполнения операций ОБЪЕДИНИТЬ, очевидно, есть , так как время выполнения одной такой операции есть константа. Время выполнения операций НАЙТИ есть, так как время выполнения одной такой операции есть. Итак, время выполнения произвольных операций есть .
