Tree - Description


The generic class Tree is a balanced binary tree. The generic has two type parameters, K - the key type, and T - the data type. The data type T contains an embedded key. The key type K is provided for separate keyed searches. The generic class Tree exists in the namespace calculus (in assembly calculus.jar).

When creating a tree Tree<K,T>, both the key class K and the data class T are expected to be comparable. These classes can derive from the appropriate Comparable interface or comparators can be explicitly specified through a constructor.

The declaration of the tree class (in Java) is shown below.

public class Tree<K, T> extends Set<T>
{
 ...
}

The class Tree derives from the class Set. All the methods of Set apply to trees.

Searches, insertions and removals are O(log2n).

When for is applied to a tree, the entries are presented in key order.

Trees are single keyed trees. The class BagTree provides multiple keyed trees.