AVL Trees using C

An AVL tree is a self-adjusting double inquiry tree where the levels of the left and right subtrees of any hub vary by all things considered one. It is coined after its creators, Adelson-Velsky and Landis.


Oneself adjusting property of an AVL tree guarantees that the tree stays adjusted, which keeps up with productive hunt, inclusion, and erasure tasks with a period intricacy of O(log n), where n is


the quantity of hubs in the tree.


Here are the critical highlights and tasks of an AVL tree:


1. Parallel Hunt Tree Property:


·        An AVL tree follows the parallel hunt tree property: for each hub, the qualities in its left subtree are more modest, and the qualities in its right subtree are more prominent.


2. Balance Variable:


·        Every hub in an AVL tree stores an extra equilibrium factor, which is the distinction in level between its left and right subtrees.


·        The equilibrium component can be - 1, 0, or 1, demonstrating whether the tree is adjusted or requires rebalancing.


3. Turn Tasks:


·        To keep up with balance, AVL trees use turn tasks: left revolution and right pivot.


·        Left Pivot: Rebalances the tree by turning a hub and its right youngster to the left.


·        Right Pivot: Rebalances the tree by turning a hub and its passed on kid to one side.


·        These turns safeguard the paired hunt tree property and change the equilibrium variables of impacted hubs.


4. Inclusion:


·        While embedding another hub into an AVL tree, the paired hunt tree property is kept up with.


·        After inclusion, the equilibrium elements of hubs along the addition way are changed and rebalanced if important.


·        On the off chance that the equilibrium element of a hub becomes - 2 or +2, revolutions are performed to reestablish harmony.


5. Cancellation:


·        While erasing a hub from an AVL tree, the double inquiry tree property is kept up with.


·        After erasure, the equilibrium elements of hubs along the cancellation way are changed and rebalanced if essential.


·        In the event that the equilibrium element of a hub becomes - 2 or +2, turns are performed to reestablish harmony.


The AVL tree's self-adjusting property guarantees that the level of the tree is logarithmic, prompting productive hunt, inclusion, and cancellation tasks. In any case, keeping up with balance requires extra above as far as memory and computational intricacy contrasted with non-self-adjusting twofold hunt trees.


AVL trees are ordinarily utilized in situations where effective pursuit and recovery are significant, for example, data set ordering, in-memory information designs, and language libraries' executions of adjusted search trees.


In rundown, an AVL tree is a self-adjusting paired search tree that guarantees the levels of the left and right subtrees of any hub vary by all things considered one. It keeps up with balance through turn tasks and ensures effective inquiry, inclusion, and erasure tasks with a period intricacy of O(log n).

Top of Form

Program:-

# include <stdio.h>

#include <stdlib.h>

 

 

struct Node {

  int key;

  struct Node *left;

  struct Node *right;

  int height;

};

 

int max(int a, int b);

 

int height(struct Node *N) {

  if (N == NULL)

    return 0;

  return N->height;

}

 

int max(int a, int b) {

  return (a > b) ? a : b;

}

 

 

struct Node *newNode(int key) {

  struct Node *node = (struct Node *)

    malloc(sizeof(struct Node));

  node->key = key;

  node->left = NULL;

  node->right = NULL;

  node->height = 1;

  return (node);

}

 

 

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;

}

 

 

int getBalance(struct Node *N) {

  if (N == NULL)

    return 0;

  return height(N->left) - height(N->right);

}

 

 

struct Node *insertNode(struct Node *node, int key) {

 

  if (node == NULL)

    return (newNode(key));

 

  if (key < node->key)

    node->left = insertNode(node->left, key);

  else if (key > node->key)

    node->right = insertNode(node->right, key);

  else

    return node;

 

 

  node->height = 1 + max(height(node->left),

               height(node->right));

 

  int balance = getBalance(node);

  if (balance > 1 && key < node->left->key)

    return rightRotate(node);

 

  if (balance < -1 && key > node->right->key)

    return leftRotate(node);

 

  if (balance > 1 && key > node->left->key) {

    node->left = leftRotate(node->left);

    return rightRotate(node);

  }

 

  if (balance < -1 && key < node->right->key) {

    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->key)

    root->left = deleteNode(root->left, key);

 

  else if (key > root->key)

    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->key = temp->key;

 

      root->right = deleteNode(root->right, temp->key);

    }

  }

 

  if (root == NULL)

    return root;

 

 

  root->height = 1 + max(height(root->left),

               height(root->right));

 

  int balance = getBalance(root);

  if (balance > 1 && getBalance(root->left) >= 0)

    return rightRotate(root);

 

  if (balance > 1 && getBalance(root->left) < 0) {

    root->left = leftRotate(root->left);

    return rightRotate(root);

  }

  if (balance < -1 && getBalance(root->right) <= 0)

    return leftRotate(root);

  if (balance < -1 && getBalance(root->right) > 0) {

    root->right = rightRotate(root->right);

    return leftRotate(root);

  }

  return root;

}

void printPreOrder(struct Node *root) {

  if (root != NULL) {

    printf("%d ", root->key);

    printPreOrder(root->left);

    printPreOrder(root->right);

  }

}

int main() {

  struct Node *root = NULL;

while(1)

{

int choice,x,y;

printf("enter ur choice");

scanf("%d",&choice);

switch(choice)

{

case 1:printf("enter element");

            scanf("%d",&x);

            root=insertNode(root,x);

            break;

case 2:printf("enter elements to delete");

            scanf("%d",&y);

            root=deleteNode(root,y);

            break;

case 3:printPreOrder(root);

            break;

case 4:printf("exiting");

            exit(0);

}

}

  return 0;

}

Output:-