Senin, 27 April 2020

Rangkuman Pertemuan 10: AVL

Balanced Binary Search Tree

Pada rangkuman sebelumnya, kita telah membahas mengenai Binary Search Tree atau BST. Sebelumnya, juga sudah saya bahas bahwa BST memiliki kelemahan, yaitu suatu kondisi dimana ternyata Tree tersebut tidak benar-benar memiliki Time Complexity O(log n). Kondisi ini disebabkan oleh bentuk Skewed Tree atau tree hanya memanjang ke salah satu sisi saja, sehingga bentuknya mirip linear dan memiliki Time Complexity O(n). Solusi untuk masalah ini adalah Balanced Binary Search Tree yang dapat diimplementasikan melalui beberapa cara, salah satunya AVL yang akan kita bahas pada pertemuan kali ini.


AVL Tree

AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi / height maksimal 1 antara subtree kiri dan subtree kanan.

Berikut gambarannya :



Menentukan Height

Cara menentukan Height dan Balance Factor :

Height : 
  • Jika node (root) tidak memiliki subtree maka heightnya = 0
  • Leaf node heightnya = 1
  • Height internal node (node yang bukan root / leaf) = successor maximum height + 1
Balance Factor :
Selisih height antara anak kiri dan kanan. Apabila tidak memiliki anak, Balance Factor = 0.

AVL Tree : Insertion

Insertion pada AVL pada dasarnya sama dengan Binary Search Tree, dimana node baru akan mengisi leaf. Perbedaannya adalah pada AVL, setiap dilakukan insertion, dilakukan juga pengecekkan. Apabila terjadi AVL violation, dimana sebuah node memiliki balance factor > 1, maka dilakukan rebalancing. Pengecekkan umumnya dimulai dari node terdalam, sampai terakhirnya root. 

Umumnya pada proses balancing, terdapat 4 kasus.

Node yang menjadi poros balancing biasanya dikenal juga dengan node T.
    1. Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left - left)
    2. Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right - right)
    3. Kasus 3 : node terdalam terletak pada subtree kiri dari anak kanan (left - right)
    4. Kasus 4 : node terdalam terletak pada subtree kanan dari anak kiri (right - left)
Keempat kasus tersebut dapat diselesaikan melalui proses rotasi
  • Kasus 1 dan 2 dengan single rotation.
  • Kasus 3 dan 4 dengan double rotation.

Note : 
  • Node terdalam dikenal juga dengan node yang baru di insert. 
  • Left dan Right adalah proses rotasinya.

Single Rotation

Single Rotation dilakukan apabila node terdalam masih satu path yang lurus dengan node yang melakukan AVL violation, sehingga bila ditarik garis, pathnya terlihat lurus.

Contoh Single Rotation
Pada contoh di atas, T melakukan AVL violation, sehingga T menjadi poros untuk proses rebalancing. Node A adalah node terdalamnya. Proses rotasi yang terjadi adalah left - left, dimana T bertukar posisi dengan S, kemudian subtree kanan dari S, menjadi subtree kiri T.

Double Rotation

Double Rotation dilakukan apabila node terdalam memiliki path yang tidak lurus dengan node yang melakukan violation, sehingga apabila ditarik garis, pathnya akan terlihat bengkok.

Contoh Kasus :
Step 1 : right - right rotation

Step 2 : left - left rotation

Pada kasus di atas, R adalah node terdalam dan T adalah node yang melakukan violation. Proses rotation yang diperlukan untuk rebalancing kasus di atas adalah right-left rotation yang dibagi menjadi 2 step.

AVL Tree : Deletion

Proses Deletion pada AVL juga sama dengan Binary Search Tree, yaitu apabila node yang dihapus adalah leaf, maka langsung dihapus saja. Apabila node yang dihapus memiliki satu child, maka childnya yang akan menggantikan. Apabila node yang dihapus memiliki dua child, maka node yang dihapus akan digantikan dengan node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Namun pada AVL, dilakukan pengecekkan setiap kali proses deletion dilakukan. Apabila tree menjadi tidak seimbang akibat proses deletion, maka rebalancing akan dilakukan (seperti pada insertion).

Contoh Kasus :

Step 1 : Node yang akan dihapus adalah node 60. Sehingga dicarikan penggantinya yaitu node terbesar dari subtree kiri, node 55.

Step 2 : Terjadi violation pada node 55, sehingga diperlukan rotation. Maka, dilakukan lah right-right rotation dengan node 55 sebagai porosnya.

Step 3 : Terjadi violation lagi di node 50. Kali ini dibutuhkan double rotation karrena pathnya bengkok. Dilakukanlah right-left Rotation dengan node 50 sebagai poros utama dan 25 sebagai poros right - right rotation.

Step 4 : Balanced AVL Tree


Sekian rangkuman pertemuan kali ini, saya harap rangkuman saya dapat membantu teman-teman dalam memahami konsep AVL Tree.

Referensi :

- http://suciantinovi.blogspot.com/2014/05/balanced-binary-tree-and-2-3-tree.html (Saya mengakui rangkuman saya sangat mirip dengan blogspot tersebut, karena memang saya mengutip blogspot tersebut. Alasannya karena saya sangat setuju dengan isi dari blogspot tersebut, penjelasannya baik. Tapi tentu saya melakukan beberapa perubahan sesuai dengan pemahaman dan preference saya)

- Slide Binusmaya : AVL Tree (hanya mengutip kasus, karena kebanyakan di internet kasusnya kurang relevan dengan apa yang saya ingin sampaikan)


