Data Structure 2 (Rangkuman sebelum UAS dan persiapan UAS )

Nama : Ariel Peaceo Gunawan

NIM : 2301952874

Dosen Kelas Besar: Henry Chong (D4460),

                                     Ferdinand Ariandy Luwinda (D4522)

Dosen Kelas Kecil: Diana (D4458).

Data Struct 

Pointer :

Seperti yang sudah diketahui dalam basic of programming bahwa pointer digunakan sebagai penujuk alamat suatu variabel penyimpan dimana dapat digunakan untuk mengubah isi dari value dari alamat variabel yang ditunjuk.

Dalam pointer ada dua tanda penting yaitu :

• * sebagai operator penunjuk
• & ampersand sebagai operator alamat suatu variabel

Array :

Sebuah koleksi of elemen yang mempunyai jenis data yang sama. Elemen dalam array disimpan secara berurutan dan dimulai dari index 0.

Data type :

Sebuah koleksi dari suatu object atau operasi dari suatu objek.

Seperti contoh : int : angka riil dan memiliki operasi sum, substract, divide, multiply, mod, etc

Abstract Data type :

Nama untuk data type yang dibuat atau di define oleh user dalam pemrograman. Memiliki konsep seperti class ( dalam java ) dan struct ( dalam bahasa C) . Implementasi dari ADT disebut data structure.

Type of Data structure :

1. Array
2. Linked List
3. Queues
4. Stack
5. Binary Tree 
6. Hash Table

Array :

Koleksi dari elemen yang memiliki data type sama secara linier dan hanya bisa menyimpan jumlah elemen sebanyak dari data yang sudah ditentukan dan pengaksesan datanya bisa secara random misal bisa mengakses data pada index 0 dan index tengah.

Linked List :

Koleksi node secara linier dimana bisa menyimpan data sebanyak apapun tanpa perlu menginisialisasi terlebih dahulu size penampung tetapi pengaksesannya secara berurutan atau tidak bisa random.

Memiliki 2 metod yaitu :

- Insertion 

- Deletion

Pengaplikasiannya dalam program jika tidak bisa diprediksi jumlah data yang akan disimpan misal pada perusahaan Bank.

Ada dua jenis yaitu :

• Single Linked List : hanya mempunyai satu tangan yang menggandeng data lain.
• Double Linked List : Mempunyai dua tangan yang menggandeng data lain.

Dikarenakan menggunakan Dynamic Allocation memory maka perlu nya penggunaan fungsi malloc (memory allocation) . Yang berbeda dengan ArrayList yang menggunakan Static Memory Allocation( jumlah memory sudah ditetapkan terlebih dahulu)

Dalam metode insert ada dua jenis yaitu mengisi data dari depan, belakang, dan tengah.

Dalam metode deletion atau penghapusan data perlu diingat bahwa setelah data yang dicari sudah dihapus maka rantai data dalam List tidak boleh terputus. Sehingga dapat ditemukan nya 3 kemungkinan yaitu jika data ada di depan , data ada di belakang , atau data bukan di depan maupun belakang.

Circular Linked List :

Yaitu sebuah Single linked List yang semuanya node nya saling menunjuk dan tidak ada yang terputus dan tidak ada node yang menujuk pada NULL/ node terakhir akan kembali menujuk node awal. Bisa terjadi pada Double Linked List hanya berbeda dari jumlah tangan yang bertambah sehingga fungsinya juga perlu ditambahkan untuk tangan tambahannya.

Double Linked List :

Linked List yang mempunyai 2 tangan yang digunakan untuk menunjuk ke node setelah dan node sebelum . Sehingga Linked List dapat berjalan dua arah. Sehingga insertion metode dan deletion akan memiliki fungsi tambahan karena memiliki tangan tambahan.

Stack :

Salah satu jenis Data Structure yang metode penyimpanan nya secara urutan dimana data yang pertama kali masuk akan menjadi data terakhir sedangkan data terakhir yang masuk akan menjadi data pertama dalam List tersebut.

Dalam representasi ArrayList :

Stack memiliki 2 variabel yaitu Top sebagai penujuk data yang paling dan Max sebagai batasan data yang muat dalam array tersebut.

Dalam representasi Linked List:

Dalam Linked List membuat stack lebih sulit daripada ArrayList tapi jumlah memory yang disimpan tidak perlu untuk ditetapkan terlebih dahulu / bisa berubah-ubah. Stack dalam Linked List mempunyai dua node dimana satu sebagai penyimpan nilai dan satu nya lagi sebagai penunjuk ke node lainnya. Metode deletion dan insertion pada Stack Linked List akan berhenti jika sudah mencapai Top.

