Sunday, May 29, 2011

Implementation of AVL Tree

In this post I will give the C program for the implementation of AVL tree.

AVL TREE


In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented.In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

ALGORITHM


Program written based on the algorithm given in the book "Data Structures and Algorithm Analysis in C " written by Mark Allen Weiss.

PROGRAM



#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct avlnode;
typedef struct avlnode *position;
typedef struct avlnode *avltree;
struct avlnode
{
  int element;
  avltree left;
  avltree right;
  int height;
};

avltree makeempty(avltree T)
{
  if(T!=NULL)
  {
    makeempty(T->left);
    makeempty(T->right);
    free(T);
  }
  return NULL;
}

position find(int X,avltree T)
{
  if(T==NULL)
    return NULL;
  if(X<T->element)
    return find(X,T->left);
  else if(X>T->element)
    return find(X,T->right);
  else
    return T;
}

static int height(position p)
{
  if(p==NULL)
    return -1;
  else
    return p->height;
}

static int max(int lhs,int rhs)
{
  return lhs>rhs ? lhs : rhs;
}

static position singlerotatewithleft(position k2)
{
  position k1;
  k1=k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = max(height(k2->left),height(k2->right))+1;
  k1->height = max(height(k1->left),k2->height)+1;
  return k1;
}

static position singlerotatewithright(position k1)
{
  position k2;
  k2=k1->right;
  k1->right = k2->left;
  k2->left = k1;
  k1->height = max(height(k1->left),height(k1->right))+1;
  k2->height = max(height(k2->right),k1->height)+1;
  return k2;
}

static position doublerotatewithleft(position k3)
{
  k3->left = singlerotatewithright(k3->left);
  return singlerotatewithleft(k3);
}

static position doublerotatewithright(position k1)
{
  k1->right = singlerotatewithleft(k1->right);
  return singlerotatewithright(k1);
}

//////Insert routine

avltree insert(int X,avltree T)
{
  if(T==NULL)
  {
    T=(avlnode*)malloc(sizeof(struct avlnode));
    if(T==NULL)
      return NULL;
    else
    {
      T->element=X;
      T->height=0;
      T->left=T->right=NULL;
    }
  }
  else if(X<T->element)
  {
    T->left = insert(X,T->left);
    if(height(T->left)-height(T->right)==2)
    {
      if(X<T->left->element)
T = singlerotatewithleft(T);
      else
T = doublerotatewithleft(T);
    }
  }
  else if(X>T->element)
  {
    T->right=insert(X,T->right);
    if(height(T->right)-height(T->left)==2)
    {
      if(X>T->right->element)
T= singlerotatewithright(T);
      else
T=doublerotatewithright(T);
    }
  }
  T->height = max(height(T->left),height(T->right))+1;
  return T;
}

inorder(avltree ptr)
{
  if(ptr!=NULL)
  {
     inorder(ptr->left);
     printf("%d ",ptr->element);
     inorder(ptr->right);
  }
}

display(avltree ptr,int level)
{
  int i;
  if(ptr!=NULL)
  {
    display(ptr->right,level+1);
    printf("\n");
    for(i=0;i<level;i++)
      printf(" ");
    printf("%d",ptr->element);
    display(ptr->left,level+1);
  }
}

void main()
{
  clrscr();
  int choice=0,data;
  avltree T;
  position p;
  T=makeempty(NULL);
  while(1)
  {
    printf("\n\n 1.Insert");
    printf("\n\n 2.Display");
    printf("\n\n 3.Exit\n");
    printf("\n\n Enter your choice:");
    scanf("%d",&choice);
    if(choice==3)
      break;
    switch(choice)
    {
      case 1:
printf("\n\n Enter the value to be inserted:");
scanf("%d",&data);
if(find(data,T)==NULL)
    T=insert(data,T);
else
  printf("\n\n Duplicate value ignored\n");
break;
      case 2:
if(T==NULL)
{
  printf("\n Empty tree...");
  continue;
}
printf("\n\n");
display(T,1);
printf("\n\n Inorder traversal of Tree is:");
inorder(T);
break;
      default:
printf("\n wrong choice...");
break;
    }
  }
  getch();
}



OUTPUT


1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:23

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:16

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:35

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:12

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:24

1.Insert
2.Display
3.Exit

Enter your choice:2


35
   24
23
  16
   12



Inorder traversal of Tree is:12 16 23 24 35

1.Insert
2.Display
3.Exit

Enter your choice:3

Sunday, May 1, 2011

Ubuntu 11.04 Screenshots

I downloaded Ubuntu 11.04 on its release date (28th of April) and found it really good...Hmmm where to begin??? First the ubuntu's attempt to shift the focus from gnome to its Unity interface...It may be looking odd in the beginning but I am sure we will be used to it as the time progresses...Given below are some screenshots of my computer loaded with ubuntu 11.04..

The new looking Desktop




Ubuntu now comes with a preloaded Banshee Meida Player

When you play those media files you will find it getting added to the panel in the 'audio' control side.



A new looking Application Browser



The Desktop Switcher


This version is considered to be the perfect replacement for Windows..;)