Definition
An instance D of the parameterized data type tree_collection<I> is a collection of vertex disjoint rooted trees, each of whose vertices has a double-valued cost and contains an information of type I, called the information type of D.
#include < LEDA/core/tree_collection.h >
Creation
tree_collection<I> | D | creates an instance D of type tree_collection<I>, initialized with the empty collection. |
Operations
Implementation
Dynamic collections of trees are implemented by partitioning the trees into vertex disjoint paths and representing each path by a self-adjusting binary tree (see [86]). All operations take amortized time O(log n) where n is the number of maketree operations.