avltree.cs

classic tsp analysis method with c++ !

using System;
using HRD.Core;

namespace HRD.AVL
{
	public class AVLTree : IAVLTree
	{
		protected class AVLNode
		{
			public int info;
			public int bfactor;
			public AVLNode llink;
			public AVLNode rlink;
		} 
    
		protected AVLNode root;
		protected bool isTaller;
		private bool isDuplicate = false;
    
		public AVLTree()  
		{
			root = null;
			isTaller = false;
		}
       
		public bool Insert(int n)
		{
			isTaller = false;
			AVLNode  newNode;
			AVLNode  tempRoot;
    
			newNode = new AVLNode();
			newNode.info = n;
			newNode.bfactor = 0;
			newNode.llink = null;
			newNode.rlink = null;
    
			this.isDuplicate = false;
			root = insertIntoAVL(root, newNode);
			
			return !isDuplicate;
		}

		public void DestroyTree()
		{
			root = null;
		}

		public void InorderTraversal()
		{
			inorder(root);
		}

		#region Private Functions

		private AVLNode rotateToLeft(AVLNode root)
		{
			AVLNode p; //reference variable to the root of the right subtree of root
			if(root == null)
				throw new Exception("Error in the tree.");
			else if(root.rlink == null)
				throw new Exception("Error in the tree: No right subtree to rotate.");
			else
			{
				p = root.rlink;
				root.rlink = p.llink; //the left subtree of p becomes the right subtree of root
				p.llink = root; 
				root = p;   //make p the new root node
			}
    
			return root;
		}
    
		private AVLNode rotateToRight(AVLNode root)
		{
			AVLNode p;  //reference variable to the root of the left subtree of root
    
			if(root == null)
				throw new Exception("Error in the tree.");
			else if(root.llink == null)
				throw new Exception("Error in the tree: No left subtree to rotate.");
			else
			{
				p = root.llink;
				root.llink = p.rlink; //the right subtree of p becomes the left subtree of root
				p.rlink = root; 
				root = p;    //make p the new root node
			}
    
			return root;
		}

		private AVLNode balanceFromLeft(AVLNode root)
		{
			AVLNode p;
			AVLNode w;
    
			p = root.llink;   //p points to the left subtree of root
    
			switch(p.bfactor)
			{
				case -1: 
					root.bfactor = 0;
					p.bfactor = 0;
					root = rotateToRight(root);
					break;
				case 0:  
					throw new Exception("Error: Cannot balance from the left.");
				case 1:  
					w = p.rlink;
					if(w.bfactor == -1)
					{
						root.bfactor = 1;
						p.bfactor = 0;
					}
					else if(w.bfactor == 0)
					{
						root.bfactor = 0;
						p.bfactor = 0;
					}
					else if(w.bfactor == 1)
					{
						root.bfactor = 0;
						p.bfactor = -1;
					}
    
					w.bfactor = 0;    
					p = rotateToLeft(p);
					root.llink = p;
					root = rotateToRight(root);
					break;
			}
    
			return root;
		}
    
		private AVLNode balanceFromRight(AVLNode root)
		{
			AVLNode p;
			AVLNode w;
    
			p = root.rlink;   //p points to the right subtree of root
    
			switch(p.bfactor)
			{
				case -1: 
					w = p.llink;
					if(w.bfactor == -1)
					{
						root.bfactor = 0;
						p.bfactor = 1;
					}
					else if(w.bfactor == 0)
					{
						root.bfactor = 0;
						p.bfactor = 0;
					}
					else if(w.bfactor == 1)
					{
						root.bfactor = -1;
						p.bfactor = 0;
					}
					w.bfactor = 0;    
					p = rotateToRight(p);
					root.rlink = p;
					root = rotateToLeft(root);
					break;
				case 0:  
					throw new Exception("Error: Cannot balance from the right.");
				case 1:  
					root.bfactor = 0;
					p.bfactor = 0;
					root = rotateToLeft(root);
					break;
			}
    
			return root;
		}

		private AVLNode insertIntoAVL(AVLNode root, AVLNode newNode)
		{
			if(root == null)
			{
				root = newNode;
				isTaller = true;
			}
			else if(root.info == newNode.info)
				isDuplicate = true;
				//throw new Exception("No duplicates are allowed.");
			else if(root.info > newNode.info) //newNode goes in the left subtree
			{
				root.llink = insertIntoAVL(root.llink, newNode);
    
				if(isTaller)             //after insertion, the subtree grew in height
					switch(root.bfactor)
					{
						case -1: root = balanceFromLeft(root);
							isTaller = false;
							break;
						case 0:  root.bfactor = -1;
							isTaller = true;
							break;
						case 1:  root.bfactor = 0;
							isTaller = false;
							break;
					}
			}
			else
			{
				root.rlink = insertIntoAVL(root.rlink, newNode);
    
				if(isTaller)              //after insertion, the subtree grew in height
					switch(root.bfactor)
					{
						case -1: root.bfactor = 0;
							isTaller = false;
							break;
						case 0:  root.bfactor = 1;
							isTaller = true;
							break;
						case 1:  root = balanceFromRight(root);
							isTaller = false;
							break;
					}
			}
    
			return root;
		}

		private void inorder(AVLNode p)
		{
			if(p != null)
			{
				inorder(p.llink);
				Console.WriteLine(p.info + " ");
				inorder(p.rlink);
			}
		}

		#endregion
	
		#region Propertys

		public bool IsEmpty
		{
			get
			{
				return (root == null);
			}
		}

		#endregion

	}
}