Skip to main content

AVL Tree

Dalam Binary Search Tree, tinggi maksimal suatu tree adalah N-1, dimana N adalah jumlah node. Dalam melakukan suatu operasi, misalnya insertion, deletion, dan seaching, kecepatan waktu merupakan hal yang cukup penting untuk diperhatikan. Setiap operasi pasti di harapkan dapat berjalan dengan cepat, sehingga semakin cepat suatu operasi maka semakin baik. Cepat atau tidaknya suatu operasi, bergantung pada ketinggian tree tersebut, semakin rendah tingginya, maka semakin cepat.

Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum.
untuk menetapkan tingginya, kita dapat menggunakan rumus berikut:

O(log n)

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.
Insertion
Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :
anggap T adalah node yang harus diseimbangkan kembali
– 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)
vio - 1
Ke-4 kasus tersebut dapat diselesaikan dengan melakukan rotasi
– Kasus 1 dan 2 dengan single rotation
– Kasus 3 dan 4 dengan double rotation
Contoh – Single Rotation: Jika suatu Tree diinsert node baru dengan nilai 12, maka akan terjadi ketidak seimbangan dan hal ini terletak pada posisi root
vio - 2
Contoh – Double Rotation : Jika terdapat sebuah tree yang kemudian dilakukan insert node 26. Maka akan terjadi ketidak seimbangan, sehingga terlihat dari bentuknya dapat diselesaikan dengan kasus 4.
vio - 3

Deletion
Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :
– Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
  • Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.
  • anggap T adalah node yang harus diseimbangkan kembali
    – 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 dalam menghapus node AVL Tree, terdapat AVL Tree yang kemudian di hapus node 60. Dengan gambaran sebagai berikut :
Yang akan menggantikan posisi node 60 adalah node 55. Akan terjadi ketidak seimbangan. Dengan tampilan sebagai berikut :
Maka akan dilakukan single rotation pada node 55 dengan kasus ketidak seimbangan pada kasus no. 2. Dengan tampilan setelah dilakukan single rotation sebagai berikut :
Ketika sudah dilakukan single rotation dan dilakukan kembali perbedaan tinggi / level maksimal 1 ternyata terdapat ketidak seimbangan yang terjadi. Sehingga diperlukan double rotation dengan kasus no. 4. Sehingga hasil dari rotasi yang dilakukan adalah sebagai berikut :
Contoh kodingan AVL Tree:
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
int data;
struct node *left,*right;
int ht;
}node;

node *root = NULL;

node *insert(node *,int);
node *del(node *,int);

void preorder(node *);
void inorder(node *);
int height(node *);

node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);