Diposting oleh di Tidak ada komentar:

Sabtu, 04 April 2020

Code untuk Aplikasi dengan Double Linked List

Berikut saya cantumkan Source Code untuk menjawab tugas membuat Aplikasi AprilMarket dengan konsep Double Linked List :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

//This program does't come with proper validation since it's not mention in the query. So be wise while using this program.

struct Node{
char barang[21];
int qty, price;
Node *next, *prev;
}*head, *tail;

Node *create(char* barang, int qty, int price){
Node *temp = (Node*)malloc(sizeof(Node));
strcpy(temp->barang, barang);
temp->qty = qty;
temp->price = price;
temp->next = temp->prev = NULL;
return temp;
}

void pushHead(Node *temp){
if(!head)head = tail = temp;
else{
head->prev = temp;
temp->next = head;
head = temp;
}
}

void pushTail(Node *temp){
if(!head)head = tail = temp;
else{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}

void pushMid(Node *temp){
if(!head)head = tail = temp;
else if(strcmp(head->barang, temp->barang) > 0)pushHead(temp);
else if(strcmp(tail->barang, temp->barang) < 0)pushTail(temp);
else{
Node *curr = head;
while(strcmp(curr->barang, temp->barang) < 0){
curr = curr->next;
}
curr->prev->next = temp;
temp->prev = curr->prev;
temp->next = curr;
curr->prev = temp;
}
}

void popHead(){
Node *temp = head;
if(!head){
printf("No Data");
return;
}
else if(head==tail){
head = tail = NULL;
}else{
head = temp->next;
temp->next = temp->prev = head->prev = NULL;
temp = NULL;
}
free(temp);
}

void popTail(){
Node *temp = tail;
if(!head){
printf("No Data");
return;
}
else if(head==tail){
head = tail = NULL;
}else{
tail = temp->prev;
temp->next = temp->prev = tail->next = NULL;
temp = NULL;
}
free(temp);
}

void popSearch(char* barang){
if(!strcmp(head->barang, barang))popHead();
else if(!strcmp(tail->barang, barang))popTail();
else {
Node *curr = head;
while(strcmp(head->barang, barang)){
curr = curr->next;
if(!curr){
printf("No Data");
return;
}
}
curr->prev->next = curr->next;
curr->next->prev = curr->prev;
curr->next = curr->prev = NULL;
free(curr);
}
}

void cls(){
for(size_t i = 0; i < 30; ++i){
puts("");
}
}

bool view(){
cls();
Node *curr = head;
if(!head){
printf("Please Input Some Item First!");
getchar();
return false;
}
puts("=========================================");
while(curr!=NULL){
printf("| %20s | %4d | %7d |\n", curr->barang, curr->qty, curr->price);
curr = curr->next;
}
puts("=========================================\n");
return true;
}


void input(){
int qty, price, temp, len;
char barang[101];
do{
if(head){
view();
}
printf("Input nama barang [3-20 Characters] [No duplicate name]: ");
scanf("%[^\n]", barang);getchar();
len = strlen(barang);
}while(len < 3 || len > 20);
printf("Input quantity barang : ");
scanf("%d",&qty);getchar();
srand(time(NULL));
temp = rand() % 10 + 1;
price = temp*1000;
pushMid(create(barang,qty,price));
cls();
printf("Item berhasil di input! ");
getchar();
}

void update(){
char barang[21];
int qty;
Node* curr;
if(!view()){
return;
}
printf("Input nama barang yang ingin diupdate [Case Sensitive] : ");
scanf("%[^\n]", barang); getchar();
if(!strcmp(head->barang, barang))curr = head;
else if(!strcmp(tail->barang, barang))curr = tail;
else{
curr = head;
while(!strcmp(curr->barang, barang)){
curr = curr->next;
if(!curr){
printf("No Data");
return;
}
}
}
printf("Input nama barang baru : ");
scanf("%[^\n]", barang);getchar();
printf("Input quantity barang baru : ");
scanf("%d", &qty);getchar();
srand(time(NULL));
int temp = rand()%10 + 1;
int price = temp*1000;
curr->price = price;
strcpy(curr->barang,barang);
curr->qty = qty;
cls();
printf("Update Succesfull! ");
getchar();
}

void del(){
char barang[21];
if(!view()){
return;
}
printf("Input nama barang yang ingin dihapus [Case Sensitive] : ");
scanf("%[^\n]", barang);getchar();
popSearch(barang);
cls();
printf("Delete Succesfull! ");
getchar();
}

int calculate(){
int total = 0;
Node *curr = head;
while(curr!=NULL){
total+=(curr->qty*curr->price);
curr = curr->next;
}
return total;
}

bool checkout(){
cls();
if(!view()){
return false;
}
int total = calculate();
puts("------------------------------------------");
printf("Total : %d\n\n", total);
printf("Proceed?");getchar();
cls();
printf("Kindness is FREE! Thanks for shopping!");
getchar();
return true;
}

void menu(){
int choose;
bool exit;
do{
if(head){
view();
}else{
cls();
puts("---No Item Inputted Yet---\n\n");
}
puts("1. Input New Item");
puts("2. Update Item");
puts("3. Delete Item");
puts("4. Checkout");
printf("Choose >> ");
scanf("%d", &choose);getchar();
switch(choose){
case 1:
input();
continue;
case 2:
update();
continue;
case 3:
del();
continue;
case 4:
exit = checkout();
continue;
}
}while(!exit);
}

int main(){
menu();
return 0;

}
Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)