CNAVLTree -- AVL balanced binary search tree

SYNOPSIS

#include <CNCL/AVLTree.h>

TYPE

CN_CNAVLTREE

BASE CLASSES

CNObject

DERIVED CLASSES

none

RELATED CLASSES

CNAVLNode

DESCRIPTION

CNAVLTree is realizing a generic AVL tree. It contains nodes derived from CNAVLNode and organizes them in a balanced binary search tree. Such Nodes can be added to the tree, searched for and be removed.

CNAVLTree is an abstract base class. It provides the general algorithms needed for AVL trees, but it makes no assumptions on what kind of key the nodes will be sorted by. Usable AVL trees require derived classes that specify the key that will be used.

Constructors:

CNAVLTree();

CNAVLTree(CNParam *param);

Initializes an empty AVL tree.

Destructor:

~CNAVLTree();

Deletes the tree and all CNAVLNode nodes still in the tree.

In addition to the member functions required by CNCL, CNAVLTree provides:

bool add(CNAVLNode*);

Adds a node to the tree. If the key the node is sorted by is already existing in the current AVL tree, FALSE is returned. otherwise TRUE is returned.

CNAVLNode *find();

Searches for a key. This is an abstract functions that may only be called by subclasses of CNAVLTree. The subclasses have to provide new find() functions that manage the key to search for. Returns a pointer to the found CNAVLNode on success and NIL on failure (key not found).

CNAVLNode *remove();

Similar to find(), but the returned node is also removed from the tree.

bool empty();

Returns TRUE if the tree is empty.

void delete_all();

Deletes all nodes still in the tree.

CNAVLNode *find_first();

Returns a pointer to the first node in the tree, i.e. the node with the lowest key. Returns NIL if the tree is empty.

CNAVLNode *remove_first();

Similar to find_first(), but also removes the returned node.

CNAVLNode *get_root();

Returns the root node of the tree or NIL is the tree is empty.

unsigned long length() const;

Returns the number of nodes in the tree.

The following example shows parts of a derived class. It uses simple long keys to sort and find nodes. See also the example for CNAVLNode.

class IntAVLTree : public CNAVLTree
{
    friend class IntAVLNode;

  // ...

  public:	/***** Public interface **************************************/

    virtual CNAVLNode *find(long key);
    virtual CNAVLNode *remove(long key);

  private:	/***** Internal private members ******************************/

    long searchkey;

  // ...
};

// ...

CNAVLNode *IntAVLTree::find(long key) {
    searchkey = key;
    return CNAVLTree::find();
};

CNAVLNode *IntAVLTree::remove(long key) {
    searchkey = key;
    return CNAVLTree::remove();
};

Go to the first, previous, next, last section, table of contents.