Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

getKey, attachKey, and detachKey Methods

Program gif also defines three methods for manipulating the root of an N-ary tree. The first, getKey, is an 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 gif, 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 gif 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).


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.