Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Red-Black Trees in C#

, 14 Sep 2004
A C# implementation of a Red-Black Tree.
redblackcs_src.zip
RedBlackCS
bin
Release
RedBlackCS.dll
obj
Release
temp
TempPE
RedBlackCS.csproj.user
Test
bin
release
RedBlackCS.dll
Test.exe
obj
Release
temp
TempPE
Test.csproj.user
///<summary>
/// The RedBlackEnumerator class returns the keys or data objects of the treap in
/// sorted order. 
///</summary>
using System;
using System.Collections;
	
namespace RedBlackCS
{
	public class RedBlackEnumerator
	{
		// the treap uses the stack to order the nodes
		private Stack stack;
		// return the keys
		private bool keys;
		// return in ascending order (true) or descending (false)
		private bool ascending;
		
		// key
		private IComparable ordKey;
		// the data or value associated with the key
		private object objValue;

        public  string  Color;             // testing only, don't use in live system
        public  IComparable parentKey;     // testing only, don't use in live system
		
		///<summary>
		///Key
		///</summary>
		public IComparable Key
		{
			get
            {
				return ordKey;
			}
			
			set
			{
				ordKey = value;
			}
		}
		///<summary>
		///Data
		///</summary>
		public object Value
		{
			get
            {
				return objValue;
			}
			
			set
			{
				objValue = value;
			}
		}
		
		public RedBlackEnumerator() 
        {
		}
		///<summary>
		/// Determine order, walk the tree and push the nodes onto the stack
		///</summary>
		public RedBlackEnumerator(RedBlackNode tnode, bool keys, bool ascending) 
        {
			
			stack           = new Stack();
			this.keys       = keys;
			this.ascending  = ascending;
			
            // 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 != RedBlack.sentinelNode)
				{
					stack.Push(tnode);
					tnode = tnode.Left;
				}
			}
			else
			{
                // the highest node will be at top of stack
				while(tnode != RedBlack.sentinelNode)
				{
					stack.Push(tnode);
					tnode = tnode.Right;
				}
			}
			
		}
		///<summary>
		/// HasMoreElements
		///</summary>
		public bool HasMoreElements()
		{
			return (stack.Count > 0);
		}
		///<summary>
		/// NextElement
		///</summary>
		public object NextElement()
		{
			if(stack.Count == 0)
				throw(new RedBlackException("Element not found"));
			
			// the top of stack will always have the next item
			// get top of stack but don't remove it as the next nodes in sequence
			// may be pushed onto the top
			// the stack will be popped after all the nodes have been returned
			RedBlackNode node = (RedBlackNode) stack.Peek();	//next node in sequence
			
            if(ascending)
            {
                if(node.Right == RedBlack.sentinelNode)
                {	
                    // yes, top node is lowest node in subtree - pop node off stack 
                    RedBlackNode tn = (RedBlackNode) stack.Pop();
                    // peek at right node's parent 
                    // get rid of it if it has already been used
                    while(HasMoreElements()&& ((RedBlackNode) stack.Peek()).Right == tn)
                        tn = (RedBlackNode) stack.Pop();
                }
                else
                {
                    // find the next items in the sequence
                    // traverse to left; find lowest and push onto stack
                    RedBlackNode tn = node.Right;
                    while(tn != RedBlack.sentinelNode)
                    {
                        stack.Push(tn);
                        tn = tn.Left;
                    }
                }
            }
            else            // descending, same comments as above apply
            {
                if(node.Left == RedBlack.sentinelNode)
                {
                    // walk the tree
                    RedBlackNode tn = (RedBlackNode) stack.Pop();
                    while(HasMoreElements() && ((RedBlackNode)stack.Peek()).Left == tn)
                        tn = (RedBlackNode) stack.Pop();
                }
                else
                {
                    // determine next node in sequence
                    // traverse to left subtree and find greatest node - push onto stack
                    RedBlackNode tn = node.Left;
                    while(tn != RedBlack.sentinelNode)
                    {
                        stack.Push(tn);
                        tn = tn.Right;
                    }
                }
            }
			
			// the following is for .NET compatibility (see MoveNext())
			Key     = node.Key;
			Value   = node.Data;
            // ******** testing only ********
            try
            {
            parentKey = node.Parent.Key;            // testing only
            
            }
            catch(Exception e)
            {
                object o = e;                       // stop compiler from complaining
                parentKey = 0;
            }
			if(node.Color == 0)                     // testing only
                Color = "Red";
            else
                Color = "Black";
            // ******** testing only ********

            return keys == true ? node.Key : node.Data;			
		}
		///<summary>
		/// MoveNext
		/// For .NET compatibility
		///</summary>
		public bool MoveNext()
		{
			if(HasMoreElements())
			{
				NextElement();
				return true;
			}
			return false;
		}
	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

RoyClem
Architect
United States United States
Roy is a software developer who digs all aspects of software development, from design and architecture to implementation.

| Advertise | Privacy | Mobile
Web02 | 2.8.140905.1 | Last Updated 14 Sep 2004
Article Copyright 2004 by RoyClem
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid