DS – AVL Program – Ameerpet Technologies

#include<stdio.h>
#include<stdlib.h>

struct Node
{
            int data;
            struct Node *left;
            struct Node *right;
            int ht;
};

struct Node *root = NULL;

struct Node* insert(struct Node*, int);
int height(struct Node*);
int balFact(struct Node*);
struct Node* rotateright(struct Node*);
struct Node* rotateleft(struct Node*);
struct Node* RR(struct Node*);
struct Node* LL(struct Node*);
struct Node* LR(struct Node*);
struct Node* RL(struct Node*);
void preorder(struct Node*);

int main()
{
            root = insert(root, 10);
            root = insert(root, 30);
            root = insert(root, 20);
            root = insert(root, 40);
            root = insert(root, 50);
            root = insert(root, 60);

            printf(“Pre Order of AVL : \n”);
            preorder(root);
            return 0;
}

struct Node* insert(struct Node *node, int x)
{
            if(node==NULL)
            {
                        node = (struct Node*)malloc(sizeof(struct Node));
                        node->data = x;
                        node->left = NULL;
                        node->right = NULL;
            }
            else
            {
                        if(x > node->data)
                        {
                                    node->right = insert(node->right, x);
                                    if(balFact(node) == -2)
                                    {
                                                if(x > node->right->data)
                                                {
                                                            node = RR(node);
                                                }
                                                else
                                                {
                                                            node = RL(node);
                                                }
                                    }
                        }
                        else if(x < node->data)
                        {
                                    node->left = insert(node->left, x);
                                    if(balFact(node) == 2)
                                    {
                                                if(x < node->left->data){
                                                            node = LL(node);
                                                }
                                                else
                                                {
                                                            node = LR(node);
                                                }
                                    }
                        }
            }
            node->ht = height(node);
            return node;
}

int height(struct Node* node)
{
            int lh, rh;
            if(node == NULL)
            {
                        return 0;
            }
            if(node->left == NULL)
            {
                        lh = 0;
            }
            else
            {
                        lh = 1 + node->left->ht;
            }
            if(node->right == NULL)
            {
                        rh = 0;
            }
            else
            {
                        rh = 1 + node->right->ht;
            }
            if(lh > rh)
            {
                        return lh;
            }
            else
            {
                        return rh;
            }
}
int balFact(struct Node *node)
{
            int lh, rh;
            if(node == NULL)
            {
                        return 0;
            }
            if(node->left == NULL)
            {
                        lh = 0;
            }
            else
            {
                        lh = 1+node->left->ht;
            }
            if(node->right == NULL)
            {
                        rh = 0;
            }
            else
            {
                        rh = 1+node->right->ht;
            }
            return lh-rh;
}

struct Node* rotateright(struct Node* x)
{
            struct Node *y;
            y = x->left;
            x->left = y->right;
            y->right = x ;
            x->ht = height(x);
            y->ht = height(y);
            return y;
}

struct Node* rotateleft(struct Node* x)
{
            struct Node *y;
            y = x->right;
            x->right = y->left;
            y->left = x ;
            x->ht = height(x);
            y->ht = height(y);
            return y;
}

struct Node* RR(struct Node* node)
{
            node = rotateleft(node);
            return node;
}

struct Node* LL(struct Node* node)
{
            node = rotateright(node);
            return node;
}

struct Node* LR(struct Node* node)
{
            node->left = rotateleft(node->left);
            node = rotateright(node);
            return node;
}

struct Node* RL(struct Node* node)
{
            node->right = rotateright(node->right);
            node = rotateleft(node);
            return node;
}

void preorder(struct Node* node)
{
            if(node != NULL)
            {
                        printf(“val : %d —– BF : %d\n” , node->data, balFact(node));
                        preorder(node->left);
                        preorder(node->right);
            }
}

Copyright © 2023 Ameerpet Technologies | Powered by Ameerpet Technologies