TOP --> libjdl
This class defines red and black nodes in the CJdlRedBlackTree.
When used properly, these nodes enforce the four properties of red-black trees for all operations:
The code fragment below shows how to use these objects to construct a tree. Normally you would use the CJdlRedBlackTree object but this is useful for understanding how this object works.
CJdlRedBlackTreeNode* tree = 0; tree = new CJdlRedBlackTreeNode("X",0); tree = tree->Insert(new CJdlRedBlackTreeNode("W",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("C",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("A",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("N",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("B",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("P",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("M",0)); tree = tree->Insert(new CJdlRedBlackTreeNode("E",0));A more complete discussion of the algorithms contained herein can be found in:CJdlRedBlackTreeNode* nd;
// ascending order for(nd=tree.GetMinimum();nd!=0;nd = nd.GetSuccessor()) { cout << nd.GetKey() << endl; }
// descending order for(nd=tree.GetMaximum();nd!=0;nd = nd.predecessor()) { cout << nd.GetKey() << endl; }
// search if(tree.contains("M")) { nd = tree.Get("M"); }
// statistics tree.DumpStats();
// debugging tree.Dump();
Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. Introduction to Algorithms. The MIT Press, McGraw-Hill, 1995.Robert Sedgewick. Algorithms. Addison-Wesley, second edition, 1988.
public CJdlRedBlackTreeNode ( const char * key , void * value ) ;
Construct a simple node for later insertion into a tree.
key | The retrieval key value. |
value | The value to store. |
public CJdlRedBlackTreeNode ( const char * key , void * value , CJdlRedBlackTreeNode * parent , POSITION pos ) ;
Construct a node with linkage information for building debugging records. This constructor should only be used by test programs.
key | The retrieval key value. |
value | The value to store. |
parent | The parent node. |
position | This childs orientation from the parent: LEFT or RIGHT. |
public CJdlRedBlackTreeNode ( const char * key , void * value , CJdlRedBlackTreeNode * parent , CJdlRedBlackTreeNode * left , CJdlRedBlackTreeNode * right , COLOR color ) ;
Private generic constructor.
key | The retrieval key value. |
value | The value to store. |
parent | The parent node. |
left | The left child node. |
right | The right child node. |
color | This nodes color: RED or BLACK. or if the color is not valid. |
public ~ CJdlRedBlackTreeNode ( ) ;
Destructor
public enum COLOR { RED , BLACK } ;
The color of the node.
public enum POSITION { LEFT , RIGHT } ;
Used to specify the position of child nodes.
public CJdlRedBlackTreeNode * GetLeftNode ( ) const ;
Return the left child node. The user must check the return node to see whether it is 0.
CJdlRedBlackTreeNode* nd = tree.getLeftNode(); if(nd) { . . }
public CJdlRedBlackTreeNode * GetRightNode ( ) const ;
Return the right child node. The user must check the return node to see whether it is 0.
CJdlRedBlackTreeNode* nd = tree.GetRightNode(); if(nd) { . . }
public CJdlRedBlackTreeNode * GetParentNode ( ) const ;
Return the parent node. The user must check the return node to see whether it is 0.
CJdlRedBlackTreeNode* nd = tree.GetParentNode(); if(nd) { . . }
public CJdlRedBlackTreeNode * GetGrandParentNode ( ) const ;
Return the grand parent node. The user must check the return node to see whether it is 0.
CJdlRedBlackTreeNode* nd = tree.GetGrandParentNode(); if(nd) { . . }
public CJdlRedBlackTreeNode * GetSiblingNode ( ) const ;
Return the sibling node. The user must check the return node to see whether it is 0.
CJdlRedBlackTreeNode* nd = tree.GetSiblingNode(); if(nd) { . . }
public CJdlRedBlackTreeNode * GetUncleNode ( ) const ;
Who is the uncle to x? The user must check the return node to see whether it is 0.
+---+ | g | +---+ / \ +---+ +---+ | p | | u | <=== UNCLE +---+ +---+ / +---+ | x | +---+
public bool IsRed ( ) const ;
Is this node red?
public bool IsBlack ( ) const ;
Is this node black?
public void RotateLeft ( ) ;
Rotate this node to the left. This node is x.
Left rotate+---+ +---+ | x | | y | +---+ Left Rot. +---+ / \ --------------> / \ A +---+ +---+ C | y | | x | +---+ +---+ / \ / \ B C A B
public void RotateRight ( ) ;
Rotate this node to the right. This node is y.
Right rotate+---+ +---+ | y | | x | +---+ Right Rot. +---+ / \ --------------> / \ +---+ C A +---+ | x | | y | +---+ +---+ / \ / \ A B B C
public const char * GetKey ( ) const ;
Get the node key value.
public void * GetValue ( ) const ;
Get the node value.
public bool Contains ( const char * key ) ;
Find out whether the tree rooted at this node contains the specified key.
key | The key name. |
public CJdlRedBlackTreeNode * Get ( const char * key ) ;
Get the node corresponding to this key.
key | The key name. |
public void BinaryTreeInsert ( CJdlRedBlackTreeNode * nd ) ;
Insert this node into the tree as though it were a simple binary tree. We will clean it up later.
public CJdlRedBlackTreeNode * InsertFixup ( CJdlRedBlackTreeNode * root ) ;
Fixup the red-black tree after a binary tree insertion. This method corrects for the following six cases.
Case Uncle Parent This Comments ==== ===== ====== ====== ================ 1 red ? ? Don't care about parent and this. 2 black left right Forces 3 as well. 3 black left left 4 red ? ? Same as 1 but here for completeness. 5 black right left Forces 6 as well. 6 black right right
root | The root of the tree. |
public CJdlRedBlackTreeNode * Insert ( CJdlRedBlackTreeNode * node ) ;
Insert this node into the specified tree.
node | The node to Insert into the tree. |
public bool UncleIsRed ( ) const ;
Is the uncle RED?
public bool IsLeftChild ( ) const ;
Is this node the left child of the parent?
public bool IsRightChild ( ) const ;
Is this node the right child of the parent?
public bool IsLeaf ( ) const ;
Is this node a leaf?
public bool IsRoot ( ) const ;
Is this node a root?
public CJdlRedBlackTreeNode * GetSuccessor ( ) ;
Find the successor node.
public CJdlRedBlackTreeNode * GetPredecessor ( ) ;
Find the predecessor node.
public CJdlRedBlackTreeNode * GetMinimum ( ) ;
Find the minimum node.
public CJdlRedBlackTreeNode * GetMaximum ( ) ;
Find the maximum node.
public CJdlRedBlackTreeNode * Remove ( CJdlRedBlackTreeNode * inRoot ) ;
Remove this node from the tree.
The | current root of the tree. |
public void DumpStats ( const char * prefix ) const ;
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 | String used to prefix the status output. |
public void Dump ( ) const ;
Dump the contents of the tree rooted at this node.
public void Dump ( const char * prefix ) const ;
Dump the contents of the tree rooted at this node.
public bool Check ( const char * prefix ) ;
Check the properties of the subtree. Messages are printed to System.out.
prefix | Prefix spacing for error messages. |
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.