Avl Tree (Binary Search Tree)

AVL Tree of Binary Search Tree

         Avl Tree adalah turunan dari Binary Search Tree yang dimana memang menggunakan prinsip dasar dari Binary Search Tree tapi dengan penambahan kriteria lainnya. Kriteria nya adalah dengan perbandingan height subtree kiri dan kanan tidak bisa lebih dari satu node. Avl Tree akan dianggap benar jika Balance dari height subtree kiri dan kanan seimbang (perbedaan node nya adalah lebih kecil sama dengan dari 1). Jika terjadi ketidakseimbangan dalam AVL tree tersebut maka diperlukan penyeimbangan dengan penarikan seperti katrol. 

      Kegunaan penggunaan AVL tree yaitu untuk menghindari kelinieran dari Binary Search Tree dimana pada kasus Skewed-Binary Search Tree dimana complexity nya menjadi O(n). Maka dengan AVL tree akan mengurusi permasalahan tersebut dimana height antara subtree kiri dan kanan akan menjadi seimbang sehingga complexity nya akan bertetap pada O(logn).

     Methode-Methode pada AVL Tree secara umum hampir sama seperti Binary Search Tree yaitu :

• Insertion 
• Deletion
• Seaching

Dimana pada setiap methodenya akan terjadi modifikasi codingan dari Binary Search Tree.

Insertion Methode :

Pada insertion AVL Tree sebenarnya hampir sama dengan BST tetapi perbedaanya dengan adanya tambahan untuk melakukan balancing height.

Dalam Balancing Height ada 4 kasus yang mungkin terjadi :

1. Left-Left Case -> memerlukan Right Rotation
2. Right-Right Case -> memerlukan Left Rotation 
3. Left-Right Case (Untuk kasus data belok) memerlukan leftRotation dulu pada node->left kemudian pada node dilakukan right rotation
4. Right-Left Case (Untuk kasus data yang belok) memerlukan RightRotation pada node->right kemudian pada node dilakukan Left  Rotation.

Cuplikan coding Insert :

struct node *insert(struct node *currNode, int value){

        if(currNode==NULL)return createNode(value);

if(value < currNode->value){

currNode->left = insert(currNode->left,value);

}else if(value>currNode->value){

currNode->right = insert(currNode->right,value);

}else{

return currNode;

}

//change the height of the ancestor

currNode->height = 1 + max(height(currNode->left),height(currNode->right));

int balance = getBalance(currNode);

//left left case

if(balance > 1 && value < currNode->left->value ){

return rightrotate(currNode);

}

//right right case

else if(balance <-1 && value > currNode->right->value){

return leftrotate(currNode);

}

//left right case

else if(balance >1 && value >currNode->left->value){

currNode->left = leftrotate(currNode->left);

return rightrotate(currNode);

}

//right left case

else if(balance <-1 && value < currNode->right->value){

currNode->right = rightrotate(currNode->right);

return leftrotate(currNode);

}

return currNode; }

Deletion Methode 

Untuk pada deletion proses delete tetap dilakukan sama seperti dengan BST dengan tambahan balancing seperti pada insertion dimana setelah melakukan penghapusan node diperlukan pengecekan kembali apakah Tree tersebut sudah balance atau belum dan jika belum akan dilakukan rotation sesuai case yang terjadi.

   if(currNode==NULL) return currNode;

if(value< currNode->value){

currNode->left = deleteValue(currNode->left,value);

}else if(value > currNode->value){

currNode->right = deleteValue(currNode->right,value);

}else{

if( currNode->left==NULL || currNode->right ==NULL){

struct node *temp = NULL;

if(currNode->left !=NULL) temp = currNode->left;

else temp = currNode->right;

//nggak ada anak

if(temp==NULL){

temp = currNode;

currNode= NULL;

}else{

//ada anak 1

*currNode = *temp;

}

free(temp);

}else {

//punya anak banyak

struct node *temp = predessesor(currNode);

currNode->value = temp->value;

//delete

currNode->left = deleteValue(currNode->left,temp->value);

}

}

if(currNode == NULL)return currNode;

currNode->height = max(height(currNode->left),height(currNode->right))+1;

int balance = getBalance(currNode);

if(balance > 1 && value < currNode->left->value ){

return rightrotate(currNode);

}

//right right case

else if(balance <-1 && value > currNode->right->value){

return leftrotate(currNode);

}

//left right case

else if(balance >1 && value >currNode->left->value){

currNode->left = leftrotate(currNode->left);

return rightrotate(currNode);

}

//right left case

else if(balance <-1 && value < currNode->right->value){

currNode->right = rightrotate(currNode->right);

return leftrotate(currNode);

}

return currNode;

Seperti yang dilihat diatas bisa dibilang hampir sama dengan BST pengcodingannya tetapi dengan tambahan balance nya.

Rotation :

Single Rotation dan Double Rotation sebenarnya sama hanya saja pembedanya dari berapa kali nya dilakukan rotation untuk mencapai balance BST.

Rotation dibagi menjadi dua yaitu Left Rotation :

struct node *leftrotate(struct node *x){

struct node *y = x->right;

struct node *temp = y->left;

y->left = x;

x->right = temp;

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

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

return y;

}

Dan untuk Right Rotation :

struct node *rightrotate(struct node *x){

struct node *y = x->left;

struct node *temp = y->right;

y->right = x;

x->left = temp;

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

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

return y;

}