Stack operation :

• Push(): Operasi pengisian atau insertion
• Pop() : Operasi penghapusan atau deletion 
• Top() : Memberi atau mereturn data value dari Top

Notasi :

• Prefix : operator nya ditulis sebelum nilai operand
• Infix : Operator ditulis/ di print diantara dua operand
• Prefix : Operator ditulis setelah operand di tulis

Depth First Search :

Metode / algoritma pencarian / Searching suatu elemen dalam tree atau graph. Bisa digunakan dengan recursive function dan stack procedure.

Queues

Sebuah data structure yang menyimpan data secara berurutan dimana data pertama yang masuk akan tetap menjadi data pertama sedangkan yang terakhir akan menjadi data terakhir.

Sebenarnya metode yang penggunaannya tidak begitu berbeda dengan stack hanya saja peletakan data nya yang berbeda. Memiliki metode / operasi yang hampir sama dengan Stack terutama untuk push dan pop nya.

Dalam queue akan ditemukan masalah jika melakukan push() dan pop() sampai dataMaks sehingga perlunya cara menanggulangi nya dengan Circular Queue jika sudah mencapai maks maka akan membuat nodenya menjadi nol begitu juga dengan node sebaliknya.

Queue Application :

• Dequeus : elemen bisa dihapus dan diinput dari depan maupun belakang / disebut head-tail List

Ada 2 varians : 

- Input restricted : Dimana pada operasi insertion hanya bisa satu arah 

- Output restricted : Dimana pada operasi Deletion hanya bisa satu arah

• Priority Queues : Dimana elemen nya disusun berdasarkan priority atau secara sorting dimana jika ditemukan data yang sama akan berlaku hukum siapa duluan dia dapat. Pada queue ini deletion akan lebih gampang karena data pada list sudah terurut.

• Breadth First Search : Sama seperti DFS merupakan algoritma searching dalam suatu tree. Dimana pencarian nya berdasarkan urutan mana yang terlebih dahulu . 

Hashing :

Merupakan teknik penyimpanan dan pengambilan keys dengan cepat. Dalam hashing sebuah String akan diambil sebuah value pendek atau keys yang mewakili String awal. Hashing menggunakan index dan keys atau short value untuk mencari item daripada mencari dengan nilai original item tersebut.

Contoh ada item : "Adi, Budi, Caki";

Setiap kata akan diambil kata awalnya yang akan dijadikan keys untuk tempat penyimpanan data tersebut. 

Beberapa metode untuk mengubah String menjadi hash keys:

• Mid-square : Mengkuadratkan value dari keys kemudian mengambil bits tengah dari hasil kuadrat value tersebut
• Division : Membagi String yang ada menggunakan modulus operator
• Folding : Membagi value of key menjadi beberapa bagian dan menjumlahkan semua value (kecuali value terakhir / diabaikan)
• Digit Extraction : Mengekstrak nilai value dari digit yang dipilih
• Rotation Hash : Menggunakan metode lainnya dan kemudian memutar posisi keys yang didapat

Melalui hashing akan memiliki permasalahan seperti terjadinya :

• Collision atau tabrakan apabila keys yang didapat sama dengan keys dari data lainnya

Cara menanggulangi nya adalah dengan menggunakan 2 handle yaitu :

1. Linear Probing : Mencari posisi kosong berikutnya dan memasukan nya disana
2. Chaining : Memasukan string ke dalam slot sebagai linked list

Tree

Data tidak linier yang mempresentasikan sebuah hierakhi relation antar data. Node dari tree tersebut tidak harus disimpan berdekatan , dapat disimpan dimananpun dan dihubungkan menggunakan pointer / Linked List.

Konsep tree :

• Root : merupakan node paling atas atau node awal
• Edge : Garis yang menghubungkan antara parent dengan child
• Leaf : Node terakhir atau node yang tidak mempunyai child
• Degree : Total subdegree dari node yang ada / cabang node anak yang ada
• Height : Level dari subtree atau banyak tingkatan degree yang ada
• Ancestor : Parent node
• Descendant : Child node

Merupakan Data Structure yang memiliki akar atau node parent awal yang dimana tiap parent dapat memiliki node child maksimal 2 yaitu child kiri dan child kanan. 

Type of Binary :

