Tree Container Library

The Tree Container Library (TCL) is a class template library that you can use to store data elements in a tree-like structure. The TCL consists of four templatized container classes, similar to those found in the STL. These classes allow storage of basic data types or user-defined types to be stored as nodes within a tree structure. Each node of the tree is considered a tree itself, having all the properties of a tree container. So, any operations that can be performed on the tree container likewise can be performed on any node within the tree. Iterators are provided to allow the transversal of the tree nodes. Insert and find operations, as well as various other operations, are also provided. The TCL provides four tree containers that differ according to their intention of use:

  • tree: The tree container is used for tree structures in which every sibling node is unique, or rather, every child node of a particular parent can be uniquely distinguished. Non-sibling nodes need not be unique.
  • multitree: The multitree container is used for tree structures in which siblings need not be unique, or rather, children which have the same parent node need not be distinguishable.
  • unique_tree: The unique_tree container is used for tree structures in which every node in the tree is unique. Because every node in the tree is guaranteed to be unique, the unique tree offers a find_deep() operation, as well as other operations different from tree and multitree.
  • sequential_tree: The sequential_tree container is used for tree structures in which the tree nodes remain in the same order in which they are inserted. Any or all nodes may later be sorted, by using a binary predicate or function object.

The tree and multitree are very similar in operation and interface. The difference between the two is much like the difference between the set and multiset in the STL. The unique_tree offers many more features because each node in the tree is unique. For example, the find() operation is available to tree, multitree, and unique_tree, which searches for a matching node contained within a single parent node. The unique_tree offers an additional operation, find_deep(), which not only searches the parent node's immediate children but also searches its descendants.

The unique_tree also offers extensions to the common interface for the three tree types. For example, all four trees offer the insert(child) operation, in which a child is inserted in the parent issuing the insert operation. The unique_tree offers an extension to this and other operations. So, the unique_tree provides another insert operation insert(parent, child), which inserts the child in the specified parent node (if found).

tree, multitree, and unique_tree are considered associative tree containers because they all use std::set for internal child node containment. sequential_tree, however, uses a std::vector to store the child nodes. Thus, sequential_tree does not offer find() operations like the associative tree containers do. sequential_tree has its unique operations, however, like multiple sort() operations that can be used to sort any/all of the child nodes within their parent. The associative trees do not need sort() operations because their nodes are ordered naturally.

Like the STL, the TCL uses iterators in many of its operations. Not only can iterators be used to traverse the tree structures in various ways, many of the operations performed on the trees returns an iterator, such as the find() and insert() operations. The most common iterators in the library are the iterator and const_iterator. These iterators are created using the same syntax as iterators in the STL. If a tree container contains objects of the type CMyClass, an iterator would be created as tree<CMyClass>::iterator it;, or tree<CMyClass>::const_iterator it;. These two standard iterators traverse only a parents immediate children.

To traverse a parent's descendant nodes as well as its children, there are three more iterators provided: pre_order_iterator, post_order_iterator, and level_order_iterator. The creation of these descendant iterators uses the same syntax as the standard iterators mentioned above.

