Interface OrientedForest

A data structure with parent/child relationships. Each node may have at most one adjacent node distinguished as being its "parent", and the data structure should be acyclic under the parent operation. The following are definitions for other terms used here (and elsewhere):

• If node X is the parent of node Y, then we also say that Y is a "child" of X. A node may have multiple children.
• A node with no parent is a "root" node. Every node in the graph is contained in a subgraph with a unique root, which can be found by following the chain of parents until it ends.
• A node with no children is a "leaf". A non-leaf node is an "internal node".
• If node X is reachable through successive applications of the parent operation from node Y, then X is an "ancestor" of Y, and Y is a "descendant" of X. Note that any node is both an ancestor and descendant of itself.
• Two nodes with the same parent are "siblings".
• The length of the path from a given node to its root is its "depth". The depth of a root node is 0.
• The length of the longest path from a given node to a leaf is its "height". The height of a leaf is 0.

The word "oriented" was chosen instead of the more commonly used "directed" because the directedness of the edges need not have any bearing on the parent-child relationships.

Since: 1.0

Version: $Revision: 1.2 $

Author: Ray A. Conner