NAME
OTC_AVLTree -
The root class of a height balanced AVL tree.
SYNOPSIS
#include <OTC/collctn/avltree.hh>
class OTC_AVLTree : public OTC_Resource
{
public:
static os_typespec* get_os_typespec();
~OTC_AVLTree();
OTC_AVLTree();
inline OTC_Boolean isEmpty() const;
inline u_int population() const;
void removeAll();
inline OTC_AVLNode* root() const;
void addRoot(OTC_AVLNode* theNode);
int depth() const;
OTC_AVLNode* node(u_int theIndex) const;
};
CLASS TYPE
Concrete
DESCRIPTION
This class is the root class of a height balanced AVL tree.
It is this class which holds the root node in the tree and
maintains the population count for the tree.
The generic AVL tree structure does not actually provide the
capability to hold any items. Instead it only maintains the
balance of the tree and ensures the integrity of the tree
structure. In order for the tree structure to actually hold
items, a specific node class must be derived from the
OTC_AVLNode class. An example of such a class is the
OTC_AVLLinkNode class, which holds a pointer to a link
within a linked list.
DESTRUCTION
~OTC_AVLTree();
Deletes all nodes in the tree.
OTC_AVLTree();
Creates an empty tree. When the tree
is empty, the user must explicitly add
the initial root node.
inline OTC_Boolean isEmpty() const;
Returns OTCLIB_TRUE if the tree is empty.
inline u_int population() const;
Returns the number of nodes in the tree.
void removeAll();
Removes and deletes all nodes in the tree.
inline OTC_AVLNode* root() const;
Returns the root node, or 0 if the tree
is empty.
void addRoot(OTC_AVLNode* theNode);
Adds the initial root node to the tree
and sets the population count to 1.
If this is invoked when the tree is not
empty, an exception is raised.
int depth() const;
Returns the depth of the tree. A tree
with a single root node is regarded as
having a depth of 0. If the tree is
empty, then -1 is returned.
OTC_AVLNode* node(u_int theIndex) const;
If the tree is empty, then 0 is returned.
Otherwise the node with index theIndex,
based on an inorder traversal, is returned.
Indexes start at 0.
SEE ALSO
OTC_AVLNode, OTC_AVLLinkNode
LIBRARY
OTC
AUTHOR(S)
Graham Dumpleton
COPYRIGHT
Copyright 1992 1993 OTC LIMITED
Copyright 1994 DUMPLETON SOFTWARE CONSULTING PTY LIMITED