CNCL - CNAVLNode

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

CNAVLNode -- Node for CNAVLTree

SYNOPSIS

#include <CNCL/AVLNode.h>

TYPE

CN_AVLNODE

BASE CLASSES

CNObject

DERIVED CLASSES

none

DESCRIPTION

CNAVLNode is an abstract base class for nodes of AVL trees.

Derived classes must be implemented for different key types. They must be able to compare their keys between two node and between a node and the serached key of the tree.

Constructors:

CNAVLNode();
CNAVLNode(CNParam *param);: Initializes a new AVL node.

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

virtual int compare(CNAVLNode*) = 0;: Compares the node's key with another node's key. Returns -1 if the current node's key is lower, 1 of it's higher and 0 if it's equal to the other node's key.
virtual int find(CNAVLTree*) = 0;: Compares the node's key with the current search key. Returns -1 if the current node's key is lower, 1 of it's higher and 0 if it's equal to the searched key. Derived tree classes must provide a possibility for nodes to get the currently searched tree key, e.g. as a member variable in the tree structure.
CNAVLNode *left();: Returns the root of the left sub-tree (lower keys) or NIL if there is no left sub-tree.
CNAVLNode *right();: Returns the root of the right sub-tree (higher keys) or NIL if there is no right sub-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 CNAVLTree.

class IntAVLNode : public CNAVLNode
{
  public:	/***** Constructors ******************************************/

    IntAVLNode(long key): key_(key) {};

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

    virtual int compare(CNAVLNode*); // compare node with another one
    virtual int find(CNAVLTree*);    // compare node with searched key  
    long get_key() { return key_; };

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

    long key_;

  // ...

};

// ...

int IntAVLNode::compare(CNAVLNode *n) {
    long c = IntAVLNode::cast_from_object(n)->key_;
    if (key_ < c) return -1;
    if (key_ > c) return  1;
    return 0;
};

int IntAVLNode::find(CNAVLTree *t) {
    long c = IntAVLTree::cast_from_object(t)->searchkey;
    if (key_ < c) return -1;
    if (key_ > c) return  1;
    return 0;
};