• Perfect Binary Tree : Dimana setiap levelnya memiliki jumlah kedalaman yang sama atau memiliki node genap pada tiap level kecuali level pertama
• Complete Binary Tree : Hampir sama seperti perfect binary Tree hanya saja ada satu node kosong yang terletak pada data terujung bisa node leaf paling kiri bisa leaf paling kanan
• Skewed Binary Tree : Binary Tree yang setidaknya memiliki satu node / bebas tidak ditentukan jumlahnya . Bisa berbentuk linier.
• Balance Binary Tree : Semua leaf jaraknya sama dengan leaf lainnya ke Root

Threaded Binary Tree :

Hampir sama dengan Binary Tree yang berbeda pada saat menyimpan NULL pointer. Dalam arti tidak ada boleh data yang menunjuk ke NULL pointer. 

Ada dua jenis Thread yaitu :

• One-Way Threading : Dimana ada salah satu pointer NULL yang menunjuk ke data lain
• Two-way Threading : Dimana hanya leaf terakhir paling kiri dan kanan yang menunjuk satu NULL pointer sisanya akan menunjuk ke data lainnya. 

Advantage : Memungkinkan linier tranversal elemen dari tree. Menghapus terjadi nya stack yang dimana memakan memory yang banyak dan compute time. Memungkin kan Tree untuk bergerak maju dan mundur.

Binary Search Tree :

Merupakan salah satu data structure yang menyuport insertion, deletion, searching , rapid sorting method dengan cepat dan mudah. Bisa dibilang sebagai binary Search Tree yang terurut. Dimana bagian kiri dari subtree akan menjadi elemen yang lebih kecil dari parent tree nya sedangkan bagian kanan dari subtree akan menjadi tempat elemen yang lebih besar dari parent treenya.

3 Methode of BST :

• Find() : Methode atau function untuk melakukan proses pencarian data
• Insert() : Methode atau function untuk mengisi BST
• Remove() : Methode atau function untuk melakukan penghapusan node pada BST

Untuk function remove jika data yang dihapus mempunyai subtree atau child maka data pengganti nya adalah data ke kanan sekali kemudian mencari data paling kiri atau sebaliknya.

Berikut contoh pengkodingan sederhana toko :
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<windows.h>
struct item{
char namabarang[50];
int quanty;
struct item *next,*prev;
}*head,*curr,*tail = NULL;
struct customer{
char barangbelanja[50];
int purchase;
struct customer *next1;
}*head1,*tail1,*curr1 = NULL;
struct item *createNewNode(char *namabarang,int quanty){
curr = (struct item*) malloc(sizeof(item));
strcpy(curr->namabarang,namabarang);
curr->quanty = quanty;
curr->next = NULL;
curr->prev = NULL;
return curr;
}

struct customer *createNode(char *barangbelanja,int purchase){
curr1 = (struct customer*) malloc(sizeof(customer));
strcpy(curr1->barangbelanja,barangbelanja);
curr1->purchase = purchase;
curr1->next1 = NULL;
return curr1;
}
void pushHeadCus(char *barangbelanja,int purchase){
curr1 = createNode(barangbelanja,purchase);
if(head1==NULL){
head1 = curr1;
tail1 = curr1;
}else{
curr1->next1 = head1;
head1 = curr1;
}
}
void pushTailCus(char *barangbelanja,int purchase){
curr1 = createNode(barangbelanja,purchase);
if(head1==NULL){
head1 = curr1;
tail1 = curr1;
}else{
tail1->next1 = curr1;
tail1 = curr1;
}
}
void pushMidCus(char *barangbelanja,int purchase){
if(head1==NULL){
pushHeadCus(barangbelanja,purchase);
}else if(strcmp(head1->barangbelanja,barangbelanja)>0){
pushHeadCus(barangbelanja,purchase);
}else if(strcmp(tail1->barangbelanja,barangbelanja)<0){
pushTailCus(barangbelanja,purchase);
}else{
curr1 = createNode(barangbelanja,purchase);
customer *temp = head1;
while(temp!=NULL){
if(strcmp(temp->barangbelanja,barangbelanja) <0 && strcmp(temp->next1->barangbelanja,barangbelanja) >0){
break;
}
temp = temp->next1;
}
curr1->next1 = temp->next1;
temp->next1 = curr1;
}
}

