main.cs

using System;
using System.Collections.Generic;
using System.Linq;
using TreeLibrary;
using System.Collections;

namespace TreeConsole
{
	public class Program
	{
		static List<MyClass> MyClasses
		{
			get;
			set;
		}

		static readonly int[] SampleSize = { 10, 50, 100, 500, 1000 };        
		static readonly int NumberOfAttempts = 1;
		public static void Main(string[] args)
		{
			MyClasses = new List<MyClass>();
			int avlTreeScore = 0;
			int rbTreeScore = 0;
			int ttTreeScore = 0;
			foreach (int runNumber in SampleSize)
			{
				RunTrees(runNumber);
			}

			foreach (var myclass in MyClasses)
			{
				int min = MoreMath.Min(myclass.AVLTree.Comparisons, myclass.RBTree.Comparisons, myclass.TwoThreeTree.Comparisons);
				if (min == myclass.AVLTree.Comparisons)
				{
					avlTreeScore++;
				}

				if (min == myclass.RBTree.Comparisons)
				{
					rbTreeScore++;
				}

				if (min == myclass.TwoThreeTree.Comparisons)
				{
					ttTreeScore++;
				}
			}

			WriteToTextFile(string.Format("{0},{1},{2}", avlTreeScore, rbTreeScore, ttTreeScore));
		}

		private static void RunTrees(int runNumber)
		{
			AvlTree<int, int> avlTree = new AvlTree<int, int>();
			RedBlackTree redBlackTree = new RedBlackTree("rbTree");
			TwoThreeTree twoThreeTree = new TwoThreeTree(runNumber * NumberOfAttempts);
			for (int i = 1; i <= runNumber; i++)
			{
				avlTree.Insert(i, i);
				redBlackTree.Add(i, i);
				twoThreeTree.InsertTwoThree(i.ToString());
			}

			for (int i = 0; i < NumberOfAttempts; i++)
			{
				Random myRandom = new Random();
				int query = myRandom.Next(0, runNumber * 2);
				//int query = 0;
				int avlTreeOutParameter = 0;
				MyClass myClass = new MyClass()
				{
				Ceiling = runNumber, Query = query
				}

				;
				avlTree.Search(query, out avlTreeOutParameter);
				myClass.AVLTree = new MyOutput()
				{
				Comparisons = StepCounter.ComparisonStep
				}

				;
				redBlackTree.Contains(query);
				myClass.RBTree = new MyOutput()
				{
				Comparisons = StepCounter.ComparisonStep
				}

				;
				twoThreeTree.FindNode(query.ToString());
				myClass.TwoThreeTree = new MyOutput()
				{
				Comparisons = StepCounter.ComparisonStep
				}

				;
				WriteToTextFile(myClass.ToString());
				MyClasses.Add(myClass);
			}
		}

		static void WriteToTextFile(string input)
		{
			Console.WriteLine(input);
		}
	}

	public static class MoreMath
	{
		// This method only exists for consistency, so you can *always* call
		// MoreMath.Max instead of alternating between MoreMath.Max and Math.Max
		// depending on your argument count.
		public static int Max(int x, int y)
		{
			return Math.Max(x, y);
		}

		public static int Min(int x, int y)
		{
			return Math.Min(x, y);
		}

		public static int Max(int x, int y, int z)
		{
			// Or inline it as x < y ? (y < z ? z : y) : (x < z ? z : x);
			// Time it before micro-optimizing though!
			return Math.Max(x, Math.Max(y, z));
		}

		public static int Min(int x, int y, int z)
		{
			// Or inline it as x < y ? (y < z ? z : y) : (x < z ? z : x);
			// Time it before micro-optimizing though!
			return Math.Min(x, Math.Min(y, z));
		}

		public static int Max(int w, int x, int y, int z)
		{
			return Math.Max(w, Math.Max(x, Math.Max(y, z)));
		}

		public static int Max(params int[] values)
		{
			return Enumerable.Max(values);
		}
	}
}

///<summary>
///A red-black tree must satisfy these properties:
///
///1. The root is black. 
///2. All leaves are black. 
///3. Red nodes can only have black children. 
///4. All paths from a node to its leaves contain the same number of black nodes.
///</summary>
namespace TreeLibrary
{
	public class RedBlackTree : object
	{
		// the number of nodes contained in the tree
		private int intCount;
		// a simple randomized hash code. The hash code could be used as a key
		// if it is "unique" enough. Note: The IComparable interface would need to 
		// be replaced with int.
		private int intHashCode;
		// identifies the owner of the tree
		private string strIdentifier;
		// the tree
		private RedBlackNode rbTree;
		//  sentinelNode is convenient way of indicating a leaf node.
		public static RedBlackNode sentinelNode;
		// the node that was last found; used to optimize searches
		private RedBlackNode lastNodeFound;
		private Random rand = new Random();
		public RedBlackTree()
		{
			strIdentifier = base.ToString() + rand.Next();
			intHashCode = rand.Next();
			// 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 RedBlackNode();
			sentinelNode.Left = null;
			sentinelNode.Right = null;
			sentinelNode.Parent = null;
			sentinelNode.Color = RedBlackNode.BLACK;
			rbTree = sentinelNode;
			lastNodeFound = sentinelNode;
		}

		public RedBlackTree(string strIdentifier)
		{
			intHashCode = rand.Next();
			this.strIdentifier = strIdentifier;
		}

		///<summary>
		/// Add
		/// args: ByVal key As IComparable, ByVal data As Object
		/// key is object that implements IComparable interface
		/// performance tip: change to use use int type (such as the hashcode)
		///</summary>
		public void Add(IComparable key, object data)
		{
			if (key == null || data == null)
				throw (new RedBlackException("RedBlackNode key and data must not be null"));
			// traverse tree - find where node belongs
			int result = 0;
			// create new node
			RedBlackNode node = new RedBlackNode();
			RedBlackNode 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)
					throw (new RedBlackException("A Node with the same key already exists"));
				if (result > 0)
					temp = temp.Right;
				else
					temp = temp.Left;
			}

			// setup node
			node.Key = key;
			node.Data = data;
			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>
		/// 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(RedBlackNode x)
		{
			// x and y are used as variable names for brevity, in a more formal
			// implementation, you should probably change the names
			RedBlackNode y;
			// maintain red-black tree properties after adding x
			while (x != rbTree && x.Parent.Color == RedBlackNode.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 == RedBlackNode.RED)
					{ // uncle is red; change x's Parent and uncle to black
						x.Parent.Color = RedBlackNode.BLACK;
						y.Color = RedBlackNode.BLACK;
						// grandparent must be red. Why? Every red node that is not 
						// a leaf has only black children 
						x.Parent.Parent.Color = RedBlackNode.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 = RedBlackNode.BLACK; // make Parent black
						x.Parent.Parent.Color = RedBlackNode.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 == RedBlackNode.RED)
					{
						x.Parent.Color = RedBlackNode.BLACK;
						y.Color = RedBlackNode.BLACK;
						x.Parent.Parent.Color = RedBlackNode.RED;
						x = x.Parent.Parent;
					}
					else
					{
						if (x == x.Parent.Left)
						{
							x = x.Parent;
							RotateRight(x);
						}

						x.Parent.Color = RedBlackNode.BLACK;
						x.Parent.Parent.Color = RedBlackNode.RED;
						RotateLeft(x.Parent.Parent);
					}
				}
			}

			rbTree.Color = RedBlackNode.BLACK; // rbTree should always be black
		}

		///<summary>
		/// RotateLeft
		/// Rebalance the tree by rotating the nodes to the left
		///</summary>
		public void RotateLeft(RedBlackNode x)
		{
			// pushing node x down and to the Left to balance the tree. x's Right child (y)
			// replaces x (since y > x), and y's Left child becomes x's Right child 
			// (since it's < y but > x).
			RedBlackNode y = x.Right; // get x's Right node, this becomes y
			// set x's Right link
			x.Right = y.Left; // y's Left child's becomes x's Right child
			// modify parents
			if (y.Left != sentinelNode)
				y.Left.Parent = x; // sets y's Left Parent to x
			if (y != sentinelNode)
				y.Parent = x.Parent; // set y's Parent to x's Parent
			if (x.Parent != null)
			{ // determine which side of it's Parent x was on
				if (x == x.Parent.Left)
					x.Parent.Left = y; // set Left Parent to y
				else
					x.Parent.Right = y; // set Right Parent to y
			}
			else
				rbTree = y; // at rbTree, set it to y
			// link x and y 
			y.Left = x; // put x on y's Left 
			if (x != sentinelNode) // set y as x's Parent
				x.Parent = y;
		}

		///<summary>
		/// RotateRight
		/// Rebalance the tree by rotating the nodes to the right
		///</summary>
		public void RotateRight(RedBlackNode 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).
			RedBlackNode 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>
		/// GetData
		/// Gets the data object associated with the specified key
		///<summary>
		public object GetData(IComparable key)
		{
			int result;
			RedBlackNode treeNode = rbTree; // begin at root
			// traverse tree until node is found
			while (treeNode != sentinelNode)
			{
				result = key.CompareTo(treeNode.Key);
				if (result == 0)
				{
					lastNodeFound = treeNode;
					return treeNode.Data;
				}

				if (result < 0)
					treeNode = treeNode.Left;
				else
					treeNode = treeNode.Right;
			}

			throw (new RedBlackException("RedBlackNode key was not found"));
		}

		///<summary>
		/// GetMinKey
		/// Returns the minimum key value
		///<summary>
		public IComparable GetMinKey()
		{
			RedBlackNode treeNode = rbTree;
			if (treeNode == null || treeNode == sentinelNode)
				throw (new RedBlackException("RedBlack 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>
		/// GetMaxKey
		/// Returns the maximum key value
		///<summary>
		public IComparable GetMaxKey()
		{
			RedBlackNode treeNode = rbTree;
			if (treeNode == null || treeNode == sentinelNode)
				throw (new RedBlackException("RedBlack 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;
		}

		///<summary>
		/// GetMinValue
		/// Returns the object having the minimum key value
		///<summary>
		public object GetMinValue()
		{
			return GetData(GetMinKey());
		}

		///<summary>
		/// GetMaxValue
		/// Returns the object having the maximum key
		///<summary>
		public object GetMaxValue()
		{
			return GetData(GetMaxKey());
		}

		///<summary>
		/// GetEnumerator
		/// return an enumerator that returns the tree nodes in order
		///<summary>
		public RedBlackEnumerator GetEnumerator()
		{
			// elements is simply a generic name to refer to the 
			// data objects the nodes contain
			return Elements(true);
		}

		///<summary>
		/// Keys
		/// if(ascending is true, the keys will be returned in ascending order, else
		/// the keys will be returned in descending order.
		///<summary>
		public RedBlackEnumerator Keys()
		{
			return Keys(true);
		}

		public RedBlackEnumerator Keys(bool ascending)
		{
			return new RedBlackEnumerator(rbTree, true, ascending);
		}

		///<summary>
		/// Values
		/// Provided for .NET compatibility. 
		///<summary>
		public RedBlackEnumerator Values()
		{
			return Elements(true);
		}

		///<summary>
		/// Elements
		/// Returns an enumeration of the data objects.
		/// if(ascending is true, the objects will be returned in ascending order,
		/// else the objects will be returned in descending order.
		///<summary>
		public RedBlackEnumerator Elements()
		{
			return Elements(true);
		}

		public RedBlackEnumerator Elements(bool ascending)
		{
			return new RedBlackEnumerator(rbTree, false, ascending);
		}

		///<summary>
		/// IsEmpty
		/// Is the tree empty?
		///<summary>
		public bool IsEmpty()
		{
			return (rbTree == null);
		}

		///<summary>
		/// Remove
		/// removes the key and data object (delete)
		///<summary>
		public void Remove(IComparable key)
		{
			if (key == null)
				throw (new RedBlackException("RedBlackNode key is null"));
			// find node
			int result;
			RedBlackNode node;
			// see if node to be deleted was the last one found
			result = key.CompareTo(lastNodeFound.Key);
			if (result == 0)
				node = lastNodeFound;
			else
			{ // not found, must search		
				node = rbTree;
				while (node != sentinelNode)
				{
					result = key.CompareTo(node.Key);
					if (result == 0)
						break;
					if (result < 0)
						node = node.Left;
					else
						node = node.Right;
				}

				if (node == sentinelNode)
					return; // key not found
			}

			Delete(node);
			intCount = intCount - 1;
		}

		///<summary>
		/// Delete
		/// Delete a node from the tree and restore red black properties
		///<summary>
		private void Delete(RedBlackNode 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
			RedBlackNode x = new RedBlackNode(); // work node to contain the replacement node
			RedBlackNode 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 == RedBlackNode.BLACK)
				RestoreAfterDelete(x);
			lastNodeFound = sentinelNode;
		}

		///<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(RedBlackNode x)
		{
			// maintain Red-Black tree balance after deleting node 			
			RedBlackNode y;
			while (x != rbTree && x.Color == RedBlackNode.BLACK)
			{
				if (x == x.Parent.Left) // determine sub tree from parent
				{
					y = x.Parent.Right; // y is x's sibling 
					if (y.Color == RedBlackNode.RED)
					{ // x is black, y is red - make both black and rotate
						y.Color = RedBlackNode.BLACK;
						x.Parent.Color = RedBlackNode.RED;
						RotateLeft(x.Parent);
						y = x.Parent.Right;
					}

					if (y.Left.Color == RedBlackNode.BLACK && y.Right.Color == RedBlackNode.BLACK)
					{ // children are both black
						y.Color = RedBlackNode.RED; // change parent to red
						x = x.Parent; // move up the tree
					}
					else
					{
						if (y.Right.Color == RedBlackNode.BLACK)
						{
							y.Left.Color = RedBlackNode.BLACK;
							y.Color = RedBlackNode.RED;
							RotateRight(y);
							y = x.Parent.Right;
						}

						y.Color = x.Parent.Color;
						x.Parent.Color = RedBlackNode.BLACK;
						y.Right.Color = RedBlackNode.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 == RedBlackNode.RED)
					{
						y.Color = RedBlackNode.BLACK;
						x.Parent.Color = RedBlackNode.RED;
						RotateRight(x.Parent);
						y = x.Parent.Left;
					}

					if (y.Right.Color == RedBlackNode.BLACK && y.Left.Color == RedBlackNode.BLACK)
					{
						y.Color = RedBlackNode.RED;
						x = x.Parent;
					}
					else
					{
						if (y.Left.Color == RedBlackNode.BLACK)
						{
							y.Right.Color = RedBlackNode.BLACK;
							y.Color = RedBlackNode.RED;
							RotateLeft(y);
							y = x.Parent.Left;
						}

						y.Color = x.Parent.Color;
						x.Parent.Color = RedBlackNode.BLACK;
						y.Left.Color = RedBlackNode.BLACK;
						RotateRight(x.Parent);
						x = rbTree;
					}
				}
			}

			x.Color = RedBlackNode.BLACK;
		}

		///<summary>
		/// RemoveMin
		/// removes the node with the minimum key
		///<summary>
		public void RemoveMin()
		{
			if (rbTree == null)
				throw (new RedBlackException("RedBlackNode is null"));
			Remove(GetMinKey());
		}

		///<summary>
		/// RemoveMax
		/// removes the node with the maximum key
		///<summary>
		public void RemoveMax()
		{
			if (rbTree == null)
				throw (new RedBlackException("RedBlackNode is null"));
			Remove(GetMaxKey());
		}

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

		///<summary>
		/// Size
		/// returns the size (number of nodes) in the tree
		///<summary>
		public int Size()
		{
			// number of keys
			return intCount;
		}

		///<summary>
		/// Equals
		///<summary>
		public override bool Equals(object obj)
		{
			if (obj == null)
				return false;
			if (!(obj is RedBlackNode))
				return false;
			if (this == obj)
				return true;
			return (ToString().Equals(((RedBlackNode)(obj)).ToString()));
		}

		///<summary>
		/// HashCode
		///<summary>
		public override int GetHashCode()
		{
			return intHashCode;
		}

		///<summary>
		/// ToString
		///<summary>
		public override string ToString()
		{
			return strIdentifier.ToString();
		}

		public bool Contains(int value)
		{
			StepCounter.ResetStepCounter();
			return (rbTree != null) && SearchRecursively(rbTree, value).Key.CompareTo(value) == 0;
		}

		private RedBlackNode SearchRecursively(RedBlackNode node, int value)
		{
			StepCounter.RecursionStep++;
			StepCounter.ComparisonStep++;
			int myCompare = node.Key.CompareTo(value);
			if (node == null || myCompare == 0)
			{
				return node;
			}
			else if (myCompare == 1)
			{
				if (node.Left == null)
				{
					return node;
				}

				return SearchRecursively(node.Left, value);
			}
			else if (myCompare == -1)
			{
				if (node.Right == null)
				{
					return node;
				}

				return SearchRecursively(node.Right, value);
			}

			return null;
		}
	}
}

namespace TreeLibrary
{
	public class AvlTree<TKey, TValue> : IEnumerable<TValue>
	{
		private IComparer<TKey> _comparer;
		private AvlNode _root;
		public AvlTree(IComparer<TKey> comparer)
		{
			_comparer = comparer;
		}

		public AvlTree(): this (Comparer<TKey>.Default)
		{
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		public IEnumerator<TValue> GetEnumerator()
		{
			return new AvlNodeEnumerator(_root);
		}

		public void Clear()
		{
			_root = null;
		}

		public bool Search(TKey key, out TValue value)
		{
			StepCounter.ResetStepCounter();
			AvlNode node = _root;
			while (node != null)
			{
				if (_comparer.Compare(key, node.Key) < 0)
				{
					StepCounter.ComparisonStep++;
					node = node.Left;
				}
				else if (_comparer.Compare(key, node.Key) > 0)
				{
					StepCounter.ComparisonStep++;
					node = node.Right;
				}
				else
				{
					StepCounter.ComparisonStep++;
					value = node.Value;
					return true;
				}
			}

			value = default (TValue);
			return false;
		}

		public void Insert(TKey key, TValue value)
		{
			if (_root == null)
			{
				_root = new AvlNode
				{
				Key = key, Value = value
				}

				;
			}
			else
			{
				AvlNode node = _root;
				while (node != null)
				{
					int compare = _comparer.Compare(key, node.Key);
					if (compare < 0)
					{
						AvlNode left = node.Left;
						if (left == null)
						{
							node.Left = new AvlNode
							{
							Key = key, Value = value, Parent = node
							}

							;
							InsertBalance(node, 1);
							return;
						}
						else
						{
							node = left;
						}
					}
					else if (compare > 0)
					{
						AvlNode right = node.Right;
						if (right == null)
						{
							node.Right = new AvlNode
							{
							Key = key, Value = value, Parent = node
							}

							;
							InsertBalance(node, -1);
							return;
						}
						else
						{
							node = right;
						}
					}
					else
					{
						node.Value = value;
						return;
					}
				}
			}
		}

		private void InsertBalance(AvlNode node, int balance)
		{
			while (node != null)
			{
				balance = (node.Balance += balance);
				if (balance == 0)
				{
					return;
				}
				else if (balance == 2)
				{
					if (node.Left.Balance == 1)
					{
						RotateRight(node);
					}
					else
					{
						RotateLeftRight(node);
					}

					return;
				}
				else if (balance == -2)
				{
					if (node.Right.Balance == -1)
					{
						RotateLeft(node);
					}
					else
					{
						RotateRightLeft(node);
					}

					return;
				}

				AvlNode parent = node.Parent;
				if (parent != null)
				{
					balance = parent.Left == node ? 1 : -1;
				}

				node = parent;
			}
		}

		public bool Delete(TKey key)
		{
			AvlNode node = _root;
			while (node != null)
			{
				if (_comparer.Compare(key, node.Key) < 0)
				{
					node = node.Left;
				}
				else if (_comparer.Compare(key, node.Key) > 0)
				{
					node = node.Right;
				}
				else
				{
					AvlNode left = node.Left;
					AvlNode right = node.Right;
					if (left == null)
					{
						if (right == null)
						{
							if (node == _root)
							{
								_root = null;
							}
							else
							{
								AvlNode parent = node.Parent;
								if (parent.Left == node)
								{
									parent.Left = null;
									DeleteBalance(parent, -1);
								}
								else
								{
									parent.Right = null;
									DeleteBalance(parent, 1);
								}
							}
						}
						else
						{
							Replace(node, right);
							DeleteBalance(node, 0);
						}
					}
					else if (right == null)
					{
						Replace(node, left);
						DeleteBalance(node, 0);
					}
					else
					{
						AvlNode successor = right;
						if (successor.Left == null)
						{
							AvlNode parent = node.Parent;
							successor.Parent = parent;
							successor.Left = left;
							successor.Balance = node.Balance;
							if (left != null)
							{
								left.Parent = successor;
							}

							if (node == _root)
							{
								_root = successor;
							}
							else
							{
								if (parent.Left == node)
								{
									parent.Left = successor;
								}
								else
								{
									parent.Right = successor;
								}
							}

							DeleteBalance(successor, 1);
						}
						else
						{
							while (successor.Left != null)
							{
								successor = successor.Left;
							}

							AvlNode parent = node.Parent;
							AvlNode successorParent = successor.Parent;
							AvlNode successorRight = successor.Right;
							if (successorParent.Left == successor)
							{
								successorParent.Left = successorRight;
							}
							else
							{
								successorParent.Right = successorRight;
							}

							if (successorRight != null)
							{
								successorRight.Parent = successorParent;
							}

							successor.Parent = parent;
							successor.Left = left;
							successor.Balance = node.Balance;
							successor.Right = right;
							right.Parent = successor;
							if (left != null)
							{
								left.Parent = successor;
							}

							if (node == _root)
							{
								_root = successor;
							}
							else
							{
								if (parent.Left == node)
								{
									parent.Left = successor;
								}
								else
								{
									parent.Right = successor;
								}
							}

							DeleteBalance(successorParent, -1);
						}
					}

					return true;
				}
			}

			return false;
		}

		private void DeleteBalance(AvlNode node, int balance)
		{
			while (node != null)
			{
				balance = (node.Balance += balance);
				if (balance == 2)
				{
					if (node.Left.Balance >= 0)
					{
						node = RotateRight(node);
						if (node.Balance == -1)
						{
							return;
						}
					}
					else
					{
						node = RotateLeftRight(node);
					}
				}
				else if (balance == -2)
				{
					if (node.Right.Balance <= 0)
					{
						node = RotateLeft(node);
						if (node.Balance == 1)
						{
							return;
						}
					}
					else
					{
						node = RotateRightLeft(node);
					}
				}
				else if (balance != 0)
				{
					return;
				}

				AvlNode parent = node.Parent;
				if (parent != null)
				{
					balance = parent.Left == node ? -1 : 1;
				}

				node = parent;
			}
		}

		private AvlNode RotateLeft(AvlNode node)
		{
			AvlNode right = node.Right;
			AvlNode rightLeft = right.Left;
			AvlNode parent = node.Parent;
			right.Parent = parent;
			right.Left = node;
			node.Right = rightLeft;
			node.Parent = right;
			if (rightLeft != null)
			{
				rightLeft.Parent = node;
			}

			if (node == _root)
			{
				_root = right;
			}
			else if (parent.Right == node)
			{
				parent.Right = right;
			}
			else
			{
				parent.Left = right;
			}

			right.Balance++;
			node.Balance = -right.Balance;
			return right;
		}

		private AvlNode RotateRight(AvlNode node)
		{
			AvlNode left = node.Left;
			AvlNode leftRight = left.Right;
			AvlNode parent = node.Parent;
			left.Parent = parent;
			left.Right = node;
			node.Left = leftRight;
			node.Parent = left;
			if (leftRight != null)
			{
				leftRight.Parent = node;
			}

			if (node == _root)
			{
				_root = left;
			}
			else if (parent.Left == node)
			{
				parent.Left = left;
			}
			else
			{
				parent.Right = left;
			}

			left.Balance--;
			node.Balance = -left.Balance;
			return left;
		}

		private AvlNode RotateLeftRight(AvlNode node)
		{
			AvlNode left = node.Left;
			AvlNode leftRight = left.Right;
			AvlNode parent = node.Parent;
			AvlNode leftRightRight = leftRight.Right;
			AvlNode leftRightLeft = leftRight.Left;
			leftRight.Parent = parent;
			node.Left = leftRightRight;
			left.Right = leftRightLeft;
			leftRight.Left = left;
			leftRight.Right = node;
			left.Parent = leftRight;
			node.Parent = leftRight;
			if (leftRightRight != null)
			{
				leftRightRight.Parent = node;
			}

			if (leftRightLeft != null)
			{
				leftRightLeft.Parent = left;
			}

			if (node == _root)
			{
				_root = leftRight;
			}
			else if (parent.Left == node)
			{
				parent.Left = leftRight;
			}
			else
			{
				parent.Right = leftRight;
			}

			if (leftRight.Balance == -1)
			{
				node.Balance = 0;
				left.Balance = 1;
			}
			else if (leftRight.Balance == 0)
			{
				node.Balance = 0;
				left.Balance = 0;
			}
			else
			{
				node.Balance = -1;
				left.Balance = 0;
			}

			leftRight.Balance = 0;
			return leftRight;
		}

		private AvlNode RotateRightLeft(AvlNode node)
		{
			AvlNode right = node.Right;
			AvlNode rightLeft = right.Left;
			AvlNode parent = node.Parent;
			AvlNode rightLeftLeft = rightLeft.Left;
			AvlNode rightLeftRight = rightLeft.Right;
			rightLeft.Parent = parent;
			node.Right = rightLeftLeft;
			right.Left = rightLeftRight;
			rightLeft.Right = right;
			rightLeft.Left = node;
			right.Parent = rightLeft;
			node.Parent = rightLeft;
			if (rightLeftLeft != null)
			{
				rightLeftLeft.Parent = node;
			}

			if (rightLeftRight != null)
			{
				rightLeftRight.Parent = right;
			}

			if (node == _root)
			{
				_root = rightLeft;
			}
			else if (parent.Right == node)
			{
				parent.Right = rightLeft;
			}
			else
			{
				parent.Left = rightLeft;
			}

			if (rightLeft.Balance == 1)
			{
				node.Balance = 0;
				right.Balance = -1;
			}
			else if (rightLeft.Balance == 0)
			{
				node.Balance = 0;
				right.Balance = 0;
			}
			else
			{
				node.Balance = 1;
				right.Balance = 0;
			}

			rightLeft.Balance = 0;
			return rightLeft;
		}

		private static void Replace(AvlNode target, AvlNode source)
		{
			AvlNode left = source.Left;
			AvlNode right = source.Right;
			target.Balance = source.Balance;
			target.Key = source.Key;
			target.Value = source.Value;
			target.Left = left;
			target.Right = right;
			if (left != null)
			{
				left.Parent = target;
			}

			if (right != null)
			{
				right.Parent = target;
			}
		}

		sealed class AvlNode
		{
			public AvlNode Parent;
			public AvlNode Left;
			public AvlNode Right;
			public TKey Key;
			public TValue Value;
			public int Balance;
		}

		sealed class AvlNodeEnumerator : IEnumerator<TValue>
		{
			private AvlNode _root;
			private Action _action;
			private AvlNode _current;
			private AvlNode _right;
			public AvlNodeEnumerator(AvlNode root)
			{
				_right = _root = root;
				_action = root == null ? Action.End : Action.Right;
			}

			public bool MoveNext()
			{
				switch (_action)
				{
					case Action.Right:
						_current = _right;
						while (_current.Left != null)
						{
							_current = _current.Left;
						}

						_right = _current.Right;
						_action = _right != null ? Action.Right : Action.Parent;
						return true;
					case Action.Parent:
						while (_current.Parent != null)
						{
							AvlNode previous = _current;
							_current = _current.Parent;
							if (_current.Left == previous)
							{
								_right = _current.Right;
								_action = _right != null ? Action.Right : Action.Parent;
								return true;
							}
						}

						_action = Action.End;
						return false;
					default:
						return false;
				}
			}

			public void Reset()
			{
				_right = _root;
				_action = _root == null ? Action.End : Action.Right;
			}

			public TValue Current
			{
				get
				{
					return _current.Value;
				}
			}

			object IEnumerator.Current
			{
				get
				{
					return Current;
				}
			}

			public void Dispose()
			{
			}

			enum Action
			{
				Parent,
				Right,
				End
			}
		}
	}
}

namespace TreeLibrary
{
	public sealed class TwoThreeTree
	{
		TwoThreeNode[] objTree;
		private int intTempPointer, intTop, intStackIndex, intTreeSize;
		private string strTempKey;
		TwoThreeStack objTwoThreeStack;
		static readonly int intNull = -1;
		public int Size
		{
			get;
			private set;
		}

		public TwoThreeTree()
		{
		}

		public TwoThreeTree(int intSize)
		{
			Size = 0;
			objTree = new TwoThreeNode[intSize + 1];
			intTreeSize = intSize;
			intTop = intNull;
			intStackIndex = 1;
			for (int i = 1; i <= intTreeSize; i++)
			{
				objTree[i] = new TwoThreeNode();
				objTree[i].RightData = objTree[i].LeftData = null;
				objTree[i].LeftChild = intNull;
				objTree[i].MiddleChild = intNull;
				objTree[i].RightChild = intNull;
			}
		}

		public int Compare(string strTemp1, string strTemp2)
		{
			int intCompare = 1;
			if (strTemp1 != null)
			{
				intCompare = String.Compare(strTemp1, strTemp2);
			}

			StepCounter.ComparisonStep++;
			return intCompare;
		}

		public int FindNode(string strKey)
		{
			int intTempPointerInside;
			intTempPointerInside = intTop;
			StepCounter.ResetStepCounter();
			while (intTempPointerInside != intNull)
			{
				int intLeftDataCompare = Compare(objTree[intTempPointerInside].LeftData, strKey);
				int intRightDataCompare = Compare(objTree[intTempPointerInside].RightData, strKey);
				if (intLeftDataCompare == 0)
				{
					objTwoThreeStack.Push(intTempPointerInside);
					objTree[intTempPointerInside].LeftDataDuplicates = 1;
					return intNull;
				}

				if (intRightDataCompare == 0)
				{
					objTwoThreeStack.Push(intTempPointerInside);
					objTree[intTempPointerInside].RightDataDuplicates = 1;
					return intNull;
				}

				if (intLeftDataCompare > 0)
				{
					objTwoThreeStack.Push(intTempPointerInside);
					intTempPointerInside = objTree[intTempPointerInside].LeftChild;
				}
				else if ((intLeftDataCompare < 0) && (intRightDataCompare == 0))
				{
					objTwoThreeStack.Push(intTempPointerInside);
					intTempPointerInside = objTree[intTempPointerInside].MiddleChild;
				}
				else if ((intLeftDataCompare < 0) && (intRightDataCompare > 0))
				{
					objTwoThreeStack.Push(intTempPointerInside);
					intTempPointerInside = objTree[intTempPointerInside].MiddleChild;
				}
				else
				{
					objTwoThreeStack.Push(intTempPointerInside);
					intTempPointerInside = objTree[intTempPointerInside].RightChild;
				}
			}

			return (objTwoThreeStack.Pop());
		}

		public void InOrderHelper(int ptr)
		{
			if (ptr != intNull)
			{
				InOrderHelper(objTree[ptr].LeftChild);
				if (objTree[ptr].LeftData != null)
					Console.WriteLine(objTree[ptr].LeftData + " [Duplicates: " + objTree[ptr].LeftDataDuplicates + "]");
				InOrderHelper(objTree[ptr].MiddleChild);
				if (objTree[ptr].RightData != null)
					Console.WriteLine(objTree[ptr].RightData + " [Duplicates: " + objTree[ptr].RightDataDuplicates + "]");
				InOrderHelper(objTree[ptr].RightChild);
			}
		}

		public bool InsertTwoThree(string strKey)
		{
			objTwoThreeStack = new TwoThreeStack(intTreeSize);
			int intTempPointerInside;
			bool bNotDone;
			if (intTop == intNull)
			{
				NewRoot(Top, strKey, intNull);
				Size++;
				return true;
			}
			else
			{
				intTempPointerInside = FindNode(strKey);
				if (intTempPointerInside != intNull)
				{
					intTempPointer = intNull;
					bNotDone = true;
					strTempKey = strKey;
					while (bNotDone)
					{
						if (objTree[intTempPointerInside].RightData == null)
						{
							PutIn(intTempPointerInside, strTempKey, intTempPointer);
							bNotDone = false;
						}
						else
						{
							Split(intTempPointerInside, strTempKey, intTempPointer);
							if (intTempPointerInside == Top)
							{
								NewRoot(Top, strTempKey, intTempPointer);
								bNotDone = false;
							}
							else
								intTempPointerInside = objTwoThreeStack.Pop();
						}
					}

					objTwoThreeStack.Clear();
				}

				Size++;
				return true;
			}
		}

		public void NewRoot(int intLeftChild, string strLeftData, int intMiddileChild)
		{
			int intTempPointerInside;
			intTempPointerInside = intStackIndex;
			intStackIndex++;
			objTree[intTempPointerInside].LeftData = strLeftData;
			objTree[intTempPointerInside].LeftChild = intLeftChild;
			objTree[intTempPointerInside].MiddleChild = intMiddileChild;
			intTop = intTempPointerInside;
		}

		public void PrintInOrder(int ptr)
		{
			InOrderHelper(ptr);
		}

		public void PutIn(int intTempPointerInside, string strKey, int intChildPointer)
		{
			int intLeftDataCompare = Compare(objTree[intTempPointerInside].LeftData, strKey);
			if (intLeftDataCompare < 0)
			{
				objTree[intTempPointerInside].RightData = strKey;
				objTree[intTempPointerInside].RightChild = intChildPointer;
			}
			else
			{
				objTree[intTempPointerInside].RightData = objTree[intTempPointerInside].LeftData;
				objTree[intTempPointerInside].RightChild = objTree[intTempPointerInside].MiddleChild;
				objTree[intTempPointerInside].LeftData = strKey;
				objTree[intTempPointerInside].MiddleChild = intChildPointer;
			}
		}

		public void Split(int intTempPointerInside, string strKey, int intChildPointer)
		{
			int intStackIndexInside;
			intStackIndexInside = intStackIndex;
			intStackIndex++;
			int intLeftDataCompare = Compare(objTree[intTempPointerInside].LeftData, strKey);
			int intRightDataCompare = Compare(objTree[intTempPointerInside].RightData, strKey);
			if (intRightDataCompare < 0)
			{
				objTree[intStackIndexInside].LeftData = strKey;
				objTree[intStackIndexInside].MiddleChild = intChildPointer;
				objTree[intStackIndexInside].LeftChild = objTree[intTempPointerInside].RightChild;
				strTempKey = objTree[intTempPointerInside].RightData;
			}
			else
			{
				objTree[intStackIndexInside].LeftData = objTree[intTempPointerInside].RightData;
				objTree[intStackIndexInside].MiddleChild = objTree[intTempPointerInside].RightChild;
				if (intLeftDataCompare < 0)
				{
					objTree[intStackIndexInside].LeftChild = intChildPointer;
					strTempKey = strKey;
				}
				else
				{
					objTree[intStackIndexInside].LeftChild = objTree[intTempPointerInside].MiddleChild;
					strTempKey = objTree[intTempPointerInside].LeftData;
					objTree[intTempPointerInside].LeftData = strKey;
					objTree[intTempPointerInside].MiddleChild = intChildPointer;
				}
			}

			objTree[intTempPointerInside].RightData = null;
			objTree[intTempPointerInside].RightChild = intNull;
			intTempPointer = intStackIndexInside;
		}

		public int Top
		{
			get
			{
				return intTop;
			}
		}
	}
}

///<summary>
/// The RedBlackEnumerator class returns the keys or data objects of the treap in
/// sorted order. 
///</summary>
namespace TreeLibrary
{
	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 != RedBlackTree.sentinelNode)
				{
					stack.Push(tnode);
					tnode = tnode.Left;
				}
			}
			else
			{
				// the highest node will be at top of stack
				while (tnode != RedBlackTree.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 == RedBlackTree.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 != RedBlackTree.sentinelNode)
					{
						stack.Push(tn);
						tn = tn.Left;
					}
				}
			}
			else // descending, same comments as above apply
			{
				if (node.Left == RedBlackTree.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 != RedBlackTree.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;
		}
	}
}

///<summary>
/// The RedBlackException class distinguishes read black tree exceptions from .NET
/// exceptions. 
///</summary>
namespace TreeLibrary
{
	public class RedBlackException : Exception
	{
		public RedBlackException()
		{
		}

		public RedBlackException(string msg): base (msg)
		{
		}
	}
}

///<summary>
/// The RedBlackNode class encapsulates a node in the tree
///</summary>
namespace TreeLibrary
{
	public class RedBlackNode
	{
		// tree node colors
		public static int RED = 0;
		public static int BLACK = 1;
		// key provided by the calling class
		private IComparable ordKey;
		// the data or value associated with the key
		private object objData;
		// color - used to balance the tree
		private int intColor;
		// left node 
		private RedBlackNode rbnLeft;
		// right node 
		private RedBlackNode rbnRight;
		// parent node 
		private RedBlackNode rbnParent;
		///<summary>
		///Key
		///</summary>
		public IComparable Key
		{
			get
			{
				return ordKey;
			}

			set
			{
				ordKey = value;
			}
		}

		///<summary>
		///Data
		///</summary>
		public object Data
		{
			get
			{
				return objData;
			}

			set
			{
				objData = value;
			}
		}

		///<summary>
		///Color
		///</summary>
		public int Color
		{
			get
			{
				return intColor;
			}

			set
			{
				intColor = value;
			}
		}

