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));
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();
A more complete discussion of the algorithms contained herein can
be found in:
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.
CJdlRedBlackTreeNode
CJdlRedBlackTreeNode
CJdlRedBlackTreeNode
~CJdlRedBlackTreeNode
COLOR
POSITION
BinaryTreeInsert
Check
Contains
Dump
Dump
DumpStats
Get
GetGrandParentNode
GetKey
GetLeftNode
GetMaximum
GetMinimum
GetParentNode
GetPredecessor
GetRightNode
GetSiblingNode
GetSuccessor
GetUncleNode
GetValue
Insert
InsertFixup
IsBlack
IsLeaf
IsLeftChild
IsRed
IsRightChild
IsRoot
Remove
RotateLeft
RotateRight
UncleIsRed
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.