Modul 3 [AVL Tree] - lab-kcks/Modul-STRUKDAT GitHub Wiki
AVL Tree merupakan salah satu jenis self-balancing BST yang menyeimbangkan heightnya dengan cara melakukan rotasi pada saat terdapat selisih height dari node child kiri dan node child kanan lebih dari 1.
AVL Tree memiliki terminologi yang sama seperti BST. Namun terdapat tambahan yaitu Balance Factor.
Balance Factor merupakan hasil dari pengurangan height node child kiri dikurang height node child kanan. Dapat juga ditulis sebagai berikut :
Sumber Gambar : https://static.javatpoint.com/ds/images/avl-tree.png
Dengan begitu, nilai valid Balance Factor hanya berikut ini
Ketika Balance Factor lebih kecil dari -1 (BF < -1) atau lebih besar dari 1 (BF > 1), maka akan dilakukan rotasi. Terdapat 4 rotasi pada AVL Tree yaitu :
- Balance Factor < -1
- Height Subtree Kiri < Height Subtree Kanan (Case Right Skewed) → Rotasi Kiri (LL)
- Height Subtree Kiri > Height Subtree Kanan (Case Right ZigZag) → Rotasi Kanan diikuti Rotasi Kiri (LR)
- Balance Factor > 1
- Height Subtree Kiri > Height Subtree Kanan (Case Left Skewed) → Rotasi Kanan (RR)
- Height Subtree Kiri < Height Subtree Kanan (Case Left ZigZag) → Rotasi Kiri diikuti Rotasi Kanan (LR)
Rotasi Kiri terjadi ketika Balance Factor < -1 dan Height Subtree Kiri < Height Subtree Kanan.
Pada rotasi kiri caranya adalah right child dari pivotNode menjadi parent baru. Kemudian left child dari newParent akan menjadi right child pivotNode. Kemudian pivotNode akan menjadi left child dari parent baru. Kemudian lakukan update height untuk pivotNode dan newParrent node.
Ilustrasi sederhana dari Rotasi kiri adalah sebagai berikut
Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/LL%20Rotation.png
AVLNode* _leftRotate(AVLNode* pivotNode) {
AVLNode* newParrent=pivotNode->right;
pivotNode->right=newParrent->left;
newParrent->left=pivotNode;
pivotNode->height=_max(_getHeight(pivotNode->left), _getHeight(pivotNode->right))+1;
newParrent->height=_max(_getHeight(newParrent->left), _getHeight(newParrent->right))+1;
return newParrent;
}
Detailnya adalah sebagai berikut :
Sumber gambar : https://github.com/AlproITS/StrukturData/wiki/img/m3-3.png
Rotasi Kanan terjadi ketika Balance Factor > 1 dan Height Subtree Kiri > Height Subtree Kanan.
Pada rotasi kanan caranya adalah left child dari pivotNode menjadi parent baru. Kemudian right child dari newParent akan menjadi left child pivotNode. Kemudian pivotNode akan menjadi right child dari parent baru. Kemudian lakukan update height untuk pivotNode dan newParrent node.
Ilustrasi sederhana dari Rotasi kanan adalah sebagai berikut
Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/RR%20Rotation.png
Detailnya adalah sebagai berikut :
AVLNode* _rightRotate(AVLNode* pivotNode){
AVLNode* newParrent=pivotNode->left;
pivotNode->left=newParrent->right;
newParrent->right=pivotNode;
pivotNode->height=_max(_getHeight(pivotNode->left),
_getHeight(pivotNode->right))+1;
newParrent->height=_max(_getHeight(newParrent->left),
_getHeight(newParrent->right))+1;
return newParrent;
}
Sumber Gambar : https://github.com/AlproITS/StrukturData/wiki/img/m3-2.png
Rotasi ini merupakan gabungan antara rotasi kiri dan rotasi kanan.
Rotasi LR terjadi ketika Balance Factor > 1 dan Height Subtree Kiri < Height Subtree Kanan.
Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/LR%20Rotation.png
Detailnya adalah sebagai berikut :
AVLNode* _leftRightCaseRotate(AVLNode* node){
node->left=_leftRotate(node->left);
return _rightRotate(node);
}
Sumber Gambar : https://github.com/AlproITS/StrukturData/wiki/img/m3-5.png
Rotasi ini merupakan gabungan antara rotasi kanan dan rotasi kiri.
Rotasi RL terjadi ketika Balance Factor < -1 dan Height Subtree Kiri > Height Subtree Kanan.
Sumber Gambar : http://www.btechsmartclass.com/data_structures/ds_images/RL%20Rotation.png
Detailnya adalah sebagai berikut :
AVLNode* _rightLeftCaseRotate(AVLNode* node){
node->right=_rightRotate(node->right);
return _leftRotate(node);
}
Sumber Gambar : https://github.com/AlproITS/StrukturData/wiki/img/m3-4.png
Insertion pada AVL sama dengan insertion pada BST. Namun pada AVL, setiap kali melakukan insertion, maka perlu dilakukan update height dan mengecek apakah perlu dilakukan rotasi atau tidak.
void avl_insert(AVL *avl,int value){
if(!avl_find(avl,value)){
avl->_root = _insert_AVL(avl,avl->_root,value);
avl->_size++;
}
}
AVLNode* _insert_AVL(AVL *avl,AVLNode* node,int value){
if(node==NULL)
return _avl_createNode(value);
if(value < node->data)
node->left = _insert_AVL(avl,node->left,value);
else if(value > node->data)
node->right = _insert_AVL(avl,node->right,value);
node->height= 1 + _max(_getHeight(node->left),_getHeight(node->right));
int balanceFactor=_getBalanceFactor(node);
if(balanceFactor > 1 && value < node->left->data)
return _leftCaseRotate(node);
if(balanceFactor > 1 && value > node->left->data)
return _leftRightCaseRotate(node);
if(balanceFactor < -1 && value > node->right->data)
return _rightCaseRotate(node);
if(balanceFactor < -1 && value < node->right->data)
return _rightLeftCaseRotate(node);
return node;
}
Sama seperti Insertion, deleteion pada AVL juga sama seperti deletion pada BST. Namun pada AVL kita perlu melakukan update height dan mengecek apakah perlu dilakukan rotasi atau tidak.
void avl_remove(AVL *avl,int value) {
if(avl_find(avl,value)) {
avl->_root=_remove_AVL(avl->_root,value);
avl->_size--;
}
}
AVLNode* _findMinNode(AVLNode *node) {
AVLNode *currNode = node;
while (currNode && currNode->left != NULL)
currNode = currNode->left;
return currNode;
}
AVLNode* _remove_AVL(AVLNode* node,int value){
if(node==NULL)
return node;
if(value > node->data)
node->right=_remove_AVL(node->right,value);
else if(value < node->data)
node->left=_remove_AVL(node->left,value);
else{
AVLNode *temp;
if((node->left==NULL)||(node->right==NULL)){
temp=NULL;
if(node->left==NULL) temp=node->right;
else if(node->right==NULL) temp=node->left;
if(temp==NULL){
temp=node;
node=NULL;
}
else
*node=*temp;
free(temp);
}
else{
temp = _findMinNode(node->right);
node->data=temp->data;
node->right=_remove_AVL(node->right,temp->data);
}
}
if(node==NULL) return node;
node->height=_max(_getHeight(node->left),_getHeight(node->right))+1;
int balanceFactor= _getBalanceFactor(node);
if(balanceFactor>1 && _getBalanceFactor(node->left)>=0)
return _leftCaseRotate(node);
if(balanceFactor>1 && _getBalanceFactor(node->left)<0)
return _leftRightCaseRotate(node);
if(balanceFactor<-1 && _getBalanceFactor(node->right)<=0)
return _rightCaseRotate(node);
if(balanceFactor<-1 && _getBalanceFactor(node->right)>0)
return _rightLeftCaseRotate(node);
return node;
}