Laborator_AVL_PAA

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

// Structura pentru un nod din arbore
typedef struct Node {
    int key;
    struct Node *left;
    struct Node *right;
    int height;
} Node;

// Functie pentru a determina inaltimea unui nod
int height(Node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// Functie pentru a calcula maximul dintre doua numere
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Functie pentru alocarea unui nou nod cu cheia data
Node* newNode(int key) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;  // Noul nod este initial adaugat la frunza
    return(node);
}

// Rotatie la dreapta
Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    // Executa rotatia
    x->right = y;
    y->left = T2;

    // Actualizeaza inaltimile
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Returneaza noua radacina
    return x;
}

// Rotatie la stanga
Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    // Executa rotatia
    y->left = x;
    x->right = T2;

    // Actualizeaza inaltimile
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Returneaza noua radacina
    return y;
}

// Obtine factorul de echilibru al nodului N
int getBalance(Node *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Functie recursiva pentru inserarea unei chei in subarborele cu radacina
// la nodul dat si returneaza noua radacina a subarborelui
Node* insert(Node* node, int key) {
    /* 1. Efectuam inserarea normala a unui BST */
    if (node == NULL)
        return(newNode(key));

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else // Chei egale nu sunt permise in arborele AVL
        return node;

    /* 2. Actualizam inaltimea acestui nod stramos */
    node->height = 1 + max(height(node->left), height(node->right));

    /* 3. Obtinem factorul de echilibru al acestui nod stramos
       pentru a verifica daca acest nod a devenit dezechilibrat */
    int balance = getBalance(node);

    // Daca acest nod devine dezechilibrat, atunci exista 4 cazuri

    // Cazul stanga-stanga
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // Cazul dreapta-dreapta
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // Cazul stanga-dreapta
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Cazul dreapta-stanga
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    /* returneaza pointer-ul nodului (nechimbat) */
    return node;
}

// Functia utilitara pentru a gasi nodul cu cea mai mica valoare
// care este mai mare decat nodul dat
Node * minValueNode(Node* node) {
    Node* current = node;

    /* gaseste frunza cea mai din stanga */
    while (current->left != NULL)
        current = current->left;

    return current;
}

// Functie recursiva pentru a sterge un nod cu o cheie data
// din subarborele cu radacina data si returneaza radacina
Node* deleteNode(Node* root, int key) {
    // PASUL 1: EFECTUARE STERGERE NORMALA BST

    if (root == NULL)
        return root;

    // Daca cheia de sters este mai mica decat cheia radacinii,
    // atunci se afla in subarborele stang
    if ( key < root->key )
        root->left = deleteNode(root->left, key);

    // Daca cheia de sters este mai mare decat cheia radacinii,
    // atunci se afla in subarborele drept
    else if( key > root->key )
        root->right = deleteNode(root->right, key);

    // Daca cheia este aceeasi cu cheia radacinii, atunci acesta
    // este nodul care trebuie sters
    else {
        // nod cu unul sau fara copil
        if( (root->left == NULL) || (root->right == NULL) ) {
            Node *temp = root->left ? root->left : root->right;

            // Fara copil
            if (temp == NULL) {
                temp = root;
                root = NULL;
            }
            else // Un copil
             *root = *temp; // Copierea continutului copilului

            free(temp);
        }
        else {
            // Nod cu doi copii: Ia succesorul inordine (cel mai mic
            // din subarborele drept)
            Node* temp = minValueNode(root->right);

            // Copiaza succesorul inordine in acest nod
            root->key = temp->key;

            // Sterge succesorul inordine
            root->right = deleteNode(root->right, temp->key);
        }
    }

    // Daca arborele avea doar un nod atunci returneaza
    if (root == NULL)
      return root;

    // PASUL 2: ACTUALIZEAZA INALTIMEA NODULUI CURENT
    root->height = 1 + max(height(root->left), height(root->right));

    // PASUL 3: VERIFICA ECHILIBRUL NODULUI CURENT
    int balance = getBalance(root);

    // Daca acest nod devine dezechilibrat, atunci exista 4 cazuri

    // Cazul stanga-stanga
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    // Cazul stanga-dreapta
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // Cazul dreapta-dreapta
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    // Cazul dreapta-stanga
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// Functie de afisare a arborelui in inordine
void inOrder(Node *root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->key);
        inOrder(root->right);
    }
}

int main() {
  Node *root = NULL;

  // Exemplu de inserari
  root = insert(root, 10);
  root = insert(root, 20);
  root = insert(root, 30);
  root = insert(root, 40);
  root = insert(root, 50);
  root = insert(root, 25);

  printf("Inorder traversal of the constructed AVL tree is \n");
  inOrder(root);

  root = deleteNode(root, 20);

  printf("\nInorder traversal after deletion of 20 \n");
  inOrder(root);

  return 0;
}