#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    1
    Rep Power
    0

    AVL TREE implementation


    Dear friends well at university i wrote this implementation of avl tree like 7 years ago and i wanted to share it with you...the problem is that i almost forget much aspects of what i wrote because of the 7 years but i thought it would be cool to share it after all these years

    Code:
    	# include<stdio.h>
    	# include<stdlib.h>
    	typedef struct tree_pointer
    	{
    	  int data;
    	 struct tree_pointer *left,*right;
    	};
      int balance_factor(struct tree_pointer *t);
      void inorder_display(struct tree_pointer *t)
      {
    	 if(t)
    		  {
    			 inorder_display(t->left) ;
    			 printf("%d\t",t->data);
    			 printf("Balance factor of %d is (%d)\t",t->data,balance_factor(t));
    			 inorder_display(t->right);
    		  }
    	}
    
    	struct tree_pointer* bst_searching(struct tree_pointer *t,int x )
    	  {
    		 if(!t)
    			return NULL;
    		 else
    		 {
    			 if(x==t->data)
    				return t;
    
    			 else
    				if(x<t->data)
    				  return bst_searching(t->left, x );
    				else
    					 return bst_searching(t->right, x );
    		}
    	 }
    
    
      int tree_high(struct tree_pointer *t)
      {
      int right,left;
    		if (t!=NULL)
    		{
    		right = tree_high(t->right);
    		right++;
    		left = tree_high(t->left);
    		left++;
    		
    
    		if ( left >=right)
    		return left;
    		else
    		return right;
    		}
    		else
    		return -1;
      }
    
    
    
    
    	int balance_factor(struct tree_pointer *t)
      {
      int l,r;
      l=tree_high(t->left);
      r=tree_high(t->right);
      return l-r;
      }
    
    /************************************************************DELETION*/
    /************************************************************DELETION*/
    /************************************************************DELETION*/
    int bst_delete(struct tree_pointer **t,int x)
    	 {
    		int i;
    		struct tree_pointer *p,*pp,*s,*ps,*c,*v[100];
    		  p=*t;
    		  pp=NULL;
    		 i=0;
    		 while(p && p->data!=x)
    			{
    			  pp=p;
    			  v[i]=p;
    			  i++;
    
    				 if(x<p->data)
    					p=p->left;
    				 else
    				  p=p->right;
    			}
    		 
    
    			if(p==NULL)
    				{
    				printf("null\n");
    				return 0;
    				}
    				if(p->left!=NULL && p->right!=NULL)
    				  {
    					 v[i]=p;
    					 i++;
    					 s=p->left;
    					 ps=p;
    					 
    					while(s->right)
    					  {
    						ps=s;
    						v[i]=s;
    						s=s->right;
    						printf("v[%d]=%d",i,v[i]);
    						printf("v[%d]->date =%d \n",i,v[i]->data);
    					  i++;
    
    					  }
    
    					  p->data=s->data;
    						 p=s;
    						 pp=ps;
    
    					}
    						  if(p->right==NULL)
    							 {
    							 c=p->left;
    							 v[i]=c;
    
    							 }
    							  else
    							  if (p->left==NULL)
    								{
    								c=p->right;
    								v[i]=c;
    
    								}
    
    							  if (p==(*t))
    								  (*t)=c;
    								  if(p==pp->left)
    									  pp->left=c;
    
    									else
    										pp->right=c;
    								 if(c==NULL)
    								 i--;
    
    
    								free (p);
    
    p=pp=NULL;
    		while (i>=0)
    		{
    
    			if (balance_factor(v[i]) == 2 && ((balance_factor(v[i]->left)== 0) || (balance_factor(v[i]->left)==1)) )
    				{
    				p=v[i]->left;
    				v[i]->left=p->right;
    				p->right=v[i];
    
    					if (i!=0)
    						{
    						if(v[i-1]->left==v[i])
    						v[i-1]->left=p;
    						else
    						v[i-1]->right=p;
    						}
    					else
    					*t=p;
    				
    				}
    			else
    				if ((balance_factor(v[i]) == 2) && balance_factor(v[i]->left)== -1)
    				{
    				p=v[i]->left;
    				pp=p->right;
    				p->right =pp->left;
    				v[i]->left=pp->right;
    				pp->right=v[i];
    				pp->left=p;
    					if (i!=0)
    						{
    						if (v[i-1]->right==v[i])
    						v[i-1]->right=pp;
    						else
    						v[i-1]->left=pp;
    						}
    					else
    					*t=pp;
    				
    				}
    
    			else
    				if ((balance_factor(v[i]) == -2) && (balance_factor(v[i]->right)== 0 || balance_factor(v[i]->right)==-1) )
    				{
    				p=v[i]->right;
    				v[i]->right=p->left;
    				p->left=v[i];
    
    					if (i!=0)
    						{
    						if(v[i-1]->left==v[i])
    						v[i-1]->left=p;
    						else
    						v[i-1]->right=p;
    						}
    					else
    					*t=p;
    				}
    			else
    			 if ((balance_factor(v[i]) == -2) && balance_factor(v[i]->right)== 1)
    				{
    				p=v[i]->right;
    				pp=p->left;
    				p->left =pp->right;
    				v[i]->right=pp->left;
    				pp->right=p;
    				pp->left=v[i];
    					if (i!=0)
    						{
    						if (v[i-1]->right==v[i])
    						v[i-1]->right=pp;
    						else
    						v[i-1]->left=pp;
    						}
    					else
    					*t=pp;
    				
    				}
    		i--;
    		
    		}
    
    
    return 0;
    }
    
    /********************************************************************INSERTION*/
    /********************************************************************INSERTION*/
     int insert(struct tree_pointer **t,int v)
     {
     int r,i=0,l=0;
     struct tree_pointer *p,*oldp,*x[50];
     p=*t;
    
    		if (*t==NULL)
    		{
    			(*t)=(struct tree_pointer *)malloc(sizeof(struct tree_pointer));
    			(*t)->data=v;
    			(*t)->left=(*t)->right=NULL;
    		}
    
    	while (p!=NULL)
    	{
    	  x[i]=p;
    	  i++;
    		if ( v >p->data)
    		{
    			oldp=p;
    			r=0;
    			p=p->right;
    		}
    		else
    		{
    			oldp=p;
    			r=1;
    			p=p->left;
    		}
    
    	}
     if(i>=1)
     {
     p=(struct tree_pointer *)malloc(sizeof(struct tree_pointer));
     p->data=v;
     p->left=p->right = NULL;
     x[i]=p;
     if (r==0)
     oldp->right = p;
     else
     oldp->left = p;
     }
     
    if(i>=2)
    	{
       i=i-2;
    		while (i>=0)
    		{
    
    			if ((balance_factor(x[i]) == 2) && (x[i+1]->left == x[i+2]))
    				{
    				x[i]->left=x[i+1]->right;
    				x[i+1]->right=x[i];
    
    					if (i!=0)
    						{
    						if(x[i-1]->left==x[i])
    						x[i-1]->left=x[i+1];
    						else
    						x[i-1]->right=x[i+1];
    						}
    					else
    					*t=x[i+1];
    				l=1;
    				}
    			else
    				if ((balance_factor(x[i]) == 2) && (x[i+1]->right == x[i+2]))
    				{
    				x[i+1]->right=x[i+2]->left;
    				x[i]->left=x[i+2]->right;
    				x[i+2]->left=x[i+1];
    				x[i+2]->right=x[i];
    					if (i!=0)
    						{
    						if (x[i-1]->right==x[i])
    						x[i-1]->right=x[i+2];
    						else
    						x[i-1]->left=x[i+2];
    						}
    					else
    					*t=x[i+2];
    				l=1;
    				}
    
    			else
    			  if ((balance_factor(x[i]) == -2) && (x[i+1]->right == x[i+2]))
    			  {
    			  x[i]->right=x[i+1]->left;
    			  x[i+1]->left=x[i];
    					if(i!=0)
    					{
    					if(x[i-1]->right==x[i])
    					x[i-1]->right=x[i+1];
    					else
    					x[i-1]->left=x[i+1];
    					}
    			  else
    			  *t=x[i+1];
    			  l=1;
    			  }
    			else
    			 if ((balance_factor(x[i]) == -2) && (x[i+1]->left == x[i+2]))
    			 {
    			 x[i]->right=x[i+2]->left;
    			 x[i+1]->left=x[i+2]->right;
    			 x[i+2]->left=x[i];
    			 x[i+2]->right=x[i+1];
    					if(i!=0)
    					{
    					if(x[i-1]->right==x[i])
    					x[i-1]->right=x[i+2];
    					else
    					x[i-1]->left=x[i+2];
    					}
    			 else
    			 *t=x[i+2];
    			 l=1;
    			 }
    
    
    
    		i--;
    		if(l==1)
    		return 0;
    		}
    		
    	}
    return 0;
    }
    
    
    
    
    
    
    
    
    
    
     void main()
    {
    struct tree_pointer *t=NULL,*z=NULL;
    int n,v,m,j,d;
    	  printf("Enter the values contained in the tree (when u want to stop press -1):");
    
    		scanf("%d",&v);
    
    		 while (v!=-1)
    		 {
    		 insert(&t,v);
    		 scanf("%d",&v);
    		 }
    	  do
    	 {
    	 printf("\t\t\t Available List:\n");
    	 printf("\t\t\t 1 --> Insert in bst\n");
    	 printf("\t\t\t 2 --> Inorder display of bst\n");
    	 printf("\t\t\t 3 --> Delete\n");
    	 printf("\t\t\t 4 --> Search for target value\n");
    	 printf("Enter your choice:\n");
    	 scanf("%d",&d);
    	 }
    	 while (d!=1 && d!=2 && d!=3 &&  d!=4 );
    	 switch(d)
    	 {
    		case 1:
    		printf("Enter the value you want to insert: ");
    		scanf("%d",&n);
    		insert(&t,n);
    		printf("The inorder display after insertion is:\n");
    		inorder_display(t);
    		break;
    		case 2:
    		printf("The inorder display is:\n");
    		inorder_display (t);
    		break;
    		case 3:
    		printf("Enter the value you want to delete: ");
    		scanf("%d",&m);
    		bst_delete(&t,m);
    		printf("The inorder display after deletion is:\n");
    		inorder_display(t);
    
    
    		break;
    		case 4:
    		printf("enter the number you want to search for\n");
    		scanf("%d",&j);
    		z=bst_searching(t,j);
    		printf("the address of the target is :%d ",z);
    
    
    		break;
    		default:
    		printf("Not Valid CHOICE!!");
    		}
    		printf("\n");
    
    
    
    
    
    }
    BTW this code has been wrote and compiled under Borland C++.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Code tags will make your code easier to read:

    http://forums.devshed.com/misc.php?do=bbcode#code

    Edit your original post, strip out the mess that's supposed to be source code, drop the open and closing code tags in there, then copy your source code directly from your source editor in between the tags. That will preserve the formatting and make it readable.

    Read the sticky notes at the top of this forum!

    Comments on this post

    • SimonB2 agrees
    I no longer wish to be associated with this site.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2013
    Posts
    40
    Rep Power
    19
    Thank you for sharing!

IMN logo majestic logo threadwatch logo seochat tools logo