Google

TOP --> libjdl

class CJdlRedBlackTree

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

Constructors Index

CJdlRedBlackTree
[public] Default constructor.


Methods Index

Check
[public] Check the tree. Messages are printed to stdout.
Clear
[public] Clear out the tree.
Clone
[public] Clone this tree.
Contains
[public] Does this tree contain the following node?
ContainsKey
[public] Does this tree contain the following key?
Dump
[public] Dump the contents of the tree.
Dump
[public] Dump the contents of the tree.
DumpStats
[public] 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.
Elements
[public] Return an enumeration of the elements in this tree in ascending order.
Elements
[public] Return an enumeration of the elements in this tree in ascending order.
Get
[public] Get the data associated with a key.
GetKey
[public] Get the key address.
GetNumItems
[public] The number of nodes in the tree.
Insert
[public] Insert a new node into the tree.
IsEmpty
[public] Does this tree have any nodes?
Put
[public] Insert a new node into the tree.
Remove
[public] Remove a node from the tree.
Size
[public] The number of nodes in the tree.


Constructors

CJdlRedBlackTree

public CJdlRedBlackTree ( ) ;

Default constructor.


Methods

Check

public bool Check ( const char * prefix ) ;

Check the tree. Messages are printed to stdout.

Parameters:
prefix Prefix spacing for error messages.

Return:
true if the tree is ok false otherwise.

Clear

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.

Clone

public CJdlRedBlackTree * Clone ( ) ;

Clone this tree.

The key values are not cloned.

Contains

public bool Contains ( CJdlRedBlackTreeNode * node ) ;

Does this tree contain the following node?

Parameters:
node The lookup node.

Return:
true if the tree contains this node or false otherwise.

ContainsKey

public bool ContainsKey ( const char * key ) ;

Does this tree contain the following key?

Parameters:
key The lookup key.

Return:
true if the tree contains this key or false otherwise.

Elements

public CJdlRedBlackTreeEnumerator * Elements ( ) ;

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

Return:
An enumeration of the elements.

Elements

public CJdlRedBlackTreeEnumerator * Elements ( bool ascending ) ;

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

Parameters:
ascending Boolean specifying the order of the returned list.

Return:
An enumeration of the elements in ascending or descending order.

Get

public void * Get ( const char * key ) ;

Get the data associated with a key.

Parameters:
key The key to retrieve.

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.

GetKey

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

Get the key address.

Parameters:
key The key to retrieve.

Return:
0 if the key does not exist.

Insert

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

Insert a new node into the tree.

Parameters:
key The key for this node.
value The value associated with this node.

IsEmpty

public bool IsEmpty ( ) const ;

Does this tree have any nodes?

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

Put

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

Insert a new node into the tree.

Parameters:
key The key for this node.
value The value associated with this node.

Remove

public void Remove ( const char * key ) ;

Remove a node from the tree.

Parameters:
key The key for the node to delete.

Size

public uint Size ( ) const ;

The number of nodes in the tree.

Return:
The number of NODEs in the tree.

GetNumItems

public uint GetNumItems ( ) const ;

The number of nodes in the tree.

Return:
The number of NODEs in the tree.

DumpStats

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.

Parameters:
prefix const char* used to prefix the status output.

Dump

public void Dump ( ) ;

Dump the contents of the tree.

Dump

public void Dump ( const char * prefix ) ;

Dump the contents of the tree.

Parameters:
prefix A user specified prefix.

This documentation was generated automatically by the ccdoc tool (version 0.7a).
Click here to submit a bug report or feature request.

Click here to return to the top of the page.