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;
CJdlRedBlackTree
Check
Clear
Clone
Contains
ContainsKey
Dump
Dump
DumpStats
Elements
Elements
Get
GetKey
GetNumItems
Insert
IsEmpty
Put
Remove
Size
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.