BagTree - Description


The generic class BagTree is a balanced binary tree. The generic has two type parameters, K - the key type, and T - the data type. BagTrees are different from single key trees in that they allow duplicate keys. The generic class BagTree exists in the namespace calculus (in assembly calculus.jar).

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

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

public class BagTree<K, T> extends Bag<T>
{
 ...
}

BagTrees derive from Bags.

For a bag tree each T has an embedded key. Separate keyed searches (on K) are supported.

Searches, insertions and removals are O(log2N).