This class defines a red-black tree object.

These objects store key/value pairs in much the same way as a hashtable but have different storage and retrieval characteristics.

Red-black trees perform get/put operations in O(log(n)) time whereas the best case performance for hashtables is O(k) where k is a constant and the worst case performance for get/put operations could be as bad as O(n).

This means that red-black trees are a good choice for handling an unknown range of key/value pairs where the range may differ by several orders of magnitude.

They are also a good choice for handling bucket overflows in hashtables.

A simple usage for this class is shown below:

    CJdlRedBlackTree tree = new CJdlRedBlackTree();
    if(!tree.IsEmpty()) {
        cout << "ERROR: #1" << endl;
    }
    tree.Put("C","This is the value data for C");
    tree.Put("A","This is the value data for A");
    tree.Put("B","This is the value data for B");
    if(tree.Size() != 3) {
        cout << "ERROR: #2" << endl;
    }
    if(tree.Contains("A")) {
        String val = (String) tree.get("A");
    }
    tree.Remove("B");

    // Enumerate over the nodes in the tree.
    CJdlRedBlackTreeEnumerator* e = tree.Elements();
    {for(;e->HasMoreElements();) {
      CJdlRedBlackTree* nd = e->NextElement();
      cout << nd->GetKey() << endl;
    }}
    delete e;

Author:

Joe Linoff

Version:

$Id: jdlrbtree.h,v 1.3 1999/06/12 18:26:00 jdl Exp $

Source:

../../libjdl/src/jdlrbtree.h:74

See Also:

CJdlRedBlackTreeNode, CJdlRedBlackTreeEnumerator, CJdlHashTable

public CJdlRedBlackTree ( ) ;

Default constructor.

public bool Check ( const char * prefix ) ;

Check the tree. Messages are printed to stdout.

Return:

true if the tree is ok false otherwise.

public void Clear ( ) ;

Clear out the tree.

This method walks through every node in the tree and deletes it. The key values are not affected.

public CJdlRedBlackTree * Clone ( ) ;

Clone this tree.

The key values are not cloned.

public bool Contains ( CJdlRedBlackTreeNode * node ) ;

Does this tree contain the following node?

Return:

true if the tree contains this node or false otherwise.

public bool ContainsKey ( const char * key ) ;

Does this tree contain the following key?

Return:

true if the tree contains this key or false otherwise.

public CJdlRedBlackTreeEnumerator * Elements ( ) ;

Return an enumeration of the elements in this tree in ascending order.

Return:

An enumeration of the elements.

public CJdlRedBlackTreeEnumerator * Elements ( bool ascending ) ;

Return an enumeration of the elements in this tree in ascending order.

Return:

An enumeration of the elements in ascending or descending order.

public void * Get ( const char * key ) ;

Get the data associated with a key.

Return:

0 if the key does not exist. If you are storing numbers in the tree, you should used containsKey() to do an existence check first.

public const char * GetKey ( const char * key ) ;

Get the key address.

Return:

0 if the key does not exist.

public void Insert ( const char * key ,
                     void * value ) ;

Insert a new node into the tree.

public bool IsEmpty ( ) const ;

Does this tree have any nodes?

Return:

true if there are no nodes or false if there are.

public void Put ( const char * key ,
                  void * value ) ;

Insert a new node into the tree.

public void Remove ( const char * key ) ;

Remove a node from the tree.

public uint Size ( ) const ;

The number of nodes in the tree.

Return:

The number of NODEs in the tree.

public uint GetNumItems ( ) const ;

The number of nodes in the tree.

Return:

The number of NODEs in the tree.

public void DumpStats ( const char * prefix ) ;

Report tree statistics. This routine prints out the number of nodes, the maximum height and the minimum height for the tree whose root is this node. It also prints out 2*log(N) which is the maximum possible theoretical height.

public void Dump ( ) ;

Dump the contents of the tree.

public void Dump ( const char * prefix ) ;

Dump the contents of the tree.