NAME
OTC_AVLNode -
Base class for nodes within an AVL tree.
SYNOPSIS
#include <OTC/collctn/avlnode.hh>
class OTC_AVLNode : public OTC_MPObject
{
public:
virtual ~OTC_AVLNode();
inline OTC_AVLNode* father() const;
inline OTC_AVLTree* tree() const;
inline OTC_Boolean isRoot() const;
inline OTC_AVLNode* left() const;
inline OTC_AVLNode* right() const;
inline OTC_Boolean isLeft() const;
inline OTC_Boolean isRight() const;
OTC_AVLNode* brother() const;
u_int level() const;
inline u_int count() const;
u_int index() const;
u_int height() const;
void addBefore(OTC_AVLNode* theNode);
void addAfter(OTC_AVLNode* theNode);
void swap(OTC_AVLNode* theNode);
void unlink();
protected:
OTC_AVLNode();
};
CLASS TYPE
Abstract
DESCRIPTION
This class is the base class for nodes within an AVL tree.
All nodes to be placed into such a tree must be derived
from this class.
It is this class which encapsulates all the operations which
can be performed on a tree and nodes within it. Of these
operations, those which involve insertion or deletion of nodes
will automatically rebalance the tree as required.
DESTRUCTION
virtual ~OTC_AVLNode();
Recursively deletes the left and
right subtrees of this node.
A node should only be explicitly
deleted if it is a root node, or
not contained within a tree at all.
If this condition is violated,
an exception is generated.
QUERY
inline OTC_AVLNode* father() const;
Returns the father of this node.
If this node is the root node within
a tree, or isn't contained within
a tree, then 0 is returned.
inline OTC_AVLTree* tree() const;
If the node is contained within a tree,
the pointer to the tree is returned,
otherwise 0 is returned.
inline OTC_Boolean isRoot() const;
Returns OTCLIB_TRUE if this node is a
root node of a tree. Will also return
OTCLIB_TRUE if the node is not contained
within a tree at all.
inline OTC_AVLNode* left() const;
Returns the node which is the root
of the left subtree of this node, or
0 if there is no left subtree.
inline OTC_AVLNode* right() const;
Returns the node which is the root
of the right subtree of this node, or
0 if there is no right subtree.
inline OTC_Boolean isLeft() const;
Returns OTCLIB_TRUE if this node is the
root node of the left subtree of its
father node. This will always return
OTCLIB_FALSE if this node is a root
node, or is not contained within a tree.
inline OTC_Boolean isRight() const;
Returns OTCLIB_TRUE if this node is the
root node of the right subtree of its
father node. This will always return
OTCLIB_FALSE if this node is a root
node, or is not contained within a tree.
OTC_AVLNode* brother() const;
Returns the brother node of this node.
The brother node is the node at the same
level, in the alternate subtree of the
father. If this node is the root node,
or there is no brother node, then 0
is returned.
u_int level() const;
Returns the level of this node in the
tree. The root node has a level of 0.
inline u_int count() const;
Returns the count of the number of nodes
in the tree, plus one, to the left of this
node. Thus for a node with an empty
left subtree, this will return 1.
u_int index() const;
Returns the index of this node in the
tree based on an inorder traversal.
u_int height() const;
Returns the height of the tree rooted
at this node.
MODIFICATION
void addBefore(OTC_AVLNode* theNode);
Adds theNode before this node in the
tree, based on an inorder traversal. Doing
this, will automatcially result in
the tree being rebalanced. Note that
due to the nature of balanced trees,
theNode will not necessarily end up
being the left node of this node.
theNode must not already be in a
tree; if it is, an exception is raised.
void addAfter(OTC_AVLNode* theNode);
Adds theNode after this node in the
tree, based on an inorder traversal.
Doing this, will automatcially result in
the tree being rebalanced. Note that
due to the nature of balanced trees,
theNode will not necessarily end up
being the right node of this node.
theNode must not already be in a
tree; if it is, an exception is raised.
void swap(OTC_AVLNode* theNode);
Swap the location of theNode and
this node. This node must be in a tree,
if it isn't, an exception is raised.
void unlink();
Unlinks this node from the tree and
adjusts the balance of the tree
accordingly. Note that the node is
not deleted, this is the responsibility
of the user after it has been unlinked.
SEE ALSO
OTC_AVLTree
LIBRARY
OTC
AUTHOR(S)
Graham Dumpleton
COPYRIGHT
Copyright 1992 1993 OTC LIMITED
Copyright 1994 DUMPLETON SOFTWARE CONSULTING PTY LIMITED