void pushHead(char *namabarang,int quanty){
curr = createNewNode(namabarang,quanty);
if(head==NULL){
head = curr;
tail = curr;
}else{
curr->next = head;
head->prev = curr;
head = curr;
}
}
void pushTail(char *namabarang,int quanty){
curr = createNewNode(namabarang,quanty);
if(head==NULL){
head = curr;
tail = curr;
}else{
curr->prev = tail;
tail->next = curr;
tail = curr;
}
}
void pushMid(char *namabarang,int quanty){
if(head==NULL){
pushHead(namabarang,quanty);
}else if(strcmp(head->namabarang,namabarang)>0){
pushHead(namabarang,quanty);
}else if(strcmp(tail->namabarang,namabarang)<0){
pushTail(namabarang,quanty);
}else{
curr = createNewNode(namabarang,quanty);
item *temp = head;
while(temp!=NULL){
if(strcmp(temp->namabarang,namabarang) <0 && strcmp(temp->next->namabarang,namabarang) >0){
break;
}
temp = temp->next;
}
curr->next = temp->next;
curr->prev = temp;
temp->next->prev = curr;
temp->next = curr;
}
}
void showAll(){
printf("===============================\n");
printf("| Nama Barang     | Quantity  |\n");
printf("===============================\n");
curr = head;
while(curr!=NULL){
printf("| %-16s| %-10d|\n",curr->namabarang,curr->quanty);
curr= curr->next;
}
printf("===============================\n");
}
void showAllCus(){
if(head1!=NULL){
printf("Customer cart\n");
printf("===============================\n");
printf("| Nama Barang     | Quantity  |\n");
printf("===============================\n");
curr1 = head1;
while(curr1!=NULL){
printf("| %-16s| %-10d|\n",curr1->barangbelanja,curr1->purchase);
curr1 = curr1->next1;
}
printf("===============================\n");
}

}
bool search(char *namabarang){
curr = head;
while(curr!=NULL){
if(strcmp(curr->namabarang,namabarang)==0){
return true;
}
}
return false;
}
bool searchCus(char *barangbelanja){
curr1 = head1;
while(curr1!=NULL){
if(strcmp(curr1->barangbelanja,barangbelanja)==0){
return true;
}
}
return false;
}
void popHeadCus(){
curr1 = head1;
head1 = curr1->next1;
free(curr1);
}
void popTailCus(char *barangbelanja){
curr1 = head1;
while(curr1!=NULL){
if(strcmp(curr1->next1->barangbelanja,barangbelanja)==0){
break;
}
curr1 = curr1->next1;
}
struct customer *temp = tail1;
tail1 = curr1;
tail1->next1 = NULL;
free(temp);
}
void popMidCus(char *barangbelanja){
if(head1==NULL){
return ;
}else if(strcmp(head1->barangbelanja,barangbelanja)==0){
popHeadCus();
}else if (strcmp(tail1->barangbelanja,barangbelanja)==0){
popTailCus(barangbelanja);
}else{
curr1 = head1;
while(curr1!=NULL){
if(strcmp(curr1->next1->barangbelanja,barangbelanja)==0){
break;
}
curr1 = curr1->next1;
}
struct customer *temp = curr1->next1;
curr->next = curr->next->next;
free(temp);
}
}
void popHead(){
curr = head;

head = curr->next;
head->prev =NULL;
free(curr);
}
void popTail(){
curr = tail;

tail = curr->prev;
tail->next = NULL;
free(curr);
}
void popMid(char *namabarang){
if(head==NULL){
return ;
}else if(strcmp(head->namabarang,namabarang)==0){
popHead();
}else if (strcmp(tail->namabarang,namabarang)==0){
popTail();
}else{
curr = head;
while(curr!=NULL){
if(strcmp(curr->next->namabarang,namabarang)==0){
break;
}
curr = curr->next;
}
struct item *temp = curr->next;
curr->next = curr->next->next;
curr->next->next->prev = curr;
free(temp);
}
}
void buygrocery(){
int choose;
int get;
long long int total=0;
int choose1;
int price =0;
char namapembeli[50];
char barangbelanja[50];
int purchase;
scanf("%[^\n]",namapembeli);
getchar();
do{
printf("Store collection\n");
showAll();

showAllCus();
printf("What do you want %s??\n",namapembeli);
printf("1. Input cart\n");
// printf("2. Update cart\n");
printf("2. Delele cart\n");
printf("3. Pay\n");
printf(">> ");
scanf("%d",&choose);
getchar();
switch(choose){
case 1 :
do{
printf("Input item you want to buy: ");
scanf("%[^\n]",barangbelanja);
getchar();
}while(search(barangbelanja)==false);
curr = head;
while(curr!=NULL){
if(strcmp(curr->namabarang,barangbelanja)==0){
break;
}
curr = curr->next;
}

do{
purchase =0;
printf("Input how much you want to buy: ");
scanf("%d",&purchase);
getchar();
}while(purchase==0 || purchase > curr->quanty);
curr->quanty -=purchase;
pushMidCus(barangbelanja,purchase);
break;
case 2 :

printf("Input item name you want to remove: ");
scanf("%[^\n]",&barangbelanja);
getchar();
curr1 = head1;
while(curr1!=NULL){
if(strcmp(curr1->barangbelanja,barangbelanja)==0){
get = curr1->purchase;
break;
}
curr1 = curr1->next1;
}
printf("%d\n",get);
popMidCus(barangbelanja);
curr = head;
while(curr!=NULL){
if(strcmp(curr->namabarang,barangbelanja)==0){
curr->quanty +=get;
break; 
}
curr = curr->next;
}
break;
case 3 :
choose1 =0;

showAllCus();
printf("Here is your total price: ");
curr1= head1;
while(curr1!=NULL){
price = (rand() % (11));
price *= 1000; 
total+= (price*curr1->purchase);
curr1 = curr1->next1;
}
printf("Rp. %lld,00\n",total);
printf("Pay ??\n");
printf("1. Yes\n");
printf("2. No\n");
printf(">> ");
scanf("%d",&choose1);
getchar();
switch(choose1){
case 1:
curr1= head1;
while(curr1!=NULL){
popHead();
}
break;
case 2 :
break;
}
break;
}

}while(choose!=3);





}
char admin[50] = "admin";
char password[50] = "Admin123";
void inputitem(){
int choose =0;
char id[50];
char pss[50];
char namabarang[50];
int quanty;
system("cls");
printf("Input your ID : ");
scanf("%[^\n]",id);
getchar();
printf("Input your password: ");
scanf("%[^\n]",pss);
getchar();
if(strcmp(admin,id)==0 && strcmp(pss,password)==0){
do{
system("cls");
showAll();
printf("What do you want admin?\n");
printf("1. Input new item\n");
printf("2. Delete item\n");
printf("3. Update item\n");
printf("4. Exit\n");
printf(">> ");
scanf("%d", &choose);
getchar();
switch(choose){
case 1 :
printf("Input item name : ");
scanf("%[^\n]",namabarang);
getchar();
printf("Input quantity : ");
scanf("%d",&quanty);
getchar();
pushMid(namabarang,quanty);
break;
case 2 :
do{
printf("Input item name : ");
scanf("%[^\n]",namabarang);
getchar();
}while(search(namabarang)==false);
popMid(namabarang);
break;
case 3 :
quanty =0;
do{
printf("Input item name : ");
scanf("%[^\n]",namabarang);
getchar();
}while(search(namabarang)==false);
curr = head;
while(curr!=NULL){
if(strcmp(curr->namabarang,namabarang)==0){
break;
}
curr = curr->next;
}
printf("Input new item name : ");
scanf("%[^\n]",namabarang);
getchar();
strcpy(curr->namabarang,namabarang);
printf("Input new quantity [0.. No change]: ");
scanf("%d",&quanty);
getchar();
if(quanty==0){
break;
}else{
curr->quanty = quanty;
}
break;
}
}while(choose!=4);

}else{
printf("You are not admin!!");
getchar();
return;
}
}
int main(){
int choose;
pushMid("aqua",90);
pushMid("catrambut",100);
pushMid("baterai",63);
do{
system("cls");
printf("Tozopedia\n");
printf("===========\n");
printf("1. Buy grocery\n");
printf("2. Input item(for admin)\n");
printf("3. Exit\n");
printf(" >> ");
scanf("%d",&choose);
getchar();
switch(choose){
case 1 :
if(head!=NULL){
system("cls");

buygrocery();
getchar();
}else{
printf("There is no item there\n");
printf("Press enter to continue...");
getchar();
}
break;
case 2 :
inputitem();
break;
}
}while(choose!=3 || choose<1 || choose >3);

return 0;
}

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;

}

