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
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>
/// The TreapNode class encapsulates a node in the treap
///</summary>

using System;
using System.Text;

namespace TreapCS
{
	public class TreapNode
	{
		// key provided by the calling class
		private IComparable ordKey;
		// the data or value associated with the key
		private object objData;
		// random priority to balance the tree
		private int intPriority;
		// left node of the tree
		private TreapNode tnLeft;
		// right node of the tree
		private TreapNode tnRight;
		
		///<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>
		///Priority
		///</summary>
		public int Priority
		{
			get
            {
				return intPriority;
			}
			
			set
			{
				intPriority = value;
			}
		}
		///<summary>
		///Left
		///</summary>
		public TreapNode Left
		{
			get
            {
				return tnLeft;
			}
			
			set
			{
				tnLeft = value;
			}
		}
		///<summary>
		/// Right
		///</summary>
		public TreapNode Right
		{
			get
            {
				return tnRight;
			}
			
			set
			{
				tnRight = value;
			}
		}
		///<summary>
		/// RotateLeft
		/// Rebalance the tree by rotating the nodes to the left
		///</summary>
		public TreapNode RotateLeft()
		{
			
			TreapNode temp  = Right;
			Right           = Right.Left;
			temp.Left       = this;
			
			return temp;
		}
		///<summary>
		/// RotateRight
		/// Rebalance the tree by rotating the nodes to the right
		///</summary>
		public TreapNode RotateRight()
		{
			TreapNode temp  = Left;
			Left            = Left.Right;
			temp.Right      = this;
			
			return temp;
		}
		///<summary>
		/// DeleteRoot
		/// If one of the children is an empty subtree, remove the root and put the other
		/// child in its place. If both children are nonempty, rotate the treapTree at
		/// the root so that the child with the smallest priority number comes to the
		/// top, then delete the root from the other subtee.
		///
		/// NOTE: This method is recursive
		///</summary>
		public TreapNode DeleteRoot()
		{
			TreapNode temp;
			
			if(Left == null)
				return Right;
			
			if(Right == null)
				return Left;
			
            if(Left.Priority < Right.Priority)
            {
                temp        = RotateRight();
                temp.Right  = DeleteRoot();
            }
            else
            {
                temp        = RotateLeft();
                temp.Left   = DeleteRoot();
            }

			return temp;
		}
	}
}

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)

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