Like the iterators of STL, the * and -> operators are overridden to return the reference/pointer to the underlying node. Because of this, the underlying node operations are available to the iterators, such as insert() and find(). All nodes have the same interface as the declared tree in which the nodes reside (remember, nodes are themselves trees). This is a very important concept in the TCL. Every node in a tree structure has the same operations of the tree itself because nodes are in fact the same type as the declared tree that it's in. The only difference between a declared tree container and one of its nodes is the simple fact that the declared tree container doesn't have a parent node (it's the root node).

Using the Tree Container Library (TCL) is much like using the container classes in the STL. The syntax and operations are very similar. First, you will need to decide which of the four tree containers will fit your needs. The difference between the tree containers is described above.

The tree and multitree both take two template parameters, the second being optional. The first parameter represents the data type you will store in the container, henceforth called the stored_type. The stored_type can be either a basic data type, such as an int or a string, or a user defined type (class). The second template parameter represents the node comparison operation, a functor, used in the searching and ordering of the nodes, henceforth called the node_compare_type. If not supplied, this template parameter defaults to std::less<stored_type>. So, if the container stores a basic type such as ints, the node_compare_type will default to std::less<int>. If the container stores class objects, you could either supply a < operation for the class that would be used when the node_compare_type defaults to std::less<stored_type>, or, create and use a functor for the second parameter.

The unique_tree takes three template parameters, the last two being optional. The first two template parameters are the same as with the tree and multitree described above. The third template parameter represents another node comparison operation, called the node_order_compare_type that is used for special iterators called ordered_iterators that can be used to determine an alternate ordering of nodes within their parent. An alternate ordering for child nodes can be handy if the comparison operation used to distinguish unique nodes within the unique_tree is not the desired ordering you want to be used to traverse child nodes within a single parent.

The sequential_tree takes a single template parameter, which is required. This parameter represents the data type you will store in the container, stored_type, discussed above. Because this container does not naturally order the nodes within their parent, there is not a node_compare_type that is needed for sequential_tree. The nodes remain in the order in which they were inserted into the tree. This container does, however, offer sorting operations for any or all of the nodes, so the order of the nodes can be changed if desired.

Given the above information, the following are simple declarations of the four tree containers:

  • tree<std::string> my_tree;
  • multitree<int> my_tree
  • unique_tree<CMyClass> my_tree;
  • sequential_tree<std::string> my_tree;

The TCL allows for polymorphic storage without the need to store pointers in the tree container. This means that you can store objects of stored_type and class objects derived from stored_type, and those objects will keep their original identity. To do this, you must supply a clone function to the tree container. The container uses the clone function to copy the stored_type or objects derived from stored_type, rather than using the stored_type copy constuctor.

The demo download contains a number of files. The files are all part of four sample console programs. The following list details the four demo programs and their associated files.

  • Generic Example: This example shows all three associative tree containers at work. It demonstrates insertion and the use of child_iterators and descendant iterators. It also demonstrates the difference between the three types of associative tree containers, by attempting to insert duplicate nodes.
    Files:
    • generic_example.cpp: The CPP file to use in your console project.
    • generic_example_explanation.rtf: An RTF file that explains the example code in detail.
    • generic_example_diagram.jpg: A diagram depicting the tree structure used in the example.
    • generic_example_results.jpg: A screenshot of the console results you should expect to see.
  • unique_tree Example: This example demonstrates the operations and features of the unique_tree because the unique_tree offers features that the tree, multitree, and sequential_tree do not.
    Files:
    • unique_tree_example.cpp: The CPP file to use in your console project.
    • unique_tree_explanation.rtf: An RTF file that explains the example code in detail.
    • unique_tree_example_diagram.jpg: A diagram depicting the tree structure used in the example.
    • unique_tree_example_results.jpg: A screenshot of the console results you should expect to see.
  • Polymorphic Example: This example demonstrates the polymorphic nature of the associative tree containers by inserting derived class objects of the declared tree type.
    Files:
    • polymorphic_example.cpp: The CPP file to be used in your console project.
    • polymorphic_example_explanation.rtf: An RTF file that explains the example code in detail.
    • polymorphic_example_diagram.jpg: A diagram depicting the tree structure used in the example.
    • polymorphic_example_results.jpg: A screenshot of the console results you should expect to see.
  • sequential_tree example
    Files:
    • sequential_tree_example.cpp: The CPP file to be used in your console project.
    • sequential_tree_example_explanation.rtf: An RTF file which explains in detail the example code.
    • sequential_tree_example_diagram.jpg: A diagram depicting the tree structure used in the example.
    • sequential_tree_example_results.jpg: A screenshot of the console results you should expect to see.

If you are using Visual C++ 6.0, you will need to uncheck the Enable minimal rebuild option in the project for successful compilation.

The following operations describe the public interface that is available to all four tree containers in the TCL. Many of the basic functions return child iterators. All occurences of the term iterator below refer to the appropriate type of child iterator for the specific tree container or tree_type. Both child iterators, iterator and const_iterator, are bi-directional iterators.

In the function signatures below, stored_type is used to refer to the type of objects being stored in the tree container. The term node_compare_type is used to refer to the function object that provides the comparison operator for the tree nodes.

The following list is categorized for easy reference.

Standard Operations

Inserting/Removing nodes

  • iterator insert(const stored_type& stored_obj): This is the standard insertion function for all trees. It's overridden in each class, and each in turn calls the similar function in the base class. The parameter is a reference to the stored object being stored in the node. This function is polymorphic, and allows the insertion of objects derived from stored_type. The object is inserted into a child node of the parent in which the function was called. An iterator is returned that points to the inserted node. For tree and unique_tree, if the stored_type object already exists as a child node, the object is not inserted, and the end iterator is returned. For sequential_tree, this function inserts the object as the last child in the parent.
    Complexity: Logarithmic
  • iterator insert(const tree_type& tree_obj): This function inserts a tree into another tree of the same type. All descendants of the inserted tree are inserted in the process.
    Complexity: Logarithmic
  • void erase(iterator it): This operation is available for all trees. It accepts an iterator that points to a child node within a parent to erase.
    Complexity: Logarithmic
  • bool erase(stored_type& stored_obj): This operation is available for the associative trees only, and not for sequential_tree. This function varies slightly depending on the tree container that it's called. For a tree, the immediate children are searched. The return result indicates its success. For a multitree, the immediate children are searched, and all occurences of the object are erased. The return result indicates whether any node was erased. For a unique_tree, all descendants are searched. The return result indicates its success.
    Complexity: Logarithmic
  • void clear(): Clears (erases) all descendants of the node. The node itself is not erased, and its stored_type object remains intact.
    Complexity: Logarithmic

Searching nodes

All find() operations are available for the associative trees only.

  • iterator find(const stored_type& stored_obj): Searches child nodes for the stored_type object. Returns an iterator pointing to the found node, or the end node if unsuccessful. There is a slight variance in the behavior of the multitree container. Because multitrees can have multiple occurences in a single parent, the iterator will return a pointer to the first found occurrence, or the end iterator if not found. Remember that, when searching nodes, the node_compare_type will determine the equality of the node that's being sought.
    Complexity: Logarithmic
  • const_iterator find(const stored_type& stored_obj) const: Same as the above function, but returns a const_iterator rather than iterator.
    Complexity: Logarithmic

Querying node state

  • stored_type get(): Returns a pointer to the stored_type object within the node. Remember that the nodes are not themselves objects of store_type, but rather contain objects of those types.
    Complexity: Constant
  • const stored_type get() const: Returns a const pointer to the stored_type object within the node.
    Complexity: Constant
  • tree_type* parent(): Returns a pointer to the parent node, or NULL if there is no parent node (indicating that this is the root node).
    Complexity: Constant
  • bool is_root(): Indicates whether node is the root node in the tree structure.
    Complexity: Constant
  • bool empty(): Indicates whether or not the node has children. Does not care about the stored_type within the node itself.
    Complexity: Constant
  • int size(): Returns the number of child nodes within the node. Only counts the immediate children, not the descendants.
    Complexity: Constant

Setting node state

  • void set(const stored_type& stored_obj): Sets the stored_type object in a node. This function is polymorphic, so the passed type can either be a stored_type or a type derived from stored_type.
    Complexity: Constant
  • void set(const tree_type& tree_obj): Sets the node to the passed tree object. All descendants of the passed tree object will afterwards be descendants of the node. A copy is made of the passed tree object and all its descendants.
    Complexity: Logarithmic
  • void for_each(void (*pFcn)(tree_type*)): Calls pFcn(tree_type*) on the node and all its descendants. Uses a pre_order_iterator internally to traverse the descendants.
    Complexity: Linear
  • void for_each(T& func_ob) Same as the function above, but a function object is passed, rather than a pointer to a function.
    Complexity: Linear

Iterator retrieval

  • iterator begin(): Returns an iterator pointing to the first child in the node. If the node is empty, returns the end iterator.
    Complexity: Constant
  • const_iterator begin() const: Same as above, but returns a const_iterator rather than iterator.
    Complexity: Constant
  • iterator end(): Returns an iterator pointing to past the last child node. Iterators can be checked against the end iterator to see whether an operation succeeded, or whether they have traversed through all the children.
    Complexity: Constant
  • const_iterator end() const: Same as above, but returns a const_iterator rather than iterator.
    Complexity: Constant
  • pre_order_iterator pre_order_begin(): Returns the beginning pre_order_iterator for the node. pre_order_begin() will by nature return an iterator pointing to the first immediate child, if any.
    Complexity: Constant
  • const_pre_order_iterator pre_order_begin() const: Same as above, but returns a const_pre_order_iterator
    Complexity: Constant
  • pre_order_iterator pre_order_end(): Returns the ending pre_order_iterator for the node. When using the pre_order_iterator, it must be checked against pre_order_end() to know when all the descendants have been traversed.
    Complexity: Constant
  • const_pre_order_iterator pre_order_end() const: Same as above, but returns a const_pre_order_iterator
    Complexity: Constant
  • post_order_iterator post_order_begin(): Returns the beginning post_order_iterator for the node. post_order_begin() will, by nature, return an iterator pointing to the deepest first descendant node, if any.
    Complexity: Logarithmic
  • const_post_order_iterator post_order_begin() const: Same as above, but returns a const_post_order_iterator
    Complexity: Constant
  • post_order_iterator post_order_end(): Returns the ending post_order_iterator for the node. When using the post_order_iterator, it must be checked against post_order_end() to know when all the descendants have been traversed.
    Complexity: Constant
  • const_post_order_iterator post_order_end() const: Same as above, but returns a const_post_order_iterator.
    Complexity: Constant
  • level_order_iterator level_order_begin(): Returns the beginning level_order_iterator for the node. level_order_begin() will, by nature, return an iterator pointing to the first immediate child, if any.
    Complexity: Constant
  • const_level_order_iterator level_order_begin() const: Same as above, but returns a const_level_order_iterator.
    Complexity: Constant
  • level_order_iterator level_order_end(): Returns the ending level_order_iterator for the node. When using the level_order_iterator, it must be checked against level_order_end() to know when all the descendants have been traversed.
    Complexity: Constant
  • const_level_order_iterator level_order_end() const: Same as above, but returns a const_level_order_iterator
    Complexity: Constant

Tree Container Library

Miscellaneous operations

  • void set_clone(stored_type* (*pFcn)(const stored_type&)): Sets a clone function needed when the tree contains objects of derived types. The clone function that you define and pass to this function takes a const reference to a stored_type as its only parameter, and returns a pointer to stored_type. Normally, this function will just call a virtual function of stored_type called clone(). clone() then would be overridden in all the derived classes to return a pointer to itself (return new derived_type(*this); )
    Complexity: Constant

unique_tree operations

The unique_tree<> offers the same standard interface as the tree<> and multitree<> containers, plus additional operations that are available because each node in the tree is guaranteed to be unique. Because of this, any node can be found from the root. In the tree<> and multitree<> containers, it's only possible to find children nodes from their immediate parent.

One of the most useful additions to the unique_tree<> interface is the find_deep() operation. This and other operations unique (no pun intended) to the unique_tree<> are described below. In the definitions, stored_type is used to refer to the type of objects being stored in the tree container. Similarly, the term derived_type is used to refer to an object of a class derived from stored_type. Following are the specific operations available in unique_tree.

Inserting nodes

  • iterator insert(const stored_type& parent_obj, const stored_type& stored_obj): Inserts a child node containing the stored_obj in the parent node specified by the parent_obj. This is a polymorphic operation, so stored_obj can be of any type derived from stored_type, and it will keep its type identity while stored in the container, provided a clone operation is provided. An iterator is returned, pointing to the inserted node. This insert operation, and the one immediately below, differ from the standard insert operations in that they take one argument. This insert operation need not fail even when the parent is not found. In this case, if orphans are allowed (see below), the unique_tree creates the parent/child pair within an internal temporary storage (orphans). The parent, and associated children and descendants, remain in the orphan storage until a matching node for the parent is inserted that has a valid parent. When this occurs, the stored_type of the new matching node replaces the stored_type of the node in orphan storage, and it (along with any of its descendants) is removed from the temporary storage and placed in its appropriate position in the tree container structure. The reason for this behavior is that, when inserting nodes using these parent/child insert operations from data in a database or sequencial container, it's not always guarenteed that its parent or its ancestors have already been inserted.
    Complexity: Logarithmic

Searching nodes

  • iterator find_deep(const stored_type& stored_obj): Searches descendant nodes for the stored_type object. Returns an iterator pointing to the found node, or the end node if unsuccessful. The difference between this operation and the find() operation is that the find() operation only searches the children nodes, whereas find_deep() searches the descendant nodes. Because multitree can have multiple occurences in a single parent, the iterator will return a pointer to the first found occurrence, or the end iterator if not found. Remember that, when searching nodes, the node_compare_type will determine the equality of the node that's being sought.
    Complexity: Logarithmic
  • const_iterator find_deep(const stored_type& stored_obj) const: Identical to the operation above, but returns a const_iterator rather than an iterator.
    Complexity: Logarithmic
  • ordered_iterator find_ordered(const stored_type& stored_obj): Searches child nodes using the alternate ordering operation. Returns an ordered_iterator to the found child, or ordered_end() if not found.
    Complexity: Logarithmic
  • const_ordered_iterator find_ordered(const stored_type& stored_obj) const: Searches child nodes using the alternate ordering operation. Returns a const_ordered_iterator to the found child, or const_ordered_end() if not found.
    Complexity: Logarithmic

Iterator retrieval

  • ordered_iterator ordered_begin(): Returns an ordered_iterator pointing to the first child in the node, if present. The ordered iterator gives an alternate way in which child nodes are traversed. It traverses the children in an order that uses the third template parameter to the unique_tree, the node_order_compare_type. Use of the ordered_iterator can be handy if you want to traverse the child nodes in an order different than offered by the standard iterator, that uses the node_compare_type for its comparisons.
    Complexity: Constant
  • ordered_iterator ordered_end(): Returns an end ordered_iterator. This iterator points just beyond the last ordered child node in the parent. When traversing a parent's children with an ordered_iterator, you would need to test it against ordered_end() to determine when all child nodes have been traversed.
    Complexity: Constant
  • const_ordered_iterator ordered_begin() const: Returns a const_ordered_iterator pointing to the first child in the node, if present. Otherwise, returns const_ordered_end().
    Complexity: Constant
  • const_ordered_iterator ordered_end() const: Returns an end const_ordered_iterator.
    Complexity: Constant

Miscellaneous operations

  • void allow_orphans(bool bAllow): Allows orphans in the container. Allowing orphans is necessary if you are using the insert(parent, child) operation, and are unable to insure that all parents will be inserted before their associated children or descendants. If orphans are not allowed, any insertion using the operation insert(parent, child) will fail if the parent cannot be found in the tree.
    Complexity: Constant
  • bool allow_orphans(): Indicates whether orphans are currently allowed in the container.
    Complexity: Constant
  • bool is_orphan(): Indicates whether the current node is an orphan.
    Complexity: Constant

sequential_tree Operations

The sequential_tree interface includes the standard interface (described above) minus three operations which are available only to associative trees. Those operations are:
bool erase(stored_type& stored_obj)
iterator find(const stored_type& stored_obj)
const_iterator find(const stored_type& stored_obj) const

The sequential_tree has some additional operations of its own, however. Those operations are described below.

Inserting nodes

  • iterator insert(const_iterator insert_before, const stored_type& stored_obj: Inserts stored_obj before insert_before. Checks whether insert_before is within bounds, and if not, inserts stored_obj at the end of the children.
    Complexity: Constant
  • iterator insert(const_iterator insert_before, const tree_type& tree_obj): Inserts a tree_node and its descendants before insert_before. Checks whether insert_before is within bounds, and if not, inserts stored_obj at the end of the children.
    Complexity: Constant

Sorting child nodes

  • void sort(): Sorts the child nodes using the less-than operator of stored_type. This operator must be defined for stored type to use this operation. Sorts only the children within the node that it's called.
    Complexity: Logarithmic
  • void sort(const pPred& predicate): Sorts the child nodes using the passed prediate function. The predicate function must have the signature: void predicate(const stored_type& lhs, const stored_type& rhs)
    Sorts only the children within the node that it's called.
    Complexity: Logarithmic
  • template<typename T> void sort(const T& function_object): Sorts the child nodes using the function object. The function object should define the call operator with the signature as below.
    bool operator ()(const stored_type& lhs, const stored_type& rhs) const
    Sorts only the children within the node that it's called.
    Complexity: Logarithmic

Sorting descendant nodes

  • void sort_descendants(): Sorts the descendant nodes using the less-than operator of stored_type. This operator must be defined for stored type to use this operation. Sorts all descendants of the node that it's called.
    Complexity: Logarithmic
  • void sort_descendants(const pPred& predicate): Sorts the descendant nodes using the passed prediate function. The predicate function must have the signature:
    void predicate(const stored_type& lhs, const stored_type& rhs)
    Sorts all descendants of the node that it's called.
    Complexity: Logarithmic
  • template<typename T> void sort_descendants(const T& function_object): Sorts the descendant nodes using the function object. The function object should define the call operator with the signature as below.
    bool operator ()(const stored_type& lhs, const stored_type& rhs) const
    Sorts all descendants of the node that it's called.
    Complexity: Logarithmic

The most current version of this library, as well as the version history and more information on the design and operations, can be found here.



Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: November 20, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT Are you wanting to target two or more platforms such as iOS, Android, and/or Windows? You are not alone. 90% of enterprises today are targeting two or more platforms. Attend this eSeminar to discover how mobile app developers can rely on one IDE to create applications across platforms and approaches (web, native, and/or hybrid), saving time, money, and effort and introducing apps to market faster. You'll learn the trade-offs for gaining long …

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds