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:

1. Every node is either red or black.
2. Every leaf (0) is black.
3. If a node is red, then both its children are black.
4. 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();

    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

public CJdlRedBlackTreeNode ( const char * key ,
                              void * value ) ;

Construct a simple node for later insertion into a tree.

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.

public CJdlRedBlackTreeNode ( const char * key ,
                              void * value ,
                              CJdlRedBlackTreeNode * parent ,
                              CJdlRedBlackTreeNode * left ,
                              CJdlRedBlackTreeNode * right ,
                              COLOR color ) ;

Private generic constructor.

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) {
      .
      .
    }

Return:

The left child node.

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.

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.

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.

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.

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.

public bool IsRed ( ) const ;

Is this node red?

Return:

true if this node is RED or false if this node is BLACK.

public bool IsBlack ( ) const ;

Is this node black?

Return:

true if this node is BLACK or false if this node is RED.

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.

Return:

Non zero if this key is contained in the subtree or 0 otherwise.

public CJdlRedBlackTreeNode * Get ( const char * key ) ;

Get the node corresponding to this key.

Return:

The node associated with this key or 0 if no node with this key exists.

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

Return:

The new root of the tree if a rotation occurred or the old root if no change occurred.

public CJdlRedBlackTreeNode * Insert ( CJdlRedBlackTreeNode * node ) ;

Insert this node into the specified tree.

Return:

The new root if the tree was rotated.

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).

public bool IsLeftChild ( ) const ;

Is this node the left child of the parent?

Return:

true if it is the left child or false otherwise.

public bool IsRightChild ( ) const ;

Is this node the right child of the parent?

Return:

true if it is the right child or false otherwise.

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.

public bool IsRoot ( ) const ;

Is this node a root?

Return:

true if this node is a root (no parent) or false otherwise.

public CJdlRedBlackTreeNode * GetSuccessor ( ) ;

Find the successor node.

public CJdlRedBlackTreeNode * GetPredecessor ( ) ;

Find the predecessor node.

public CJdlRedBlackTreeNode * GetMinimum ( ) ;

Find the minimum node.

Return:

The minimum node in the tree.

public CJdlRedBlackTreeNode * GetMaximum ( ) ;

Find the maximum node.

Return:

The maximum node in the tree.

public CJdlRedBlackTreeNode * Remove ( CJdlRedBlackTreeNode * inRoot ) ;

Remove this node from the tree.

Return:

The root of the tree after the remove operation.

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.

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.

Return:

true if the tree is ok or false otherwise.