Skip to content
This repository was archived by the owner on Sep 7, 2025. It is now read-only.

Commit d64a345

Browse files
vshalprashrabranhe
vshalprashr
authored and
abranhe
committed
Added AVL Tree Implementation
1 parent 6cc1ec2 commit d64a345

1 file changed

Lines changed: 175 additions & 0 deletions

File tree

‎data-structures/avl.cpp‎

Lines changed: 175 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,175 @@
1+
#include <iostream>
2+
#include <queue>
3+
using namespace std;
4+
5+
struct node
6+
{
7+
int data, height;
8+
node *left, *right;
9+
};
10+
11+
class avl
12+
{
13+
node* root=NULL;
14+
public:
15+
int height(node* root){
16+
if(root)
17+
return root->height;
18+
return 0;
19+
}
20+
node* rotateLeft(node* root){
21+
node* newroot = root->right;
22+
root->right = newroot->left;
23+
newroot->left = root;
24+
return newroot;
25+
}
26+
node* rotateRight(node* root){
27+
node* newroot = root->left;
28+
root->left = newroot->right;
29+
newroot->right = root;
30+
return newroot;
31+
}
32+
void insert(int x){
33+
this->root = insert(this->root, x);
34+
}
35+
node* insert(node* root, int x){
36+
if(root==NULL){
37+
root = new node;
38+
root->data = x;
39+
root->height = 1;
40+
root->left = NULL;
41+
root->right = NULL;
42+
return root;
43+
}
44+
if(x < root->data)
45+
root->left = insert(root->left,x);
46+
else if(x > root->data)
47+
root->right = insert(root->right,x);
48+
else
49+
return root;
50+
51+
int lh = height(root->left), rh = height(root->right);
52+
root->height = 1 + max(lh,rh);
53+
54+
lh -= rh;
55+
if(lh>1){
56+
if(x > root->left->data)
57+
root->left = rotateLeft(root->left);
58+
return rotateRight(root);
59+
}
60+
else if(lh<-1){
61+
if(x < root->right->data)
62+
root->right = rotateRight(root->right);
63+
return rotateLeft(root);
64+
}
65+
return root;
66+
}
67+
int minValue(node* root){
68+
while(root->left)
69+
root = root->left;
70+
return root->data;
71+
}
72+
void remove(int x){
73+
this->root = remove(this->root, x);
74+
}
75+
node* remove(node* root, int x){
76+
if(root == NULL)
77+
return NULL;
78+
if(x < root->data)
79+
root->left = remove(root->left, x);
80+
else if(x > root->data)
81+
root->right = remove(root->right, x);
82+
else{
83+
if(root->left == NULL && root->right == NULL){
84+
delete root;
85+
return NULL;
86+
}
87+
else if(root->right == NULL){
88+
node* temp = root;
89+
root = root->left;
90+
delete temp;
91+
return root;
92+
}
93+
else if(root->left == NULL){
94+
node* temp = root;
95+
root = root->right;
96+
delete temp;
97+
return root;
98+
}
99+
else{
100+
root->data = minValue(root->right);
101+
root->right = remove(root->right, root->data);
102+
}
103+
}
104+
105+
int lh = height(root->left), rh = height(root->right);
106+
root->height = 1 + max(lh,rh);
107+
108+
lh -= rh;
109+
if(lh>1){
110+
if(x > root->left->data)
111+
root->left = rotateLeft(root->left);
112+
return rotateRight(root);
113+
}
114+
else if(lh<-1){
115+
if(x < root->right->data)
116+
root->right = rotateRight(root->right);
117+
return rotateLeft(root);
118+
}
119+
return root;
120+
}
121+
void printLevel(){
122+
printLevel(this->root);
123+
}
124+
void printLevel(node* root){
125+
if(root){
126+
queue<node*> q;
127+
q.push(root);
128+
q.push(NULL);
129+
node* temp;
130+
while(!q.empty()){
131+
temp = q.front();
132+
q.pop();
133+
if(temp){
134+
cout << temp->data << " ";
135+
if(temp->left)
136+
q.push(temp->left);
137+
if(temp->right)
138+
q.push(temp->right);
139+
}
140+
else if(q.front()){
141+
cout << endl;
142+
q.push(NULL);
143+
}
144+
}
145+
}
146+
}
147+
void print(){
148+
print(this->root);
149+
}
150+
void print(node* root){
151+
if(root){
152+
print(root->left);
153+
cout << root->data << " ";
154+
print(root->right);
155+
}
156+
}
157+
};
158+
159+
int main()
160+
{
161+
avl a;
162+
a.insert(5);
163+
a.insert(6);
164+
a.insert(7);
165+
a.insert(8);
166+
a.insert(9);
167+
a.insert(4);
168+
a.printLevel();
169+
a.remove(7);
170+
a.remove(5);
171+
cout << endl;
172+
a.printLevel();
173+
174+
return 0;
175+
}

0 commit comments

Comments
 (0)