AVL ALGORITHM
#include<stdio.h>
#include<stdlib.h>
struct node{
int key,length;
struct node* left;
struct node* right;
};
int getheight(struct node* n){
if(n==NULL){
return 0;
return n->length;
struct node* create(int data){
struct node* newnode=(struct node*)malloc(sizeof(struct node));
newnode->key=data;
newnode->length=1;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
int Max(int a,int b){
return (a>b)?a:b;
}
int getbalance(struct node* root){
if(root==NULL){
return 0;
return getheight(root->left)-getheight(root->right);
struct node * right(struct node* y){
struct node* x=y->left;
struct node* t2=x->right;
x->right=y;
y->left=t2;
y->length=Max(getheight(y->left),getheight(y->right));
x->length=Max(getheight(x->left),getheight(x->right));
return x;
struct node * left(struct node* x){
struct node* y=x->right;
struct node* t2=y->left;
x->left=y;
y->right=t2;
y->length=Max(getheight(y->left),getheight(y->right))+1;
x->length=Max(getheight(x->left),getheight(x->right))+1;
return y;
struct node* insert(struct node* node,int key){
if(node==NULL){
return create(key);
}
if(key<node->key){
node->left=insert(node->left,key);
else if(key>node->key){
node->right=insert(node->right,key);
node->length=1+max(getheight(node->left),getheight(node->right));
int balance=getbalance(node);
if(balance>1 && key<node->left->key){
return right(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return left(node);
// Left Right Case
if (balance > 1 && key > node->left->key) {
node->left = left(node->left);
return right(node);
// Right Left Case
if (balance < -1 && key < node->right->key) {
node->right = right(node->right);
return left(node);
}
return node;
void inorder(struct node* root){
if(root==NULL){
return;
inorder(root->left);
printf("%d",root->key);
inorder(root->right);
int main(){
struct node* root=NULL;
root=insert(root,1);
root=insert(root,3);
root=insert(root,6);
root=insert(root,2);
root=insert(root,9);
inorder(root);