Rudiments
Public Member Functions | List of all members
avltree< valuetype > Class Template Reference

Public Member Functions

 avltree ()
 
 ~avltree ()
 
void insert (valuetype value)
 
void insert (avltreenode< valuetype > *node)
 
avltreenode< valuetype > * detach (avltreenode< valuetype > *node)
 
bool remove (valuetype value)
 
bool removeAll (valuetype value)
 
bool remove (avltreenode< valuetype > *node)
 
uint64_t getLength () const
 
avltreenode< valuetype > * getTop ()
 
avltreenode< valuetype > * getFirst ()
 
avltreenode< valuetype > * getLast ()
 
avltreenode< valuetype > * getPrevious (avltreenode< valuetype > *node)
 
avltreenode< valuetype > * getNext (avltreenode< valuetype > *node)
 
avltreenode< valuetype > * find (valuetype value)
 
avltreenode< valuetype > * find (avltreenode< valuetype > *startnode, valuetype value)
 
void clear ()
 
void print () const
 

Detailed Description

template<class valuetype>
class avltree< valuetype >

The avltree class allows you to store an arbitrary number of values in a self-sorting, self-balancing binary tree. Since the avltree class is template-based, you can store arbitrary types of values.

Each avltree is composed of a set of avltreenodes. Each avltreenode contains a value.

Constructor & Destructor Documentation

template<class valuetype>
avltree< valuetype >::avltree ( )

Creates an empty instance of the avltree class.

template<class valuetype>
avltree< valuetype >::~avltree ( )

Deletes this instance of the avltree class and all of its avltreenodes. Note however, that the data stored in each avltreenode is not deleted by this call.

Member Function Documentation

template<class valuetype>
void avltree< valuetype >::clear ( )

Deletes all avltreenodes currently in the avltree. Note however, that the data stored in each avltreenode is not deleted by this call.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::detach ( avltreenode< valuetype > *  node)

Detaches "node" from the tree.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::find ( valuetype  value)

Returns a pointer to the first avltreenode containing "value" or NULL if "value" was not found.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::find ( avltreenode< valuetype > *  startnode,
valuetype  value 
)

Returns a pointer to the first avltreenode below "startnode" containing "value" or NULL if "value" was not found.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::getFirst ( )

Returns the first node in the avltree (in an in-order, depth-first traversal).

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::getLast ( )

Returns the last node in the avltree (in an in-order, depth-first traversal).

template<class valuetype>
uint64_t avltree< valuetype >::getLength ( ) const

Returns the number of nodes in the avltree.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::getNext ( avltreenode< valuetype > *  node)

Returns the node after "node" or NULL if this node is the last node in the tree (in an in-order, depth-first traversal). "node" is presumed to be in the tree.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::getPrevious ( avltreenode< valuetype > *  node)

Returns the node prior to "node" or NULL if this node is the first node in the tree (in an in-order, depth-first traversal). "node" is presumed to be in the tree.

template<class valuetype>
avltreenode<valuetype>* avltree< valuetype >::getTop ( )

Returns the top-most node in the avltree.

template<class valuetype>
void avltree< valuetype >::insert ( valuetype  value)

Creates a new avltreenode containing "value" and prepends it to the avltree.

template<class valuetype>
void avltree< valuetype >::insert ( avltreenode< valuetype > *  node)

Inserts already created avltreenode "node" to the avltree.

template<class valuetype>
void avltree< valuetype >::print ( ) const

Prints out an xml-style representation of the avltree.

template<class valuetype>
bool avltree< valuetype >::remove ( valuetype  value)

Deletes the first avltreenode containing "value".

Note that this operation requires a search and is expensive in both execution time and code size.

Returns true on success and false on failure.

template<class valuetype>
bool avltree< valuetype >::remove ( avltreenode< valuetype > *  node)

Removed avltreenode "node" from the avltree.

Note that this operation does not require a search and is far less expensive than the remove(value) operation and removeAll().

Returns true on success and false on failure.

template<class valuetype>
bool avltree< valuetype >::removeAll ( valuetype  value)

Deletes all avltreenodes containing "value".

Note that this operation requires a search and is expensive in both execution time and code size.

Returns true on success and false on failure.