AVL TREE

Jadi Untuk Kali ini saya belajar tentang AVL Tree, AVL sendiri adalah tree yang setiap di Insert selalu membalance dan kompleksitasnya adalah mendekati logN. Dengan syarat balance factor dari tree tidak lebih dari 1.


Ini adalah contoh code dari AVL Tree :

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

struct Node {
    int val;
    int height;
    struct Node *left, *right;
};

int max (int a, int b){
    return (a > b) ? a : b;
}

struct Node *createNode (int val){
    struct Node* temp = (Node*) malloc (sizeof (Node));
    temp->val = val;
    temp->right = temp->left = NULL;
    temp->height = 1;
   
    return temp;
}

struct Node *successor(struct Node *node){
    node = node->right;
    while (node->left) node = node->left;
    return node;
}

struct Node *predecessor (struct Node *node){
    node = node->left;
    while (node->right) node = node->right;
    return node;
}

int height (struct Node *node){
    if (!node) return 0;
    return (node->height);
}

struct Node *rotateRight(struct Node* node){
    struct Node *a = node->left;
    struct Node *b = a->right;
   
    node->left = b;
    a->right = node;
   
    node->height = max(height(node->left), height(node->right)) + 1;
    a->height = max(height(a->left), height(a->right)) + 1;
   
    return a;
}

struct Node *rotateLeft(struct Node* node){
    struct Node *a = node->right;
    struct Node *b = a->left;
   
    node->right = b;
    a->left = node;
   
    node->height = max(height(node->left), height(node->right)) + 1;
    a->height = max(height(a->left), height(a->right)) + 1;
   
    return a;
}

struct Node *insert(struct Node *node, int val){
    if (!node) return createNode(val);
   
    else if (val > node->val){
        node->right = insert(node->right, val);
       
    } else if (val < node->val){
        node->left = insert(node->left, val);
       
    } else return node;
   
    //Rebalancing
    node->height = 1 + max (height(node->left), height(node->right));
   
    int balance = height(node->left) - height(node->right);
   
   
    //Left Left        (kondisi simpang full kiri)
    if (balance > 1 && val < node->left->val){
        return rotateRight(node);
    }   
   
    //Left Right   
    if (balance > 1 && val > node->left->val){
        node->left = rotateLeft(node);
        return rotateRight(node);
    }   
   
    //Right Right    (kondisi simpang full kanan)
    if (balance < -1 && val > node->right->val){
        return rotateLeft(node);
    }   
   
    //Right Left   
    if (balance < -1 && val < node->right->val){
        node->right = rotateRight(node);
        return rotateLeft(node);
    }   
   
    return node;
}

int getBalance (struct Node *node){
    if (!node) return 0;
    return height(node->left) - height(node->right);
}

struct Node *deleteNode (struct Node* node, int val){
    if (!node) return node;
    else if (val > node->val){
        node->right = deleteNode(node->right, val);
    } else if (val < node->val){
        node->left = deleteNode(node->left, val);
    } else {
        if (!node->left || !node->right){
            //Skenario 1 & 2
            struct Node *temp = node->left != NULL ? node->left : node->right;
           
            if (!temp){
                temp = node;
                node = NULL;
            } else {
                *node = *temp;
            }
            free(temp);
        } else {
            //Skenario 3
            //Predecessor & Successor
           
            struct Node *temp = predecessor(node);
            node->val = temp->val;
            node->left = deleteNode(node->left, node->val);
        }
    }
   
    //Rebalancing
    if (!node) return node;
   
    node->height = max(height(node->left), height(node->right)) + 1;
    int balance = height(node->left) - height(node->right);
       
    if (balance > 1 && getBalance(node->left) >= 0){
        return rotateRight(node);
    }   
   
    //Left Right   
    if (balance > 1 && getBalance(node->left) < 0){
        node->left = rotateLeft(node);
        return rotateRight(node);
    }   
   
    //Right Right    (kondisi simpang full kanan)
    if (balance < -1 && getBalance(node->right) <= 0){
        return rotateLeft(node);
    }   
   
    //Right Left   
    if (balance < -1 && getBalance(node->left) > 0){
        node->right = rotateRight(node);
        return rotateLeft(node);
    }   
    return node;
}

void inOrder (struct Node *node){
    if (!node) return;
    inOrder(node->left);
    printf ("%d\n", node->val);
    inOrder(node->right);
}

void preOrder (struct Node *node){
    if (!node) return;
    printf ("%d\n", node->val);
    preOrder(node->left);
    preOrder(node->right);
}

void postOrder (struct Node *node){
    if (!node) return;
    postOrder(node->left);
    postOrder(node->right);
    printf ("%d\n", node->val);
}

int main (){
    struct Node *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 60);
   
    inOrder(root);
   
}