xavax::Tree<T>

Xavax C++ Library

Class xavax::Tree<T>

Tree<T> is a template class for containers that store elements of type T by value. The elements are stored in a balanced binary tree. A binary tree is considered balanced if the height of the subtrees of each node do not differ by more than one level.

Tree<T> can access any element of the collection by key value or position in O(log₂n) time where n is the collection size. This compares favorably with containers which require O(n) time such as DList<T>. For example, when searching a collection of 1000 elements, DList would traverse an average of 500 elements while Tree would traverse no more than 11 elements. However, this performance comes with a price. When inserting and removing elements, rotations must be performed to keep the tree balanced. Insertion can result in a single or double rotation while removal can result in multiple rotations as the change in subtree height propagates up the tree. The following diagram illustrates the two basic rotation types.

Tree<T> is an ordered collection; therefore, it requires a means of comparing two elements or an element and a key. The client may provide a compare functor and this is highly recommended as it can result in improved performance. If the client does not provide a compare functor, then type T must implement operator== and operator< so that PTree<T> can generate a default compare functor.

Since Tree<T> stores elements by value, type T must provide a copy constructor and implement operator=. Due to the overhead of storing elements by value, this container is only recommended for storing native types and small objects. For larger objects, consider using PTree<T> which stores objects by reference. PTree also does not require type T to have a copy constructor or implement operator=.

Constructor Summary

Tree(CompareFunctor<T>* compareFunctor = defaultCompareFunctor)
Construct an empty tree.

Method Summary

void clear()
         Remove all elements in the tree.

size_t count() const
         Returns the number of elements in the tree.

void insert(const T& t)
         Insert object t of type T into the tree.

T* locate(const T& key)
         Locate and return a pointer to the element at position p.

T* locate(size_t p)
         Locate and return a pointer to the element at position p.

void remove(const T* key)
         Remove the element matching key.

void remove(size_t p)
         Remove the element at position p.

void traverse(TraversalOrder order, void (proc)(T*,void*), void* data)
         Traverse the tree in the specified order calling proc for each element.

Related Classes

TreeConstIterator<T>, TreeIterator<T>, PTree<T>

Constructor Detail

Tree<T>

Tree<T>(CompareFunctor<T>*
compareFunctor = defaultCompareFunctor)

Construct an empty tree.

Parameters:: compareFunctor - a function that compares two objects of type T. If a compare functor is not provided, the default compare functor is used.

Method Detail

clear

void clear()

Remove all objects from the tree.

count

size_t count() const

Return the number of elements in this tree.

Returns:: the number of elements in this tree.

insert

void insert(const T& t)

Insert object t of type T into the tree.

Parameters:: t - the object to be inserted.

locate

T* locate(const T& key)

Locate and return a pointer to the element matching key.

Parameters:: key - a key which the retrieved item must match.

Returns:: a pointer to the element matching key, or null if no match was found.

locate

T* locate(size_t p)

Locate and return a pointer to the element at position p in the tree. The first element is at position 0.

Parameters:: p - the position of the object to be retrieved.

Returns:: a pointer to the element at position p if the tree contains at least p+1 elements; otherwise, null.

remove

void remove(const T& key)

Remove the element matching key.

Parameters:: key - an object that matches the object to be removed.

remove

void remove(size_t p)

Remove the element at position p in the tree.

Parameters:: p - the position of the object to be removed.

Throws:: RangeException - if the tree contains fewer than p+1 elements.

traverse

void traverse(TraversalOrder
order, void (proc)(T*,void*), void* data);

Traverse the tree in the specified order calling proc for each element.

Parameters:: order - the order of the traversal.; proc - the function to be called for each element.; data - can be used to pass client data to proc.

Example Code

Method Summary
`void`	`clear()` Remove all elements in the tree.
`size_t`	`count() const` Returns the number of elements in the tree.
`void`	`insert(const T& t)` Insert object t of type T into the tree.
`T*`	`locate(const T& key)` Locate and return a pointer to the element at position p.
`T*`	`locate(size_t p)` Locate and return a pointer to the element at position p.
`void`	`remove(const T* key)` Remove the element matching `key`.
`void`	`remove(size_t p)` Remove the element at position p.
`void`	`traverse(TraversalOrder order, void (proc)(T,void), void* data)` Traverse the tree in the specified order calling proc for each element.

Related Classes
TreeConstIterator<T>, TreeIterator<T>, PTree<T>