Red Black Tree

Salah satu jenis self balancing Tree yang kompleks. Meskipun begitu, RBT merupakan Tree yang mempunyai good worst-case running time sehingga efisien dalam operasi insertion, searching, deletion yang dimana dapat dibuat dalam O(log n) time.

Red Black Tree Rule :

1.       Setiap Node nya akan memiliki identitas warna : Merah atau Hitam (Alasan menggunakan warna merah karena mengikuti warna pena yang sering dipakai yaitu hitam dan merah )

2.       Root akan selalu hitam secara default

3.       Setiap node eksternal akan selalu berwarna hitam

4.       Untuk setiap node merah, maka child nodenya akan selalu hitam ( node merah tidak boleh mempunyai child node nya merah juga / merah tidak boleh bertemu merah harus diselingi warna hitam)

Insertion Methode

Cara melakukan insert RBT sama seperti BST dengan recursive Function. Dengan tambahan menyelesaikan violation yang ada dalam RBT.

Setiap node baru akan berwarna merah.

Violation akan terjadi jika parent dari node adalah warna merah.

Fix Violation :

Misalkan node baru adalah q yang mempnyai parent p dan sibling parent adalah s.

Jika s adalah node merah maka ganti node p dan s menjadi hitam dan parent dari p dan s menjadi merah.

