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

Treaps in C#

, 15 Sep 2004 CPOL
A Treap implementation in C#.
treapcs_src.zip
TreapCS
bin
release
TreapCS.dll
obj
Release
temp
TempPE
Test
bin
release
Test.exe
TreapCS.dll
obj
Debug
temp
TempPE
Release
temp
TempPE
Test.csproj.user
TreapCS.csproj.user
///<summary>
///   An implementation of a treap data structure.
///
///   A treap is based upon a randomized binary Tree whose nodes have keys and
///   which also have priorities associated with them in a heap - hence the
///   name (tre)e h(eap).
///
///   A Tree is a `heap' if each node has a priority such that the priority of
///   each child is greater than the priority of its parent (trees that are heaps
///   can also called "priority queues", and are the basis of a heap sort).
///
///   The priorities are a means to randomize the Tree. Randomized trees are better
///   balanced (essentially meaning less depth) so that seach time is minimized.
///
///   Treaps were first introduced by Seidel and Aragon in <blockquote>
///   R. Seidel and C. R. Aragon. Randomized Binary Search Trees.
///   <em>Algorithmica</em>, 16(4/5):464-497, 1996. </blockquote>
///
///   Most methods run in O(log n) randomized time, where n is the number of keys in
///   the treap. The exceptions are clone() and toString() that run in time
///   proportional to the intCount of their output.
///
///   This code was was ultimately based upon the Java treap implementation by Stefan Nilsson
///   published in Dr. Dobb's Journal, pp. 40-44, Vol. 267, July 1997
///</summary>

using System.Collections;
using System.Text;
using System;

namespace TreapCS
{
	public class Treap : object
	{
		
		// random priority to keep the treap balanced
		private Random      rndPriority;
		// the number of key-and-value pairs contained in the treap
		private int         intCount;
		// used for quick comparisons
		private int         intHashCode;
		// identIfies the owner of the treap
		private string      strIdentIfier;
		// the treap
		private TreapNode   treapTree;
		private bool        boolKeyFound;
		private object      prevData;
		
		public Treap() 
        {
			rndPriority = new Random();
			intHashCode = rndPriority.Next();
		}
		
		public Treap(string strIdentIfier) 
        {
			rndPriority         = new Random();
			intHashCode         = rndPriority.Next();
			this.strIdentIfier  = strIdentIfier;
		}
		
		///<summary>
		/// Add
		/// args: ByVal key As IComparable, ByVal data As Object
		/// key is object that implements IComparable interface
		///</summary>
		public void Add (IComparable key, object data)
		{
			if(key == null || data == null)
				throw(new TreapException("Treap key and data must not be Nothing"));
			
			// create New node
			TreapNode node = new TreapNode();
			if(node == null)
				throw(new TreapException("Unable to create Treap Node"));
			
			node.Key    = key;
			node.Data   = data;

			// generate random priority
			node.Priority   = rndPriority.Next();
		
			// insert node into treapTree
            boolKeyFound    = false;
            treapTree = InsertNode(node, treapTree);
			if(boolKeyFound)
				throw(new TreapException("A Node with the same key already exists"));
			else
				intCount = intCount + 1;
		}
		
		///<summary>
		/// InsertNode
		/// inserts a node into the tree - note recursive method
		/// this method rebalances the tree using the priorities
		///
		/// Note: The lower the number, the higher the priority
		///<summary>
		private TreapNode InsertNode(TreapNode node, TreapNode tree)
		{
			if(tree == null)
				return node;
			
			int result = node.Key.CompareTo(tree.Key);
			
			if(result < 0)
			{
				tree.Left = InsertNode(node, tree.Left);
				if(tree.Left.Priority < tree.Priority)
					tree = tree.RotateRight();
			}
			else
            if(result > 0)
			{
				tree.Right = InsertNode(node, tree.Right);
				if(tree.Right.Priority < tree.Priority)
					tree = tree.RotateLeft();
			}
			else
			{
				prevData    = tree.Data;
				tree.Data   = node.Data;
			}
			
			return tree;
		}
		
		///<summary>
		/// GetData
		/// Gets the data associated with the specified key
		///<summary>
		public object GetData(IComparable key)
		{
			TreapNode treeNode = treapTree;
			int result;
			
			while(treeNode != null)
			{
				result = key.CompareTo(treeNode.Key);
				if(result == 0)
					return treeNode.Data;
				if(result < 0)
					treeNode = treeNode.Left;
				else
					treeNode = treeNode.Right;
			}
			
			throw(new TreapException("Treap key was not found"));
		}
		///<summary>
		/// GetMinKey
		/// Returns the minimum key value
		///<summary>
		public IComparable GetMinKey()
		{
			TreapNode treeNode = treapTree;
			
			if(treeNode == null)
				throw(new TreapException("Treap is empty"));
			
			while(treeNode.Left != null)
				treeNode = treeNode.Left;
			
			return treeNode.Key;
			
		}
		///<summary>
		/// GetMaxKey
		/// Returns the maximum key value
		///<summary>
		public IComparable GetMaxKey()
		{
			TreapNode treeNode = treapTree;
			
			if(treeNode == null)
				throw(new TreapException("Treap is empty"));
			
			while(treeNode.Right != null)
				treeNode = treeNode.Right;
			
			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
		///<summary>
		public TreapEnumerator GetEnumerator()
		{
			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 TreapEnumerator Keys()
		{
			return Keys(true);
		}
		public TreapEnumerator Keys(bool ascending)
		{
			return new TreapEnumerator(treapTree, true, ascending);
		}
		///<summary>
		/// Values
		/// .NET compatibility
		///<summary>
		public TreapEnumerator 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 TreapEnumerator Elements()
		{
			return Elements(true);
		}
		public TreapEnumerator Elements(bool ascending)
		{
			return new TreapEnumerator(treapTree, false, ascending);
		}
		///<summary>
		/// IsEmpty
		///<summary>
		public bool IsEmpty()
		{
			return (treapTree == null);
		}
		///<summary>
		/// Remove
		/// removes the key and Object
		///<summary>
		public void Remove (IComparable key)
		{
            if(key == null)
                throw(new TreapException("Treap key is null"));
            
            boolKeyFound = false;
			
			treapTree  = Delete(key, treapTree);
			
			if(boolKeyFound)
				intCount = intCount - 1;
		}
		///<summary>
		/// RemoveMin
		/// removes the node with the minimum key
		///<summary>
		public object RemoveMin()
		{
            if(treapTree == null)
                throw(new TreapException("Treap is null"));
            
            // start at top
			TreapNode treeNode = treapTree;
			TreapNode prevTreapNode;
			
			if(treeNode.Left == null)
				// remove top node by replacing with right
				treapTree = treeNode.Right;
			else
			{
				do
				{
					// find the minimum node
					prevTreapNode   = treeNode;
					treeNode        = treeNode.Left;
				} while(treeNode.Left != null);
				// remove left node by replacing with right node
				prevTreapNode.Left  = treeNode.Right;
			}
			
			intCount = intCount - 1;
			
			return treeNode.Data;
			
		}
		///<summary>
		/// RemoveMax
		/// removes the node with the maximum key
		///<summary>
		public object RemoveMax()
		{
            if(treapTree == null)
                throw(new TreapException("Treap is null"));
            
            // start at top
			TreapNode treeNode = treapTree;
			TreapNode prevTreapNode;
			
			if(treeNode.Right == null)
				// remove top node by replacing with left
				treapTree = treeNode.Left;
			else
			{
				do
				{
					// find the maximum node
					prevTreapNode = treeNode;
					treeNode = treeNode.Right;
				} while(treeNode.Right != null);
				// remove right node by replacing with left node
				prevTreapNode.Right = treeNode.Left;
			}
			
			intCount = intCount - 1;
			
			return treeNode.Data;
		}
		///<summary>
		/// Clear
		///<summary>
		public void Clear ()
		{
			treapTree   = null;
			intCount    = 0;
		}
		///<summary>
		/// Size
		///<summary>
		public int Size()
		{
			// number of keys
			return intCount;
		}
		///<summary>
		/// Delete
		/// deletes a node - note recursive function
		/// Deletes works by "bubbling down" the node until it is a leaf, and then
		/// pruning it off the tree
		///<summary>
		private TreapNode Delete(IComparable key, TreapNode tNode)
		{
			if(tNode == null)
				return null;
			
			int result = key.CompareTo(tNode.Key);
			
			if(result < 0)
				tNode.Left = Delete(key, tNode.Left);
			else
            if(result > 0)
                tNode.Right = Delete(key, tNode.Right);
			else
			{
				boolKeyFound    = true;
				prevData        = tNode.Data;
				tNode           = tNode.DeleteRoot();
			}
			
			return tNode;
		}
		///<summary>
		/// Equals
		///<summary>
		public override bool Equals(object obj)
		{
			if(obj == null)
				return false;
			
			if(!(obj is Treap ))
				return false;
			
			if(this == obj)
				return true;
			
			return (ToString().Equals(((Treap)(obj)).ToString()));
			
		}
		///<summary>
		/// HashCode
		///<summary>
		public override int GetHashCode()
		{
			return intHashCode;
		}
		///<summary>
		/// ToString
		///<summary>
		public override string ToString()
		{
			return strIdentIfier.ToString();
		}
	}
}

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 | Terms of Use | Mobile
Web04 | 2.8.141223.1 | Last Updated 15 Sep 2004
Article Copyright 2004 by RoyClem
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid