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

◆ avltree()

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

Creates an empty instance of the avltree class.

◆ ~avltree()

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

◆ clear()

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.

◆ detach()

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

Detaches "node" from the tree.

◆ find() [1/2]

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.

◆ find() [2/2]

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.

◆ getFirst()

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

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

◆ getLast()

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

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

◆ getLength()

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

Returns the number of nodes in the avltree.

◆ getNext()

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.

◆ getPrevious()

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.

◆ getTop()

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

Returns the top-most node in the avltree.

◆ insert() [1/2]

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

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

◆ insert() [2/2]

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

Inserts already created avltreenode "node" to the avltree.

◆ print()

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

Prints out an xml-style representation of the avltree.

◆ remove() [1/2]

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.

◆ remove() [2/2]

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.

◆ removeAll()

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.