|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
also defines three operations for manipulating
the root of an N-ary tree.
The Key property provides a get accessor that returns the
object contained in the root node of the tree.
Clearly, this operation is not defined for the empty tree.
If the tree is not empty, the running time of this method is O(1).
The purpose of AttachKey is to insert the specified object into a given N-ary tree at the root node. This operation is only defined for an empty tree. The AttachKey method takes as its argument an object to be inserted in the root node and assigns that object to the key field. Since the node is no longer empty, it must have exactly N subtrees. Therefore, N new empty subtrees are created and attached to the node. The running time is O(N) since N subtrees are created, and the running time of the constructor for an empty N-ary tree takes O(1).
Finally, DetachKey is used
to remove the object from the root of a tree.
In order that the tree which remains still conforms
to Definition ,
it is only permissible to remove the root from a leaf node.
And upon removal, the leaf node becomes an empty tree.
The implementation given in Program
throws an exception if an attempt is made to remove the root
from a non-leaf node.
Otherwise, the node is a leaf which means that its N subtrees are all empty.
When the root is detached,
the array of subtrees is also discarded.
The running time of this method is clearly O(1).
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.