TOP --> libjdl
- class CJdlRedBlackTreeNode
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:
- Every node is either red or black.
- Every leaf (0) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendent leaf contains the
same number of black nodes.
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.
- Author:
-
Joe Linoff
- Version:
-
$Id: jdlrbtreenode.h,v 1.3 1999/06/12 18:26:00 jdl Exp $
- Source:
-
../../libjdl/src/jdlrbtreenode.h:87
- See Also:
-
CJdlRedBlackTree
CJdlRedBlackTreeNode
- [public] Construct a simple node for later insertion into a tree.
CJdlRedBlackTreeNode
- [public] Construct a node with linkage information for building debugging records.
This constructor should only be used by test programs.
CJdlRedBlackTreeNode
- [public] Private generic constructor.
~CJdlRedBlackTreeNode
- [public] Destructor
COLOR
- [public] The color of the node.
POSITION
- [public] Used to specify the position of child nodes.
BinaryTreeInsert
- [public] Insert this node into the tree as though it were a simple binary tree.
We will clean it up later.
Check
- [public] Check the properties of the subtree.
Messages are printed to System.out.
Contains
- [public] Find out whether the tree rooted at this node
contains the specified key.
Dump
- [public] Dump the contents of the tree rooted at this node.
Dump
- [public] Dump the contents of the tree rooted at this node.
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.
Get
- [public] Get the node corresponding to this key.
GetGrandParentNode
- [public] Return the grand parent node.
The user must check the return node to see whether it is 0.
GetKey
- [public] Get the node key value.
GetLeftNode
- [public] Return the left child node.
The user must check the return node to see whether it is 0.
GetMaximum
- [public] Find the maximum node.
GetMinimum
- [public] Find the minimum node.
GetParentNode
- [public] Return the parent node.
The user must check the return node to see whether it is 0.
GetPredecessor
- [public] Find the predecessor node.
GetRightNode
- [public] Return the right child node.
The user must check the return node to see whether it is 0.
GetSiblingNode
- [public] Return the sibling node.
The user must check the return node to see whether it is 0.
GetSuccessor
- [public] Find the successor node.
GetUncleNode
- [public] Who is the uncle to x?
The user must check the return node to see whether it is 0.
GetValue
- [public] Get the node value.
Insert
- [public] Insert this node into the specified tree.
InsertFixup
- [public] Fixup the red-black tree after a binary tree insertion. This method
corrects for the following six cases.
IsBlack
- [public] Is this node black?
IsLeaf
- [public] Is this node a leaf?
IsLeftChild
- [public] Is this node the left child of the parent?
IsRed
- [public] Is this node red?
IsRightChild
- [public] Is this node the right child of the parent?
IsRoot
- [public] Is this node a root?
Remove
- [public] Remove this node from the tree.
RotateLeft
- [public] Rotate this node to the left.
This node is x.
RotateRight
- [public] Rotate this node to the right.
This node is y.
UncleIsRed
- [public] Is the uncle RED?
CJdlRedBlackTreeNode
public CJdlRedBlackTreeNode ( const char * key ,
void * value ) ;
Construct a simple node for later insertion into a tree.
- Parameters:
-
key
| The retrieval key value.
| value
| The value to store.
|
CJdlRedBlackTreeNode
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.
- Parameters:
-
key
| The retrieval key value.
| value
| The value to store.
| parent
| The parent node.
| position
| This childs orientation from the parent: LEFT or RIGHT.
|
CJdlRedBlackTreeNode
public CJdlRedBlackTreeNode ( const char * key ,
void * value ,
CJdlRedBlackTreeNode * parent ,
CJdlRedBlackTreeNode * left ,
CJdlRedBlackTreeNode * right ,
COLOR color ) ;
Private generic constructor.
- Parameters:
-
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.
|
CJdlRedBlackTreeNode
public ~ CJdlRedBlackTreeNode ( ) ;
Destructor
COLOR
public enum COLOR { RED ,
BLACK } ;
The color of the node.
POSITION
public enum POSITION { LEFT ,
RIGHT } ;
Used to specify the position of child nodes.
GetLeftNode
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) {
.
.
}
- Return:
-
The left child node.
GetRightNode
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) {
.
.
}
- Return:
-
The right child node.
GetParentNode
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) {
.
.
}
- Return:
-
The parent node.
GetGrandParentNode
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) {
.
.
}
- Return:
-
The grand parent node.
GetSiblingNode
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) {
.
.
}
- Return:
-
The sibling node.
GetUncleNode
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 |
+---+
- Return:
-
The uncle node.
IsRed
public bool IsRed ( ) const ;
Is this node red?
- Return:
-
true if this node is RED or false if this node is BLACK.
IsBlack
public bool IsBlack ( ) const ;
Is this node black?
- Return:
-
true if this node is BLACK or false if this node is RED.
RotateLeft
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
RotateRight
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
GetKey
public const char * GetKey ( ) const ;
Get the node key value.
GetValue
public void * GetValue ( ) const ;
Get the node value.
Contains
public bool Contains ( const char * key ) ;
Find out whether the tree rooted at this node
contains the specified key.
- Parameters:
-
- Return:
-
Non zero if this key is contained in the subtree or 0 otherwise.
Get
public CJdlRedBlackTreeNode * Get ( const char * key ) ;
Get the node corresponding to this key.
- Parameters:
-
- Return:
-
The node associated with this key or 0 if no node with this
key exists.
BinaryTreeInsert
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.
InsertFixup
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
- Parameters:
-
root
| The root of the tree.
|
- Return:
-
The new root of the tree if a rotation occurred
or the old root if no change occurred.
Insert
public CJdlRedBlackTreeNode * Insert ( CJdlRedBlackTreeNode * node ) ;
Insert this node into the specified tree.
- Parameters:
-
node
| The node to Insert into the tree.
|
- Return:
-
The new root if the tree was rotated.
UncleIsRed
public bool UncleIsRed ( ) const ;
Is the uncle RED?
- Return:
-
true if the uncle is red or false otherwise.
If the uncle node is 0, zero is returned (e.g.,
it is assumed to be black).
IsLeftChild
public bool IsLeftChild ( ) const ;
Is this node the left child of the parent?
- Return:
-
true if it is the left child or false otherwise.
IsRightChild
public bool IsRightChild ( ) const ;
Is this node the right child of the parent?
- Return:
-
true if it is the right child or false otherwise.
IsLeaf
public bool IsLeaf ( ) const ;
Is this node a leaf?
- Return:
-
true if this node is a leaf (no left and right children) or
false otherwise.
IsRoot
public bool IsRoot ( ) const ;
Is this node a root?
- Return:
-
true if this node is a root (no parent) or
false otherwise.
GetSuccessor
public CJdlRedBlackTreeNode * GetSuccessor ( ) ;
Find the successor node.
GetPredecessor
public CJdlRedBlackTreeNode * GetPredecessor ( ) ;
Find the predecessor node.
GetMinimum
public CJdlRedBlackTreeNode * GetMinimum ( ) ;
Find the minimum node.
- Return:
-
The minimum node in the tree.
GetMaximum
public CJdlRedBlackTreeNode * GetMaximum ( ) ;
Find the maximum node.
- Return:
-
The maximum node in the tree.
Remove
public CJdlRedBlackTreeNode * Remove ( CJdlRedBlackTreeNode * inRoot ) ;
Remove this node from the tree.
- Parameters:
-
The
| current root of the tree.
|
- Return:
-
The root of the tree after the remove operation.
DumpStats
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.
- Parameters:
-
prefix
| String used to prefix the status output.
|
Dump
public void Dump ( ) const ;
Dump the contents of the tree rooted at this node.
Dump
public void Dump ( const char * prefix ) const ;
Dump the contents of the tree rooted at this node.
Check
public bool Check ( const char * prefix ) ;
Check the properties of the subtree.
Messages are printed to System.out.
- Parameters:
-
prefix
| Prefix spacing for error messages.
|
- Return:
-
true if the tree is ok or false otherwise.
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.
|