node * insert(node *temp, int x)
{
if(!temp)
{
temp = (node*)malloc(sizeof(node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;
}
else if(x > temp->data){
temp->right = insert(temp->right, x);
if(BF(temp) == -2)
if(x > temp->right->data)
temp = RR(temp);
else
temp = RL(temp);
}
else if(x < temp->data){
temp->left = insert(temp->left, x);
if(BF(temp) == 2)
if(x < temp->left->data)
temp = LL(temp);
else
temp = LR(temp);
}
temp->ht = height(temp);
return(temp);
}

node * del(node *temp, int x)
{
node *curr;
if(!temp)
{
return NULL;
}
else if(x > temp->data)
{
temp->right = del(temp->right, x);
if(BF(temp) == 2)
if(BF(temp->left) >= 0)
temp = LL(temp);
else
temp = LR(temp);
}
else
if(x < temp->data){
temp->left = del(temp->left, x);
if(BF(temp) == -2)
if(BF(temp->right) <= 0)
temp = RR(temp);
else
temp = RL(temp);
}
else{
if(temp->right != NULL)
{
curr = temp->right;
while(temp->left != NULL)
curr = curr->left;
temp->data = curr->data;
temp->right = del(temp->right, curr->data);
if(BF(temp) == 2)
if(BF(temp->left) >= 0)
temp = LL(temp);
else
temp = LR(temp);
}
else
return(temp->left);
}
temp->ht = height(temp);
return(temp);
}

int height(node *temp)
{
int lh, rh;
if(!temp)
return 0;
if(temp->left == NULL)
lh = 0;
else
lh  =1 + temp->left->ht;
if(temp->right == NULL)
rh = 0;
else
rh = 1 + temp->right->ht;
if(lh > rh)
return lh;
return rh;
}

node * rotateright(node *x)
{
node *y;
y = x->left;
x->left = y->right;
y->right = x;
x->ht = height(x);
y->ht = height(y);
return y;
}

node * rotateleft(node *x)
{
node *y;
y = x->right;
x->right = y->left;
y->left = x;
x->ht = height(x);
y->ht = height(y);
return y;
}

node * RR(node *temp)
{
temp = rotateleft(temp);
return temp;
}

node * LL(node *temp)
{
temp = rotateright(temp);
return temp;
}

node * LR(node *temp)
{
temp->left = rotateleft(temp->left);
temp = rotateright(temp);
return temp;
}

node * RL(node *temp)
{
temp->right = rotateright(temp->right);
temp = rotateleft(temp);
return temp;
}

int BF(node *temp)
{
int lh, rh;
if(!temp)
return 0;

if(temp->left == NULL)
lh = 0;
else
lh = 1 + temp->left->ht;

if(temp->right == NULL)
rh = 0;
else
rh = 1 + temp->right->ht;

return lh - rh;
}

void preorder(node *temp)
{
if(temp != NULL)
{
printf("%d(BF = %d)", temp->data, BF(temp));
preorder(temp->left);
preorder(temp->right);
}
}

void inorder(node *temp)
{
if(temp != NULL)
{
inorder(temp->left);
printf("%d(BF = %d)", temp->data, BF(temp));
inorder(temp->right);
}
}

int main(){
int x, element, input;
do
{
printf("============= AVL TREE =============\n");
printf("1. Create\n");
printf("2. Insert\n");
printf("3. Delete\n");
printf("4. Print\n");
printf("5. Close\n");
printf("====================================\n");
printf("Input: ");
scanf("%d", &input);
switch(input)
{
case 1: 
printf("\nNumber of elements: ");
scanf("%d", &element);
printf("Enter tree data: ");
root = NULL;
for(int i = 0; i < element; i++)
{
scanf("%d", &x);
root = insert(root, x);
}
break;
case 2: 
    printf("\nEnter a data: ");
scanf("%d", &x);
root = insert(root, x);
break;
case 3: 
printf("\nEnter a data: ");
scanf("%d", &x);
root = del(root, x);
break;
case 4: 
printf("\nPreorder sequence: \n");
preorder(root);
printf("\nInorder sequence:  \n");
inorder(root);
printf("\n");
break;
case 5: 
printf("Bye!");
}
}while(input != 5);
return 0;
}


Comments

Post a Comment

Popular posts from this blog

Hashing and Hash Tables, Trees & Binary Tree

1. Hashing Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Pada contoh sebelumnya, kita melakukan  hash  pada string menjadi bilangan. Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi: T["gozali"] = 3; printf("%d\n", T["gozali"]); Pada ilmu komputer, tabel seperti ini disebut sebagai  hash table . Struktur data ini erat kaitannya dengan konsep " key value ".  Key  adalah hal yang menjadi indeks, dan  value  adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan  key , dan IPK merupakan  value . Fungsi  Hashing Pada bagian sebelumnya, saya memberi contoh fungsi  hashing  sederhana. Sebenarnya fungsi  hashing  itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi  hashing  memiliki ...
Post a Comment
Read more

Final Review

Cathleen 2301867910 AVL Tree Dalam Binary Search Tree, tinggi maksimal suatu tree adalah N-1, dimana N adalah jumlah node. Dalam melakukan suatu operasi,  Dengan Balanced Binary Search Tree, kita dapat membuat suatu tree dengan tinggi minimum. untuk menetapkan tingginya, kita dapat menggunakan rumus berikut: O(log n) 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. Insertion Ada 4 kasus yang biasanya terjadi saat operasi  insert  dilakukan, yaitu : anggap T adalah node yang harus diseimbangkan kembali – 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 terd...
Post a Comment
Read more

Heaps and Tries

Heap Struktur data heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan sebagai complete tree. Ada korespondensi satu ke satu diantara elemen array dan node dari tree. tree itu benar-benar penuh pada semua tingkatan kecuali mungkin yang terendah, yang diisi dari kiri sampai titik tertentu. Semua node dari heap juga memenuhi hubungan bahwa nilai kunci pada setiap node pada kurangnya sama besar dengan  nilai pada anak-anaknya. Ini dapat dilihat sebagai sebuah pohon biner dengan dua kendala tambahan: Bentuk property : pohon itu adalah complete binary tree , yaitu semua tingkat tree, kecuali mungkin yang terakhir (paling dalam) sepenuhnya diisi, dan, jika tingkat terakhir tree itu tidak lengkap, maka node pada tingkat itu diisi dari kiri ke kanan. Sifat heap: setiap node lebih besar dari atau sama dengan masing-masing anak sesuai dengan perbandingan predikat yang ditetapkan untuk struktur data. Jenis heap : Min Heap: setiap elemen node adalah lebih k...
Post a Comment
Read more