An AVL
tree is a self-balancing binary search tree. 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. The
AVL tree is named after its two Soviet inventors, G. M. Adelson-Velskii and E. M.
Landis.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1
typedef
struct nodes
{
char
Data;
struct Anode *Left;
struct Anode *Right;
int
status;
}Anode;
Anode
* Right_Bal(Anode *Root, int *Num)
{
Anode
*Ptr1, *Ptr2;
switch(Root->status)
{
case
-1:
Root->status
= 0;
break;
case
0:
Root->status = 1;
*Num=
FALSE;
break;
case
1:
Ptr1
= Root->Right;
if(Ptr1->status
>= 0)
{
Root->Right=
Ptr1->Left;
Ptr1->Left
= Root;
if(Ptr1->status
== 0)
{
Root->status
= 1;
Ptr1->status
= -1;
*Num
= FALSE;
}
else
{
Root->status
= Ptr1->status = 0;
}
Root
= Ptr1;
}
else
{
Ptr2
= Ptr1->Left;
Ptr1->Left
= Ptr2->Right;
Ptr2->Right
= Ptr1;
Root->Right
= Ptr2->Left;
Ptr2->Left
= Root;
if(Ptr2->status
== 1)
Root->status
= -1;
else
Root->status
= 0;
if(Ptr2->status
== -1)
Ptr1->status
= 1;
else
Ptr1->status
= 0;
Root = Ptr2;
Ptr2->status
= 0;
}
}
return(Root);
}
Anode
* Left_Bal(Anode *Root, int *Num)
{
Anode
*Ptr1, *Ptr2;
switch(Root->status)
{
case
1:
Root->status
= 0;
break;
case
0:
Root->status
= -1;
*Num=
FALSE;
break;
case
-1:
Ptr1
= Root->Left;
if(Ptr1->status
<= 0)
{
Root->Left=
Ptr1->Right;
Ptr1->Right
= Root;
if(Ptr1->status
== 0)
{
Root->status
= -1;
Ptr1->status
= 1;
*Num
= FALSE;
}
else
{
Root->status = Ptr1->status
= 0;
}
Root
= Ptr1;
}
else
{
Ptr2
= Ptr1->Right;
Ptr1->Right
= Ptr2->Left;
Ptr2->Left
= Ptr1;
Root->Left
= Ptr2->Right;
Ptr2->Right
= Root;
if(Ptr2->status
== -1)
Root->status
= 1;
else
Root->status
= 0;
if(Ptr2->status
== 1)
Ptr1->status
= -1;
else
Ptr1->status
= 0;
Root = Ptr2;
Ptr2->status
= 0;
}
}
return(Root);
}
Anode * Replace(Anode *R, Anode
*Tmp, int *Num)
{
Anode
*rNode = R;
if(
R->Right != NULL)
{
R->Right
= Replace(R->Right, Tmp, Num);
if(*Num)
R =
Left_Bal(R, Num);
}
else
{
rNode = R;
Tmp->Data
= R->Data;
R = R->Left;
free(rNode);
*Num = TRUE;
}
return(R);
}
Anode *Del(Anode *Root, char
Data, int *Num)
{
Anode
*Tmp;
if(!Root)
{
printf("\n\tEmpty
Tree!!!\n");
return(Root);
}
else
{
if
(Data < Root->Data )
{
Root->Left
= Del
if(*Num)
Root
= Right_Bal(Root, Num);
}
else
if(Data
> Root->Data)
{
Root->Right
= Del
if(*Num)
Root
= Left_Bal(Root, Num);
}
else
{
Tmp=
Root;
if(Tmp->Right
== NULL)
{
Root
= Tmp->Left;
*Num
= TRUE;
free(Tmp);
}
else
if(Tmp->Left == NULL)
{
Root
= Tmp->Right;
*Num
= TRUE;
free(Tmp);
}
else
{
Tmp->Left
= Replace(Tmp->Left, Tmp, Num);
if(*Num)
Root
= Right_Bal(Root, Num);
}
}
}
return(Root);
}
Anode
* Insert (char Data, Anode *Root, int
*Num)
{
Anode
*Ptr1;
Anode
*Ptr2;
if(!Root)
{
Root
= (Anode *) malloc(sizeof(Anode));
Root->Data
= Data;
Root->Left
= NULL;
Root->Right
= NULL;
Root->status
= 0;
*Num
= TRUE;
return
(Root);
}
if(Data
< Root->Data)
{
Root->Left
= Insert(Data, Root->Left, Num);
if(*Num)
{
switch(Root->status)
{
case
1:
Root->status
= 0;
*Num
= FALSE;
break;
case
0:
Root->status
= -1;
break;
case
-1:
Ptr1
= Root->Left;
if(Ptr1->status
== -1)
{
Root->Left=
Ptr1->Right;
Ptr1->Right
= Root;
Root->status
= 0;
Root
= Ptr1;
}
else
{
Ptr2
= Ptr1->Right;
Ptr1->Right
= Ptr2->Left;
Ptr2->Left
= Ptr1;
Root->Left
= Ptr2->Right;
Ptr2->Right
= Root;
if(Ptr2->status
== -1)
Root->status
= 1;
else
Root->status
= 0;
if(Ptr2->status
== 1)
Ptr1->status
= -1;
else
Ptr1->status
= 0;
Root = Ptr2;
}
Root->status
= 0;
*Num
= FALSE;
}
}
}
if(Data
> Root->Data)
{
Root->Right
= Insert(Data, Root->Right, Num);
if(*Num)
{
switch(Root->status)
{
case
-1:
Root->status
= 0;
*Num
= FALSE;
break;
case
0:
Root->status
= 1;
break;
case
1:
Ptr1
= Root->Right;
if(Ptr1->status
== 1)
{
Root->Right=
Ptr1->Left;
Ptr1->Left
= Root;
Root->status
= 0;
Root
= Ptr1;
}
else
{
Ptr2
= Ptr1->Left;
Ptr1->Left
= Ptr2->Right;
Ptr2->Right
= Ptr1;
Root->Right
= Ptr2->Left;
Ptr2->Left
= Root;
if(Ptr2->status
== 1)
Root->status
= -1;
else
Root->status
= 0;
if(Ptr2->status
== -1)
Ptr1->status
= 1;
else
Ptr1->status
= 0;
Root = Ptr2;
}
Root->status
= 0;
*Num
= FALSE;
}
}
}
return(Root);
}
void
Disp(Anode *Tnode,int Level)
{
int
i;
if
(Tnode)
{
Disp(Tnode->Right,
Level+1);
printf("%c
- ", Tnode->Data);
Disp(Tnode->Left,
Level+1);
}
}
void
main()
{
int
Num;
char
Data ;
int
ch;
Anode
*Tnode = (Anode *)malloc(sizeof(Anode));
Tnode
= NULL;
clrscr();
while(ch
!= 4)
{
printf("\n\t1. Create
\n\t2. Display \n\t3. Delete \n\t4. Exit");
printf("\n\tEnter
the Choice ");
scanf("%d",&ch);
switch(ch)
{
case
1:
fflush(stdin);
printf("\n\tEnter
Data : " );
scanf("%c",
&Data);
Tnode = Insert(Data, Tnode, &Num);
break;
case
2:
printf("\n\t
Tree Elements : ");
Disp(Tnode,
1);break;
case
3:
fflush(stdin);
printf("\n\tEnter Data to Delete : ");
scanf("%c",
&Data);
Tnode
= Del(Tnode, Data, &Num);
break;
case
4:
clrscr();
printf("\n\n\n\t\tQuiting....");
getch();
break;
}
}
}
No comments:
Post a Comment