static OrderedTree() {
     // set up the sentinel node. the sentinel node is the key to a successfull
     // implementation and for understanding the red-black tree properties.
     sentinelNode = new OrderedTreeNode();
     sentinelNode.Left = sentinelNode.Right = sentinelNode;
     sentinelNode.Parent = null;
     sentinelNode.Color = OrderedTreeNode.BLACK;
 }

        public object this[IComparable key] {
            get {
                return GetData(key);
            }
            set {
                if(key == null)
                    throw new ArgumentNullException("key");
                
                // traverse tree - find where node belongs
                int result = 0;
                // create new node
                OrderedTreeNode node = new OrderedTreeNode();
                OrderedTreeNode temp = rbTree; // grab the rbTree node of the tree

                while(temp != sentinelNode) {
                    // find Parent
                    node.Parent = temp;
                    result = key.CompareTo(temp.Key);
                    if(result == 0) {
                        lastNodeFound = temp;
                        temp.Data = value;
                        return;
                    }
                    if(result > 0)
                        temp = temp.Right;
                    else
                        temp = temp.Left;
                }
                
                // setup node
                node.Key = key;
                node.Data = value;
                node.Left = sentinelNode;
                node.Right = sentinelNode;

                // insert node into tree starting at parent's location
                if(node.Parent != null) {
                    result = node.Key.CompareTo(node.Parent.Key);
                    if(result > 0)
                        node.Parent.Right = node;
                    else
                        node.Parent.Left = node;
                }
                else
                    rbTree = node; // first node added

                RestoreAfterInsert(node); // restore red-black properities

                lastNodeFound = node;
                
                intCount = intCount + 1;
            }
        }

 ///<summary>
 /// Determine order, walk the tree and push the nodes onto the stack
 ///</summary>
 public OrderedTreeEnumerator(OrderedTreeNode tnode, bool keys, bool ascending, OrderedTreeNode sentinelNode) {
     this.sentinelNode = sentinelNode;
     stack = new Stack();
     this.keys = keys;
     this.ascending = ascending;
     this.tnode = tnode;
     Reset();            
 }

        ///<summary>
        /// RestoreAfterDelete
        /// Deletions from red-black trees may destroy the red-black 
        /// properties. Examine the tree and restore. Rotations are normally 
        /// required to restore it
        ///</summary>
        private void RestoreAfterDelete(OrderedTreeNode x) {
            // maintain Red-Black tree balance after deleting node          

            OrderedTreeNode y;

            while(x != rbTree && x.Color == OrderedTreeNode.BLACK) {
                if(x == x.Parent.Left) { // determine sub tree from parent
                    y = x.Parent.Right; // y is x's sibling 
                    if(y.Color == OrderedTreeNode.RED) { 
                        // x is black, y is red - make both black and rotate
                        y.Color = OrderedTreeNode.BLACK;
                        x.Parent.Color = OrderedTreeNode.RED;
                        RotateLeft(x.Parent);
                        y = x.Parent.Right;
                    }
                    if(y.Left.Color == OrderedTreeNode.BLACK && 
                        y.Right.Color == OrderedTreeNode.BLACK) { 
                        // children are both black
                        y.Color = OrderedTreeNode.RED; // change parent to red
                        x = x.Parent; // move up the tree
                    } 
                    else {
                        if(y.Right.Color == OrderedTreeNode.BLACK) {
                            y.Left.Color = OrderedTreeNode.BLACK;
                            y.Color = OrderedTreeNode.RED;
                            RotateRight(y);
                            y = x.Parent.Right;
                        }
                        y.Color = x.Parent.Color;
                        x.Parent.Color = OrderedTreeNode.BLACK;
                        y.Right.Color = OrderedTreeNode.BLACK;
                        RotateLeft(x.Parent);
                        x = rbTree;
                    }
                } 
                else { 
                    // right subtree - same as code above with right and left swapped
                    y = x.Parent.Left;
                    if(y.Color == OrderedTreeNode.RED) {
                        y.Color = OrderedTreeNode.BLACK;
                        x.Parent.Color = OrderedTreeNode.RED;
                        RotateRight (x.Parent);
                        y = x.Parent.Left;
                    }
                    if(y.Right.Color == OrderedTreeNode.BLACK && 
                        y.Left.Color == OrderedTreeNode.BLACK) {
                        y.Color = OrderedTreeNode.RED;
                        x = x.Parent;
                    } 
                    else {
                        if(y.Left.Color == OrderedTreeNode.BLACK) {
                            y.Right.Color = OrderedTreeNode.BLACK;
                            y.Color = OrderedTreeNode.RED;
                            RotateLeft(y);
                            y = x.Parent.Left;
                        }
                        y.Color = x.Parent.Color;
                        x.Parent.Color = OrderedTreeNode.BLACK;
                        y.Left.Color = OrderedTreeNode.BLACK;
                        RotateRight(x.Parent);
                        x = rbTree;
                    }
                }
            }
            x.Color = OrderedTreeNode.BLACK;
        }

        ///<summary>
        /// Delete
        /// Delete a node from the tree and restore red black properties
        ///<summary>
        private void Delete(OrderedTreeNode z) {
            // A node to be deleted will be: 
            // 1. a leaf with no children
            // 2. have one child
            // 3. have two children
            // If the deleted node is red, the red black properties still hold.
            // If the deleted node is black, the tree needs rebalancing

            OrderedTreeNode x = new OrderedTreeNode(); // work node to contain the replacement node
            OrderedTreeNode y; // work node 

            // find the replacement node (the successor to x) - the node one with 
            // at *most* one child. 
            if(z.Left == sentinelNode || z.Right == sentinelNode) 
                y = z; // node has sentinel as a child
            else {
                // z has two children, find replacement node which will 
                // be the leftmost node greater than z
                y = z.Right; // traverse right subtree   
                while(y.Left != sentinelNode) // to find next node in sequence
                    y = y.Left;
            }

            // at this point, y contains the replacement node. it's content will be copied 
            // to the valules in the node to be deleted

            // x (y's only child) is the node that will be linked to y's old parent. 
            if(y.Left != sentinelNode)
                x = y.Left;                 
            else
                x = y.Right;                    

            // replace x's parent with y's parent and
            // link x to proper subtree in parent
            // this removes y from the chain
            x.Parent = y.Parent;
            if(y.Parent != null)
                if(y == y.Parent.Left)
                    y.Parent.Left = x;
                else
                    y.Parent.Right = x;
            else
                rbTree = x; // make x the root node

            // copy the values from y (the replacement node) to the node being deleted.
            // note: this effectively deletes the node. 
            if(y != z) {
                z.Key = y.Key;
                z.Data = y.Data;
            }

            if(y.Color == OrderedTreeNode.BLACK)
                RestoreAfterDelete(x);

            lastNodeFound = sentinelNode;
        }

        ///<summary>
        /// GetMaxKey
        /// Returns the maximum key value
        ///<summary>
        virtual public IComparable GetMaxKey() {
            OrderedTreeNode treeNode = rbTree;
            
            if(treeNode == null || treeNode == sentinelNode)
                throw(new InvalidOperationException("Tree is empty"));

            // traverse to the extreme right to find the largest key
            while(treeNode.Right != sentinelNode)
                treeNode = treeNode.Right;

            lastNodeFound = treeNode;

            return treeNode.Key;
            
        }

 virtual public bool ContainsKey(IComparable key) {
     OrderedTreeNode treeNode = rbTree; // begin at root
     int result = 0;
     // traverse tree until node is found
     while(treeNode != sentinelNode) {
         result = key.CompareTo(treeNode.Key);
         if(result == 0) {
             lastNodeFound = treeNode;
             return true;
         }
         if(result < 0)
             treeNode = treeNode.Left;
         else
             treeNode = treeNode.Right;
     }
     return false;
 }

        ///<summary>
        /// RotateRight
        /// Rebalance the tree by rotating the nodes to the right
        ///</summary>
        virtual public void RotateRight(OrderedTreeNode x) {
            // pushing node x down and to the Right to balance the tree. x's Left child (y)
            // replaces x (since x < y), and y's Right child becomes x's Left child 
            // (since it's < x but > y).
            
            OrderedTreeNode y = x.Left; // get x's Left node, this becomes y

            // set x's Right link
            x.Left = y.Right; // y's Right child becomes x's Left child

            // modify parents
            if(y.Right != sentinelNode) 
                y.Right.Parent = x; // sets y's Right Parent to x

            if(y != sentinelNode)
                y.Parent = x.Parent; // set y's Parent to x's Parent

            if(x.Parent != null) { // null=rbTree, could also have used rbTree
                // determine which side of it's Parent x was on
                if(x == x.Parent.Right)         
                    x.Parent.Right = y; // set Right Parent to y
                else
                    x.Parent.Left = y; // set Left Parent to y
            } 
            else 
                rbTree = y; // at rbTree, set it to y

            // link x and y 
            y.Right = x; // put x on y's Right
            if(x != sentinelNode) // set y as x's Parent
                x.Parent = y;       
        }

        ///<summary>
        /// RestoreAfterInsert
        /// Additions to red-black trees usually destroy the red-black 
        /// properties. Examine the tree and restore. Rotations are normally 
        /// required to restore it
        ///</summary>
        private void RestoreAfterInsert(OrderedTreeNode x) {   
            // x and y are used as variable names for brevity, in a more formal
            // implementation, you should probably change the names

            OrderedTreeNode y;

            // maintain red-black tree properties after adding x
            while(x != rbTree && x.Parent.Color == OrderedTreeNode.RED) {
                // Parent node is .Colored red; 
                if(x.Parent == x.Parent.Parent.Left) { // determine traversal path         
                                                        // is it on the Left or Right subtree?
                    y = x.Parent.Parent.Right; // get uncle
                    if(y!= null && y.Color == OrderedTreeNode.RED) {
                        // uncle is red; change x's Parent and uncle to black
                        x.Parent.Color = OrderedTreeNode.BLACK;
                        y.Color = OrderedTreeNode.BLACK;
                        // grandparent must be red. Why? Every red node that is not 
                        // a leaf has only black children 
                        x.Parent.Parent.Color = OrderedTreeNode.RED; 
                        x = x.Parent.Parent; // continue loop with grandparent
                    }   
                    else {
                        // uncle is black; determine if x is greater than Parent
                        if(x == x.Parent.Right) { 
                            // yes, x is greater than Parent; rotate Left
                            // make x a Left child
                            x = x.Parent;
                            RotateLeft(x);
                        }
                        // no, x is less than Parent
                        x.Parent.Color = OrderedTreeNode.BLACK; // make Parent black
                        x.Parent.Parent.Color = OrderedTreeNode.RED; // make grandparent black
                        RotateRight(x.Parent.Parent); // rotate right
                    }
                }
                else {
                    // x's Parent is on the Right subtree
                    // this code is the same as above with "Left" and "Right" swapped
                    y = x.Parent.Parent.Left;
                    if(y!= null && y.Color == OrderedTreeNode.RED) {
                        x.Parent.Color = OrderedTreeNode.BLACK;
                        y.Color = OrderedTreeNode.BLACK;
                        x.Parent.Parent.Color = OrderedTreeNode.RED;
                        x = x.Parent.Parent;
                    }
                    else {
                        if(x == x.Parent.Left) {
                            x = x.Parent;
                            RotateRight(x);
                        }
                        x.Parent.Color = OrderedTreeNode.BLACK;
                        x.Parent.Parent.Color = OrderedTreeNode.RED;
                        RotateLeft(x.Parent.Parent);
                    }
                }                                                                                                                   
            }
            rbTree.Color = OrderedTreeNode.BLACK; // rbTree should always be black
        }

 ///<summary>
 /// GetMinKey
 /// Returns the minimum key value
 ///<summary>
 public IComparable GetMinKey() {
     OrderedTreeNode treeNode = rbTree;
     
     if(treeNode == null || treeNode == sentinelNode)
         throw(new InvalidOperationException("Tree is empty"));
     
     // traverse to the extreme left to find the smallest key
     while(treeNode.Left != sentinelNode)
         treeNode = treeNode.Left;
     
     lastNodeFound = treeNode;
     
     return treeNode.Key;
     
 }

 ///<summary>
 /// Determine order, walk the tree and push the nodes onto the stack
 ///</summary>
 public OrderedTreeEnumerator(OrderedTreeNode tnode, bool keys, bool ascending)
 {
     stack = new Stack();
     this.keys = keys;
     this.ascending = ascending;
     this.tnode = tnode;
     Reset();
 }

 virtual public void Reset() {
     pre = true;
     stack.Clear();
     // use depth-first traversal to push nodes into stack
     // the lowest node will be at the top of the stack
     if(ascending) {
         // find the lowest node
         while(tnode != sentinelNode) {
             stack.Push(tnode);
             tnode = tnode.Left;
         }
     }
     else {
         // the highest node will be at top of stack
         while(tnode != sentinelNode) {
             stack.Push(tnode);
             tnode = tnode.Right;
         }
     }
 }

 ///<summary>
 /// Clear
 /// Empties or clears the tree
 ///<summary>
 virtual public void Clear () {
     rbTree = sentinelNode;
     intCount = 0;
 }

 public OrderedTree()
 {
     rbTree = sentinelNode;
     lastNodeFound = sentinelNode;
 }