-
Notifications
You must be signed in to change notification settings - Fork 0
/
avl_tree.c
134 lines (133 loc) · 2.88 KB
/
avl_tree.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//
// Created by antoa on 25-02-2024.
//
#include<stdio.h>
#include<conio.h>
#include <malloc.h>
struct treenode;
typedef struct treenode *position,*avltree,ptrtonode;
struct treenode
{
int element;
avltree left;
avltree right;
int height;
};
int height(position p)
{
if(p!=NULL)
return p->height;
else
return 0;
}
int max(int h1,int h2)
{
if(h1>h2)
return h1;
else
return h2;
}
position singlelerightrotation(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),height(k1->right))+1;
return k1;
}
position singlerileftrotation(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->left),height(k2->right))+1;
return k2;
}
position doublelerightrotation(position k3)
{
k3->left=singlerileftrotation(k3->left);
return singlerileftrotation(k3);
}
position doublerileftrotation(position k3)
{
k3->right=singlerileftrotation(k3->right);
return singlerileftrotation(k3);
}
avltree insert(int x,avltree t)
{
if(t== NULL)
{
t=(ptrtonode *)malloc(sizeof(struct treenode));
if(t== NULL)
{
printf("\nOut of space");
}
else
{
t->element=x;
t->left=NULL;
t->right=NULL;
t->height=0;
}
}
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=singlelerightrotation(t);
else
t=doublelerightrotation(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=singlerileftrotation(t);
else
t=doublerileftrotation(t);
}
t->height=max(height(t->left),height(t->right))+1;
return t;
}
void display(avltree root)
{
if(root!=NULL)
{
display(root->left);
if(root->element== NULL)
{
printf("0");
}
else
{
printf("\n%d",root->element);
}
display(root->right);
}
}
void main()
{
int item;
char ch;
avltree t;
position p;
t=NULL;
do
{
printf("\nEnter the item to be inserted:");
scanf("%d",&item);
t=insert(item,t);
printf("\nThe item is inserted");
printf("\nDo u want to insert the item again:(y for YES/n for NO)");
ch=getche();
}while(ch=='y');
printf("\nThe AVL Tree is ..... ");
display(t);
getch();
}