		///<summary>
		///Left
		///</summary>
		public RedBlackNode Left
		{
			get
			{
				return rbnLeft;
			}

			set
			{
				rbnLeft = value;
			}
		}

		///<summary>
		/// Right
		///</summary>
		public RedBlackNode Right
		{
			get
			{
				return rbnRight;
			}

			set
			{
				rbnRight = value;
			}
		}

		public RedBlackNode Parent
		{
			get
			{
				return rbnParent;
			}

			set
			{
				rbnParent = value;
			}
		}

		public RedBlackNode()
		{
			Color = RED;
		}
	}
}

namespace TreeLibrary
{
	public static class StepCounter
	{
		public static int ComparisonStep
		{
			get;
			set;
		}

		public static int TraversalStep
		{
			get;
			set;
		}

		public static int RecursionStep
		{
			get;
			set;
		}

		public static void ResetStepCounter()
		{
			ComparisonStep = 0;
			TraversalStep = 0;
			RecursionStep = 0;
		}
	}
}

namespace TreeLibrary
{
	public sealed class TwoThreeNode
	{
		private int intLeftDataDuplicates, intRightDataDuplicates;
		public TwoThreeNode()
		{
			intLeftDataDuplicates = 0;
			intRightDataDuplicates = 0;
		}

		public int LeftChild
		{
			get;
			set;
		}