Jika s adalah node hitam maka lakukan rotation kemudian mengganti pivot terakhir saat rotation menjadi hitam dan childnya menjadi merah.

Deletion Methode

Operasi untuk mendelete data dalam Tree sama seperti BST dimana jika data yang dihapus mempnyai data atau tidak dan cara handle nya seperti apa. Tapi dengan tambahan untuk memperhatikan warna dalam node yang ada misal :

-          Node yang mau dihapus adalah M dengan child C, jika M merupakan node warna merah, posisinya tinggal digantikan dengan C.

-          Jika sebaliknya maka setelah C menggantikan posisi M maka node C diubah warna menjadi hitam.

Operasi deletion :

Sama seperti BST proses deletion nya dan mengganti nya dengan predessesor (left and last right) atau successor( right and last left).

Ketentuannya :

1.       Node yang dihapus berwarna merah : Tidak ada Violation

2.       Node yang dihapus berwarna hitam :

Node dihapus dan menandakan posisi sebagai Double Black

·         Sibling : Merah

-          Mengganti parent nya menjadi node merah

-          Mengganti sibling menjadi hitam

-          Rotate pada node yang didelete -> kemudian recheck doubleblack

·         Sibling : Hitam

-          Kedua Child : Hitam

1.       Mengganti Sibling menjadi merah

2.       Move Double Black ke parentnya ->recheck DoubleBlack

-          Salah satu child : Merah

1.       Single / Double Rotation

2.       Mengganti Child menjadi hitam  dan Last Pivot menjadi merah-> Remove Double Black

 BTree

Rules :

1. Semua leaf node harus di level yang sama.

2. Sebuah btree di define dengan term minimum degree

3. Setiap node kecuali root harus memiliki t-1 keys/value. Root boleh memiliki minimum 1 key.

4. Semua node memiliki maksimal 2t-1 keys / value nya

Insertion methode :

1. Pada operasi insertion data , key / value baru yang dimasukan akan selalu berada di node daun / leaf node terlebih dahulu.

2. Seperti di BST jika memang datanya lebih kecil dari parent class nya maka value / key itu akan masuk ke node kiri dan begitu sebaliknya untuk node kanannya.

3. Jika key / value yang sudah dimasukan sudah full pada node leaf tersebut maka akan dilakukan split dan height tree tersebut akan bertambah

4. Pada node yang sudah penuh tersebut nilai yang akan tersplit adalah nilai tengah berdasarkan data yang sudah diurutkan pada node tersebut

5. Value / keys pada setiap node akan selalu terurut secara ascending

Deletion Methode :

Deletion operation pada btree lebih kompleks daripada insert operation karena data yang didelete tidak hanya data dari leaf node tetapi juga dari node lain yang dimana kemungkinan mempunyai node child. 

