Tweet
# include<stdio.h>
# include<malloc.h>
# define F 0
# define T 1
typedef struct NODE
{
char Info;
int Flag;
struct NODE *Left_Child;
struct NODE *Right_Child;
}nd;
nd *Binary_Tree (char , nd *, int *);
void Output(nd *, int );
struct NODE *Balance_Right_Heavy(nd *, int *);
nd *Balance_Left_Heavy(nd *, int *);
nd *DELETE(nd *, nd *, int *);
nd *Delete_Element(nd *, char , int *);
nd * Binary_Tree (char Info, nd *Parent, int *H)
{
nd *Node1;
nd *Node2;
if(!Parent)
{
Parent = (nd *) malloc(sizeof(nd));
Parent->Info = Info;
Parent->Left_Child = NULL;
Parent->Right_Child = NULL;
Parent->Flag = 0;
*H = T;
return (Parent);
}
if(Info < Parent->Info)
{
Parent->Left_Child = Binary_Tree(Info, Parent->Left_Child, H);
if(*H)
{
switch(Parent->Flag)
{
case 1: /* Right heavy */
Parent->Flag = 0;
*H = F;
break;
case 0: /* Balanced tree */
Parent->Flag = -1;
break;
case -1: /* Left heavy */
Node1 = Parent->Left_Child;
if(Node1->Flag == -1)
{
printf("\n Left to Left Rotation\n");
Parent->Left_Child= Node1->Right_Child;
Node1->Right_Child = Parent;
Parent->Flag = 0;
Parent = Node1;
}
else
{
printf("\n Left to right rotation\n");
Node2 = Node1->Right_Child;
Node1->Right_Child = Node2->Left_Child;
Node2->Left_Child = Node1;
Parent->Left_Child = Node2->Right_Child;
Node2->Right_Child = Parent;
if(Node2->Flag == -1)
Parent->Flag = 1;
else
Parent->Flag = 0;
if(Node2->Flag == 1)
Node1->Flag = -1;
else
Node1->Flag = 0;
Parent = Node2;
}
Parent->Flag = 0;
*H = F;
}
}
}
if(Info > Parent->Info)
{
Parent->Right_Child = Binary_Tree(Info, Parent->Right_Child, H);
if(*H)
{
switch(Parent->Flag)
{
case -1: /* Left heavy */
Parent->Flag = 0;
*H = F;
break;
case 0: /* Balanced tree */
Parent->Flag = 1;
break;
case 1: /* Right heavy */
Node1 = Parent->Right_Child;
if(Node1->Flag == 1)
{
printf("\n Right to Right Rotation\n");
Parent->Right_Child= Node1->Left_Child;
Node1->Left_Child = Parent;
Parent->Flag = 0;
Parent = Node1;
}
else
{
printf("\n Right to Left Rotation\n");
Node2 = Node1->Left_Child;
Node1->Left_Child = Node2->Right_Child;
Node2->Right_Child = Node1;
Parent->Right_Child = Node2->Left_Child;
Node2->Left_Child = Parent;
if(Node2->Flag == 1)
Parent->Flag = -1;
else
Parent->Flag = 0;
if(Node2->Flag == -1)
Node1->Flag = 1;
else
Node1->Flag = 0;
Parent = Node2;
}
Parent->Flag = 0;
*H = F;
}
}
}
return(Parent);
}
void Output(nd *Tree,int Level)
{
int i;
if (Tree)
{
Output(Tree->Right_Child, Level+1);
printf("\n");
for (i = 0; i < Level; i++)
printf(" ");
printf("%c", Tree->Info);
Output(Tree->Left_Child, Level+1);
}
}
nd * Balance_Right_Heavy(nd *Parent, int *H)
{
nd *Node1, *Node2;
switch(Parent->Flag)
{
case -1:
Parent->Flag = 0;
break;
case 0:
Parent->Flag = 1;
*H= F;
break;
case 1: /* Rebalance */
Node1 = Parent->Right_Child;
if(Node1->Flag >= 0)
{
printf("\n Right to Right Rotation\n");
Parent->Right_Child= Node1->Left_Child;
Node1->Left_Child = Parent;
if(Node1->Flag == 0)
{
Parent->Flag = 1;
Node1->Flag = -1;
*H = F;
}
else
{
Parent->Flag = Node1->Flag = 0;
}
Parent = Node1;
}
else
{
printf("\n Right to Left Rotation\n");
Node2 = Node1->Left_Child;
Node1->Left_Child = Node2->Right_Child;
Node2->Right_Child = Node1;
Parent->Right_Child = Node2->Left_Child;
Node2->Left_Child = Parent;
if(Node2->Flag == 1)
Parent->Flag = -1;
else
Parent->Flag = 0;
if(Node2->Flag == -1)
Node1->Flag = 1;
else
Node1->Flag = 0;
Parent = Node2;
Node2->Flag = 0;
}
}
return(Parent);
}
nd * Balance_Left_Heavy(nd *Parent, int *H)
{
nd *Node1, *Node2;
switch(Parent->Flag)
{
case 1:
Parent->Flag = 0;
break;
case 0:
Parent->Flag = -1;
*H= F;
break;
case -1: /* Rebalance */
Node1 = Parent->Left_Child;
if(Node1->Flag <= 0)
{
printf("\n Left to Left Rotation\n");
Parent->Left_Child= Node1->Right_Child;
Node1->Right_Child = Parent;
if(Node1->Flag == 0)
{
Parent->Flag = -1;
Node1->Flag = 1;
*H = F;
}
else
{
Parent->Flag = Node1->Flag = 0;
}
Parent = Node1;
}
else
{
printf("\n Left to Right Rotation\n");
Node2 = Node1->Right_Child;
Node1->Right_Child = Node2->Left_Child;
Node2->Left_Child = Node1;
Parent->Left_Child = Node2->Right_Child;
Node2->Right_Child = Parent;
if(Node2->Flag == -1)
Parent->Flag = 1;
else
Parent->Flag = 0;
if(Node2->Flag == 1)
Node1->Flag = -1;
else
Node1->Flag = 0;
Parent = Node2;
Node2->Flag = 0;
}
}
return(Parent);
}
nd * DELETE(nd *R, nd *Temp, int *H)
{
nd *Dnode = R;
if( R->Right_Child != NULL)
{
R->Right_Child = DELETE(R->Right_Child, Temp, H);
if(*H)
R = Balance_Left_Heavy(R, H);
}
else
{
Dnode = R;
Temp->Info = R->Info;
R = R->Left_Child;
free(Dnode);
*H = T;
}
return(R);
}
nd * Delete_Element(nd *Parent, char Info, int *H)
{
nd *Temp;
if(!Parent)
{
printf("\n Information does not exist");
return(Parent);
}
else
{
if (Info < Parent->Info )
{
Parent->Left_Child = Delete_Element(Parent->Left_Child, Info, H);
if(*H)
Parent = Balance_Right_Heavy(Parent, H);
}
else
if(Info > Parent->Info)
{
Parent->Right_Child=Delete_Element(Parent->Right_Child,Info,H);
if(*H)
Parent = Balance_Left_Heavy(Parent, H);
}
else
{
Temp= Parent;
if(Temp->Right_Child == NULL)
{
Parent = Temp->Left_Child;
*H = T;
free(Temp);
}
else
if(Temp->Left_Child == NULL)
{
Parent = Temp->Right_Child;
*H = T;
free(Temp);
}
else
{
Temp->Left_Child = DELETE(Temp->Left_Child, Temp, H);
if(*H)
Parent = Balance_Right_Heavy(Parent, H);
}
}
}
return(Parent);
}
main()
{
int H;
char Info ;
char choice;
nd *Tree = (nd *)malloc(sizeof(nd));
Tree = NULL;
printf("\n Input choice 'b' to break:");
choice = getchar();
while(choice != 'b')
{
fflush(stdin);
printf("\n Input information of the node: ");
scanf("%c", &Info);
Tree = Binary_Tree(Info, Tree, &H);
printf("\n Tree is:\n");
Output(Tree, 1);
fflush(stdin);
printf("\n Input choice 'b' to break:");
choice = getchar();
}
while(1)
{
printf("\n Input choice 'b' to break:");
printf("\n Input the key value want to deletedir:");
scanf("%c", &Info);
if (Info == 'b')
break;
Tree = Delete_Element(Tree, Info, &H);
printf("\n Tree is:\n");
Output(Tree, 1);
}
}
AVL Tree Programming in C