		public string LeftData
		{
			get;
			set;
		}

		public int MiddleChild
		{
			get;
			set;
		}

		public int RightChild
		{
			get;
			set;
		}

		public string RightData
		{
			get;
			set;
		}

		public int LeftDataDuplicates
		{
			get
			{
				return intLeftDataDuplicates;
			}

			set
			{
				intLeftDataDuplicates += value;
			}
		}

		public int RightDataDuplicates
		{
			get
			{
				return intRightDataDuplicates;
			}

			set
			{
				intRightDataDuplicates += value;
			}
		}
	}
}

namespace TreeLibrary
{
	public sealed class TwoThreeStack
	{
		int[] objItems;
		int intTop;
		public TwoThreeStack()
		{
		}

		public TwoThreeStack(int intTreeSize)
		{
			objItems = new int[intTreeSize];
			intTop = -1;
		}

		public int Pop()
		{
			return objItems[intTop--];
		}

		public void Push(int key)
		{
			objItems[++intTop] = key;
		}

		public void Clear()
		{
			for (int i = 0; i < objItems.Length; i++)
			{
				objItems[i] = 0;
			}

			intTop = -1;
		}

		public bool Empty()
		{
			return intTop == -1;
		}
	}
}

namespace TreeConsole
{
	public class MyOutput
	{
		public int Comparisons
		{
			get;
			set;
		}
	}

	class MyClass
	{
		public int Ceiling
		{
			get;
			set;
		}

		public int Query
		{
			get;
			set;
		}

		public MyOutput AVLTree
		{
			get;
			set;
		}

		public MyOutput RBTree
		{
			get;
			set;
		}

		public MyOutput TwoThreeTree
		{
			get;
			set;
		}

		public override string ToString()
		{
			//return String.Format("Ceiling: {0}, Query: {1}, AVLTree: {2}, RBTree: {3}, TwoThreeTree: {4}", Ceiling, Query, AVLTree.Comparisons, RBTree.Comparisons, TwoThreeTree.Comparisons);
			return String.Format("{0},{1},{2},{3},{4}", Ceiling, Query, AVLTree.Comparisons, RBTree.Comparisons, TwoThreeTree.Comparisons);
		}
	}
}