1. Node yang dihapus tidak mempengaruhi height dalam btree ( Setiap leaf harus mempunyai / berada di level yang sama

2. Ada 3 case dalam deletion :

a. Kalau key / value yang dihapus berada di leaf tersebut maka tinggal menghapus data tersebut ( masih ada data lain pada node tersebut / semua leaf selevel ).

b. Jika key / value terletak pada node dalam yang memiliki subtree

c. Jika key / value berada pada root

3. Node yang dihapus jika memiliki child maka perlu digantikan seperti pada BST yaitu dengan key lainnya pada tree tersebut.

4. Jika merupakan node yang mempunyai 3 node maka ubah menjadi yang mempunyai 2 node

5. Jika merupakan node yang mempunyai 2 node maka :

a. Jika parent mempanyai 3 node cabang maka ambil salah value nya untuk menggantikan node yang dihapus. Jika sibling dari node yang dihapus mempunyai 3 node cabang , maka push data value dari sibling tersebut ke parent nya. Jika sibling dari node yang dihapus mempunyai 2 node cabang, maka buatlah parentnya menjadi node 2 cabang dan sambungkan node current dengan siblingnya.

b. Jika parent adalah node 2 cabang. Jika sibling nya adalah node 3 cabang maka ambil satu value dari parent nya dan push satu value dari siblingnya ke parent . Selain itu merge parent dengan siblingnya

Heap & Tries 

Heap 

Heap adalah Complete Binary Tree yang menggunakan konsep Heap.

Ada dua jenis Heap :

1. Min Heap : Dimana setiap node elemen nya akan lebih kecil daripada node anaknya (Root nya akan menjadi nilai terkecil dalam tree ).
2. Max Heap : Berbanding terbalik dengan min Heap yaitu dimana setiap node nya akan lebih besar daripada node anaknya (Root nya akan menjadi nilai terbesar dalam tree )

Ada satu jenis lagi heap yang merupakan gabungan antara min heap dan max heap yaitu ; Min-Max Heap , yang dimana dimulai dari root yang menjadi min heap dilanjutkan dengan anaknya yang sebagai max heap dan subtree berikutnya akan kembali ke Min heap begitu seterusnya.

Min - Heap

Setiap node nya akan lebih kecil dari node child nya. Dan root nya akan menjadi nilai terkecil dari tree tersebut dan nilai terbesar berada pada di salah satu leaf node tree tersebut. 

Implementasi nya biasanya menggunakan arraylist karena lebih mudah daripada Linked List.

Methode implementation of min heap :

• Find-min : Dengan mudah dapat diketahui karena root dalam min heap akan selalu menjadi value terkecil pada tree tersebut
• Insert : Seperti operation method pada tree lainnya min heap juga ada operasi untuk memasukan datanya
• Deletion : Menghapus value dalam tree dengan tetap menuruti syarat dalam min heap tree

Dalam implementasi array ;

Root tree tersebut akan menjadi index 1 pada arraynya. Kenapa bukan 0 karena untuk memudahkan mencari letak parent tersebut seperti untuk misal index 2 untuk mencari parent nya yaitu dengan membagi dengan angka (int) 2 sehingga didapatkan hasilnya 1 dan bukan 0 oleh sebab itu digunakan nya mulai index ke-1.

Pemberian index pada tree yaitu dari kiri ke kanan secara menurun.

Misalkan index berada di : x

Hubungan antara node dalam tree 

Parent (x) : x/2

Left-Child(x) : 2*x

Right-Child(x) : 2*x+1

Hubungan diatas merupakan alasan mengapa index root adalah 1 supaya dapat digunakan hubungan tersebut.

Find min in Min heap

Dalam operasi find min sangatlah mudah karena aturan dalam min heap sudah dipastikan root nya adalah nilai terkecil dalam tree tersebut

Insertion

Setiap ada elemen yang masuk , harus tetap konsisten mengikuti aturan dalam heap nya. Dan juga setiap elemen baru akan dimasukan awal nya di index paling akhir. Jika saat data baru dimasukan tidak sesuai dengan aturan min-heap maka perlu methode fixing tree yaitu uphead elemennya.

Uphead :

Membandingkan node yang dimulai dari index data yang baru dimasukan dan kembali ke node root. Value yang berada pada index data yang baru akan dibandingkan dengan parentnya, jika parent nya lebih besar daripada value yang baru tersebut maka value nya ditukar dan dilanjutkan uphead parent nodenya. Proses akan berhenti jika sudah mencapai root / tidak ada parent.

Deletion 

Pada min heap deletion hanya terjadi pada root nya atau head sehingga perlu digantikan posisinya awalnya dengan data dari index terakhir dari heap. Hal ini berlaku juga untuk Max-Heap . Setelah itu juga menghapus jumlah total data dalam heap tersebut. Kemudian dilakukan DownHeap root untuk memperbaiki kesalahan yang ada dalam heap setelah pengubahan data.

DownHeap pada root yaitu dengan membandingkan value dirinya ke child nya sampai ke leaf node terkecilnya. Jika ada value yang lebih kecil dari value root tersebut maka akan terjadi pertukaran data antara yang lebih kecil. Untuk menentukan root tersebut akan membandingkan value nya dengan yang mana maka kita ambil dari node child terkecil dari node tersebut dan kemudian membandingkan node anak dengan value terkecil dengan value node nya.

Max Heap

Tidak begitu berbeda dengan min heap hanya saja semua yang terjadi dan aturan dalam min-heap ditukarbalik seperti pada contoh untuk root pada Max heap merupakan data terbesar dalam tree tersebut dan setiap node dalam tree akan mempunyai child node yang lebih kecil daripada node tersebut. 

Untuk operasi Method nya pun hampir sama :

• Find-max Heap  : mereturn data root / pada index pertama
• Insertion : Sama seperti min heap dimana memerhatikan aturan dari max-heap yang berbanding terbalik dengan min-heap
• Deletion : Operasi menghapus data dengan menuruti aturan max-heap

Min-Max Heap

Kondisi heap nya akan bergantian antara minimum dan maksimum per level nya / height. 

Pada min-max heap root nya akan sama seperti konsep min heap dimana merupakan data terkecil dalam tree. Kemudian diikuti dengan data terbesar pada tree yaitu salah satu dari child rootnya. 

Untuk operasi Find(x) max dan min nya yaitu :

Find-Min(x) : mereturn value yang dimana terletak pasti pada root nya 

Find-Max(x) : yaitu mereturn data child dari root dan membandingkan antara child kiri ato kanan yang lebih besar.

Insertion Min-Max Heap

Seperti biasa pada heap yaitu dimana setiap data baru akan pertama kali diletakkan pada index terakhir dalam tree. Kemudian melakukan uphead untuk melakukan perbaikan dalam tree supaya sesuai dengan konsep min-max heap. Konsep nya berbeda dengan min-heap dan max-heap dan lebih kompleks.

Ada 2 kemungkinan yang akan terjadi dalam insertion min-max heap :

• Node baru berada di level min

1. Kondisi : Jika parent dari node baru lebih kecil maka tukar kedua valuenya dan lakukan upheadmax dari parentnya.
2. Else : Upheadmin dari node baru                   

• Node baru berada di level max

1. Kondisi : Jika parent dari node baru lebih besar maka tukar kedua valuenya dan lakukan upheadmin dari parentnya.
2. Else : Upheadmax dari node baru     

Upheadmin

Membandingkan value currNode nya dengan value grand parent dari currNode. Jika value dari currNode dan lebih kecil dari grand parent nya maka tuker value keduanya dan lakukan upheadmin kembali dari grand parent nodenya

Upheadmax

Membandingkan value currNode nya dengan value grand parent dari currNode. Jika value dari currNode dan lebih besar dari grand parent nya maka tuker value keduanya dan lakukan upheadmax kembali dari grand parent nodenya.

Deletion 

Deletion pada tree tersebut ada dua macam yaitu; deletion of smallest element dan deletion of largest element.

Deletion of smallest element

1. Mengganti value root dengan elemen terakhir dari heap / data pada index terakhir.
2. Mengurangi jumlah data dalam heap nya
3. Kemudian lakukan downheapmin dari root

Deletion of largest element

1. Mengganti value child dari root (bisa child kiri atau kanan tergantung dari yang mana paling besar nilainya) dengan elemen terakhir dari heap / data pada index terakhir.
2. Mengurangi jumlah data dalam heap nya
3. Kemudian lakukan downheapmax dari root

Downheapmin 

Andaikan m merupakan value terkecil pada currNode child dan grandchild. 

Jika m adalah grandchild dari currNode maka :

1. Jikalau m lebih kecil daripada currNode : Tukar value keduanya, kemudian jika m lebih besar daripada parentnya maka tukar valuenya lagi. Lanjut lakukan downheapmin dari m.

Jika m adalah child dari currNode nya maka :
Jika m lebih kecil daripada currNode maka tukar valuenya.

Downheapmax

Hampir sama dengan downheapmin tapi hubungan operasi berbanding terbalik

Aplikasi Heap : 

• Heap Sort : Salah satu methode sort yang terbaik dan tidak ada masalah no quadratic scenarios.
• Selection : Seperti pada kasus Find max(x) dan Find min (x)
• Graph : Implementasi minimal spanning tree algorithm

Tries

Prefix Tree yang terdiri dari data secara berurut yang disimpan dalam array. Tries digunakan untuk mencari kata dalam data kamus kata dengan prefix dari suatu kata. Pengaplikasian nya yaitu dalam auto-correction pada smarthphone.

Tries adalah tree dimana setiap vertex nya mewakili sebuah kata atau sebuah prefix. Root pada tries mewakili empty character. Length sebuah kata dihitung dari jarak antara root ke last edge dari sebuah kata.