AVL TREE

Rabu, 6 Mei 2020

Kevin
2301880231

AVL TREE

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

A. Insert dalam AVL Tree

Untuk menjaga agar tree tetap seimbang, setelah penyisipan sebuah node, dilakukan pemeriksaan dari node baru → root. Node pertama yang memiliki |balance factor| > 1 diseimbangkan. Proses penyeimbangan tersebut dapat  dilakukan dengan dua metode yaitu : Single rotation dan Double rotation. 

1. Single Rotation

Single Rotation terjadi bila kondisi tree dinsert dan terjadi ketidakseimbangan balance factor > 1 dan node yang mengalami ketidakseimbangan tersebut searah atau disebut Left Left (LL) atau sebaliknya yaitu Right Right (RR).

2. Double Rotation

Sebaliknya, Double Rotation terjadi bila tree diinsert dan jika terjadi ketidakseimbangan balance factor > 1 dan node yang mengalami ketidakseimbangan tersebut berlawanan arah yaitu Left Right (LR) atau Right Left (RL).

Berikut contoh gambar dari insert AVL Tree :

B. Delete node dalam AVL Tree

Terdapat 2 kasus yang biasanya terjadi dalam operasi delete yaitu kurang lebih mirip dengan 

Binary Search Tree (BST) akan tetapi bedanya harus menyeimbangkan balance factor, yaitu :

 - Jika node yang ingin dihapus terletak pada posisi leaf atau node yang tidak memiliki anak kiri maupun kanan, maka dapat langsung dihapus.

- Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

            - Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
            - Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
            - Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

           Berikut contoh dari delete AVL Tree :

Berikut contoh dari coding-an AVL Tree Insert dan Delete :
#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
int height;
struct node *left;
struct node *right;
};

int max(int a, int b){
if(a < b) return b;
else return a;
}

int getHeight(struct node *root){
if(root == NULL) return 0;
return root->height;
}

// Get Balance Factor
int getBF(struct node *root){
if(root == NULL) return 0;
return getHeight(root->left) - getHeight(root->right);
}

struct node *rightRotate(struct node *y){
struct node *x = y->left;
struct node *B = x->right;

//rotate
x->right = y;
y->left = B;

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

return x;
}

struct node *leftRotate(struct node *x){
struct node *y = x->right;
struct node *B = y->left;

//rotate
y->left = x;
x->right = B;

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

return y;
}


// di subtree kanan , ambil nilai terkecil
struct node *successor(struct node *root){
struct node *cur = root->right;
while(cur->left != NULL){
cur = cur->left;
}
return cur;
}

// di subtree kiri, ambil nilai terbesar
struct node *predecessor(struct node *root){
struct node *cur = root->left;
while(cur->right != NULL){
cur = cur->right;
}
return cur;
}

struct node *newNode(int x){
struct node *currNewNode =
(struct node*)malloc(sizeof(struct node));

currNewNode->key = x;
currNewNode->height = 1;
currNewNode->left = NULL;
currNewNode->right = NULL;

return currNewNode;
}

struct node *insert(struct node *root, int value){
if(root == NULL) return newNode(value);
else if(value < root->key){
root->left = insert(root->left, value);
}else{
root->right = insert(root->right, value);
}

// calculate balance factor for each node
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int bfactor = getBF(root);

// if violation , then rotate
if(bfactor > 1 && value < root->left->key){
return rightRotate(root); //LL bf = 2
}
if(bfactor <-1 && value > root->right->key){
return leftRotate(root); //RR bf = -2
}
if(bfactor > 1 && value > root->left->key){
root->left = leftRotate(root->left);
return rightRotate(root); //LR bf = 2
}
if(bfactor < -1 && value < root->right->key){
root->right = rightRotate(root->right);
return leftRotate(root); //RL bf = -2
}
return root;
}

struct node *deleteValue(struct node *root, int value){
if(root == NULL) return NULL; // tidak ketemu...
if(value < root->key){
root->left = deleteValue(root->left, value);
}else if(value > root->key){
root->right = deleteValue(root->right, value);
}else{

// ketemu mari kita mulai delete...

// case 1 : tidak punya anak
// case 2 : hanya punya anak kiri
// case 3 : hanya punya anak kanan
if((root->left == NULL) || (root->right == NULL)){

struct node *temp = NULL;
if(root->left != NULL) temp = root->left;
else temp = root->right;

if(temp == NULL){
// pasti tidak punya anak
// ini adalah case 1
temp = root;
root = NULL;
}else{
// ini adalah case 2 dan case 3
*root = *temp;
}
free(temp);

}else{
// ini adalah case 4
// ada 2 anak, maka kita ambil suksesor / predesesor
// terserah

struct node *temp = predecessor(root);
root->key = temp->key;

// delete
root->left = deleteValue(root->left, temp->key);
}
}

if(root == NULL) return root;

// kita perlu fix height dlsbnya
root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int bfactor = getBF(root);

if(bfactor > 1 && getBF(root->left) >= 0){
return rightRotate(root);
}
if(bfactor > 1 && getBF(root->left) < 0){
root->left = leftRotate(root->left);
return rightRotate(root);
}
if(bfactor < -1 && getBF(root->right) <= 0){
return leftRotate(root);
}
if(bfactor < -1 && getBF(root->right) > 0){
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}


void printAll(struct node *root){
if(root == NULL) return;
printAll(root->left);
printf(" %d ", root->key);
printAll(root->right);
}

struct node *freeAll(struct node *root){
if(root == NULL) return NULL;
root->left = freeAll(root->left);
root->right = freeAll(root->right);
free(root);
return NULL;
}

int main(){
struct node *root = NULL;

root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 15);
root = insert(root, 20);
root = insert(root, 17);

printAll(root);
puts("");

root = deleteValue(root, 10);

printAll(root);
puts("");

root = deleteValue(root, 15);

printAll(root);
puts("");

root = freeAll(root);

return 0;

}