Linked List

AVL Tree

-       AVL tree(atau ada yang menyebutnya balanced binary search tree) adalah perkembangan dari BST yang treenya akan diseimbangkan secara otomatis. Cara kerja dari AVL trree adalah selisih left subtree dan right subtree tidak boleh lebih dari 1. Jika lebih dari 1, maka akan terjadi penyeimbangan data dalam AVL tree.

-       Tujuan dari AVL tree adalah untuk menyeimbangkan Tree agar tidak ada cabang tree yang panjang sendiri sehingga memudahkan kita dalam pencarian

Macam macam operasi dalam AVL tree :

-       Single Rotation

Terbagi menjadi 2 :

1.     Right-Right Rotation

2.     Left-Left Rotation

-       Double Rotation :

Terbagi menjadi 2:

1.     Right-Left Rotation

2.     Leltf-Right Rotation

Berikut adalah contoh penggunaan AVL tree dalam C

struct Node{

            int key;

            Node right, left;

            int height;

};

Node newNode(int key){

            Node node = (Node) malloc(sizeof(Node));

            node->key = key;

            node->left = NULL;

            node->right = NULL;

            node->height = 1;

}

int findMax(int a, int b){

            return (a>b) ? a : b;

}

int height(Node current){

            if(current == NULL){

                        return 0;

            }

            return current->height;

}

int getBalance(struct Node* curr){

            if(curr == NULL){



                        return 0;

            }

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

}

Node* rightRotate(struct Node x){

            Node y = x->left;

            Node* subChild = y->right;



            y->right = x;

            x->left = subChild;

            //return new root



            x->height = findMax(height(x->left),height(x->right))+1;

            y->height = findMax(height(x->left),height(x->right))+1;

            return y;

}

Node* leftRotate(struct Node x){

            Node y = x->right;

            Node* subChild = y->left;



            y->left = x;

            x->right = subChild;



            x->height = findMax(height(x->left),height(x->right))+1;

            y->height = findMax(height(x->left),height(x->right))+1;

            //return new root

            return y;

}

Node insert(Node root, int key){

            if(root == NULL){

                        return newNode(key);

            }else if(root->key>key){

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

            }else if(root->key<key){

                        root->right = insert(root->right, key);

            }else{

                        return root;

            }



            root->height = findMax(height(root->left), height(root->right))+1;



            int balance = getBalance(root);



            //left2 case

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

                        //right rotate

                        return rightRotate(root);

            }

            //right2 case

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

                        //left rotate

                        return leftRotate(root);

            }

            //left right case

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

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

                        //right rotate

                        return rightRotate(root);

            }

            //right left case

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

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

                        //left rotate

                        return leftRotate(root);

            }

            return root;

}

void printData(Node* root){

            if(root!=NULL){

                        printData(root->left);

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

                        printData(root->right);

            }

}

int main(){

            Node *root = NULL;

            root = insert(root, 15);

//          root = insert(root, 10);

            root = insert(root, 18);

            root = insert(root, 5);

            root = insert(root, 3);

            root = insert(root, 6);

            root = insert(root, 7);

            root = insert(root, 21);

            root = insert(root, 30);

            root = insert(root, 31);

            root = insert(root, 32);

            root = insert(root, 33);

            printData(root);



            return 0;

}

Comments