AVL TREE
NAME : SANIDHYA
SHARMA
REGISTRATION NUMBER:
25BYB1114
PROF. DR MALATHI
Code:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b) {
return (a > b) ? a : b;
}
int height(struct Node *n) {
if (n == NULL)
return 0;
return n->height;
}
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
node->height = 1;
return node;
}
int getBalance(struct Node *n) {
if (n == NULL)
return 0;
return height(n->left) - height(n->right);
}
struct Node* rightRotate(struct Node *y) {
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
struct Node* leftRotate(struct Node *x) {
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
struct Node* insert(struct Node* node, int key) {
if (node == NULL)
return newNode(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
// LL
if (balance > 1 && key < node->left->data)
return rightRotate(node);
// RR
if (balance < -1 && key > node->right->data)
return leftRotate(node);
// LR
if (balance > 1 && key > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// RL
if (balance < -1 && key < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
struct Node * minValueNode(struct Node* node) {
struct Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
struct Node* deleteNode(struct Node* root, int key) {
if (root == NULL)
return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
if ((root->left == NULL) || (root->right == NULL)) {
struct Node *temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
}
else
*root = *temp;
free(temp);
}
else {
struct Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
// LL
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// LR
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// RR
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// RL
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
struct Node* search(struct Node* root, int key) {
if (root == NULL || root->data == key)
return root;
if (key < root->data)
return search(root->left, key);
return search(root->right, key);
}
void inorder(struct Node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void preorder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct Node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}
int main() {
struct Node *root = NULL;
int choice, val;
while (1) {
printf("\[Link] [Link] [Link] [Link] [Link] [Link]
[Link]\n");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter value: ");
scanf("%d", &val);
root = insert(root, val);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d", &val);
root = deleteNode(root, val);
break;
case 3:
printf("Enter value to search: ");
scanf("%d", &val);
if (search(root, val))
printf("Found\n");
else
printf("Not Found\n");
break;
case 4:
printf("Inorder: ");
inorder(root);
printf("\n");
break;
case 5:
printf("Preorder: ");
preorder(root);
printf("\n");
break;
case 6:
printf("Postorder: ");
postorder(root);
printf("\n");
break;
case 7:
exit(0);
default:
printf("Invalid choice\n");
}
}
}
Sample input that were given to the
code of line was:
1 10
1 20
1 30
1 40
1 50
1 25
4
5
6
3 25
2 40
4
7
Sample output :
Inorder: 10 20 25 30 40 50
Preorder: 30 20 10 25 40 50
Postorder: 10 25 20 50 40 30
Found
Inorder: 10 20 25 30 50
REPORT TITLE 3
SAN
THANK YOU MAM
FOR PROVIDING
ALL YOUR
KNOWLEDGE
- SANIDHYA SHARMA ,