TOP --> libjdl
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;
public CJdlRedBlackTree ( ) ;
Default constructor.
public bool Check ( const char * prefix ) ;
Check the tree. Messages are printed to stdout.
prefix | Prefix spacing for error messages. |
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?
node | The lookup node. |
public bool ContainsKey ( const char * key ) ;
Does this tree contain the following key?
key | The lookup key. |
public CJdlRedBlackTreeEnumerator * Elements ( ) ;
Return an enumeration of the elements in this tree in ascending order.
public CJdlRedBlackTreeEnumerator * Elements ( bool ascending ) ;
Return an enumeration of the elements in this tree in ascending order.
ascending | Boolean specifying the order of the returned list. |
public void * Get ( const char * key ) ;
Get the data associated with a key.
key | The key to retrieve. |
public const char * GetKey ( const char * key ) ;
Get the key address.
key | The key to retrieve. |
public void Insert ( const char * key , void * value ) ;
Insert a new node into the tree.
key | The key for this node. |
value | The value associated with this node. |
public bool IsEmpty ( ) const ;
Does this tree have any nodes?
public void Put ( const char * key , void * value ) ;
Insert a new node into the tree.
key | The key for this node. |
value | The value associated with this node. |
public void Remove ( const char * key ) ;
Remove a node from the tree.
key | The key for the node to delete. |
public uint Size ( ) const ;
The number of nodes in the tree.
public uint GetNumItems ( ) const ;
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.
prefix | const char* used to prefix the status output. |
public void Dump ( ) ;
Dump the contents of the tree.
public void Dump ( const char * prefix ) ;
Dump the contents of the tree.
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.