Структуры данных и модели вычислений


Реализация операций с помощью древовидной структуры


Операция СОЗДАТЬ

() назначает в качестве родителя узла сам узел с помощью присваивания . Таким образом, время выполнения операции есть . В результате выполнения операции СОЗДАТЬ() образуется новое одновершинное дерево с петлей в корне, изображенное на рис. 3.2.


Рис. 3.2. 

Если к коллекции подмножеств, изображенных на рис. 3.1, применить операцию СОЗДАТЬ (5), то получим коллекцию, изображенную на рис. 3.3.


Рис. 3.3. 

Операция ОБЪЕДИНИТЬ

() назначает узел

родителем узла с помощью присваивания . Заметим, что и должны быть до выполнения рассматриваемой операции корнями соответствующих деревьев. Именем вновь образованного подмножества будет , а перестанет быть именем какого-либо множества. Время выполнения этой операции есть .


Рис. 3.4. 

Если применить операцию ОБЪЕДИНИТЬ к коллекции, представленной на рис. 3.3, то получим коллекцию, состоящую из двух подмножеств и , — изображенную на рис. 3.4. Именем первого из этих подмножеств будет 6, второго — 5.

Операция НАЙТИ() осуществляется продвижением по указателям на родителей от узла до корня дерева. В качестве берется этот корень. Описанные действия можно реализовать с помощью операторов

Очевидно, что время выполнения данной операции есть , где — длина пути из узла в корень соответствующего дерева. Но заметим, что при выполнении операций СОЗДАТЬ и ОБЪЕДИНИТЬ возможно образование дерева в виде линейной цепочки из узлов, изображенной на рис. 3.5.


Рис. 3.5. 

К такой цепочке может привести, например, следующая последовательность операций

СОЗДАТЬ ();

СОЗДАТЬ ();

… … …

СОЗДАТЬ ();

ОБЪЕДИНИТЬ ();

ОБЪЕДИНИТЬ ();

… … …

ОБЪЕДИНИТЬ ();

Как видим,может достигать величины, поэтому трудоемкость операции НАЙТИ является величиной.

Худший случай применения операции НАЙТИ в данной ситуации — это НАЙТИ (). В этом случае необходимо сделатьпереход по ссылкам на родителей, чтобы дойти от узла к корню дерева , и один переход, чтобы узнать, что родитель узла есть сам узел .

Если операция СОЗДАТЬ выполняетсяраз, то время выполнения последовательности, составленной изопераций ОБЪЕДИНИТЬ иили НАЙТИ, при рассматриваемой реализации разделенных множеств есть величина . Действительно, время выполнения операций ОБЪЕДИНИТЬ, очевидно, есть , так как время выполнения одной такой операции есть константа. Время выполнения операций НАЙТИ есть, так как время выполнения одной такой операции есть. Итак, время выполнения произвольных операций есть .




Начало  Назад  Вперед