Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement