Archive for 2020
Heaps
Pengenalan
Heap adalah sebuah struktur data berbasis tree yang memenuhi kondisi heap. Berikut merupakan kondisi-kondisi heap:
- Min Heap: Setiap node lebih kecil dari anaknya
- Max Heap: Setiap node lebih besar dari anaknya
Dari kondisi itu, kita dapat simpulkan bahwa node terkecil ada pada root (root dimulai dari index 1 u/ mempermudah dalam membuat relasi antar node), sementara node terbesar ada pada leaf. Heap bisa diimplementasikan dengan ArrayList, namun akan jauh lebih mudah jika menggunakan array.
Pengaplikasian heap pada priority queue:
- Selection Algorithm (mencari min/max, median, elemen terbesar, dll)
- Algoritma Dijkstra (mencari jalan terpendek dalam grafik)
- Algoritma Prim (mencari spanning tree yang minimum)
Sort pada heap memiliki efisiensi O(n.log(n)).
Dalam pengaplikasian heap pada priority queue, terdapat beberapa operasi seperti:
- find-min: mencari elemen terkecil dalam heap
- insert: memasukkan elemen baru dalam heap
- delete-min: menghapus elemen terkecil dalam heap
Relasi antar node pada heap dengan implemetasi array dapat dibuat dengan mudah, seperti berikut:
*misalkan index dari suatu node adalah n
- Index parent = x / 2
- Index left-child = x * 2
- Index right-child = (x * 2) + 1
Operasi
Find-min
Find-min dalam heap dapat dilakukan dengan mudah, karena node terkecil sudah pasti berada di root. Fungsi nya dapat dituliskan seperti:
int findMin(){
return data[1];
}
Insert
Min-Heap
Child dari node selalu lebih kecil dari pada parent.
Berikut adalah step by step dalam melakukan insert pada min-heap:
- Masukkan elemen baru ke bagian akhir heap (pada leaf)
- Jika node baru tersebut lebih besar daripada parentnya, lakukan upheap
- Upheap: bandingkan node dengan parentnya. Jika node > parent, tukarkan posisi antara node dengan parent. Kemudian loop terus hingga parent > node
Berikut adalah step by step dalam melakukan delete pada min-heap:
- Dalam operasi delete pada min-heap, kita hanya harus menghapus node terkecil yaitu root
- Gantikan root dengan node paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Lakukan downheap pada root agar sesuai dengan peraturan heap
- Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi
antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf
Max-heap
Child selalu lebih besar dari parent. Cara insertnya sama saja dengan min-heap, hanya saja dengan kondisi yang berkebalikan.
Min-Max Heap
Untuk min-max heap, perhatikan gambar berikut:
Dari contoh diatas kita bisa melihat bagaimana child bisa lebih kecil/besar dari parent tergantung posisi levelnya. Jika node lebih kecil dari parent pada level genap, maka node akan lebih besar dari parent pada level ganjil. Root selalu merupakan elemen terkecil, elemen terbesar sudah pasti merupakan salah satu dari root child.
Insert pada min-max heap sama saja dengan min-heap atau max-heap, namun upheap nya sedikit berbeda. Berikut penjelasan terhadap upheap untuk min-max heap:
- Upheapmin: bandingkan nilai dari node dengan nilai dari grand parentnya. Jika nilai node lebih kecil dari parentnya, tukar nilai antara node dengan parent. Lalu, lanjutkan dengan upheapmin grand parentnya.
- Upheapmax: bandingkan nilai dari node dengan nilai dari grand parentnya. Jika nilai node lebih besar dari parentnya, tukar nilai antara node dengan parent. Lalu, lanjutkan dengan upheapmin grand parentnya.
Delete
Min-Heap
Berikut adalah step by step dalam melakukan delete pada min-heap:
Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi
antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf- Dalam operasi delete pada min-heap, kita hanya harus menghapus node terkecil yaitu root
- Gantikan root dengan node paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Lakukan downheap pada root agar sesuai dengan peraturan heap
- Downheap: bandingkan node dengan kedua childnya (kiri-kanan). Jika node > child, tukarkan posisi antara node dengan child terkecil. Kemudian loop terus hingga node < child atau node telah menjadi leaf
Max-heap
Child selalu lebih besar dari parent. Cara deletionnya sama
saja dengan min-heap, hanya saja dengan kondisi yang berkebalikan.
Min-Max Heap
Untuk deletionnya, kita bisa menghapus node terkecil atau node terbesar. Berikut step nya:
- Deletion untuk node terkecil:
- Gantikan root dengan elemen paling akhir dalam heap
- Kurangkan jumlah elemen dalam heap
- Downheapmin dari root
- Deletrion untuk node terbesar:
- Gantikan antara child terbesar (kiri / kanan) dengan elemen paling akhir dari heap
- Kurangkan jumlah elemen dalam heap
- Downheapmax dari node
Downheapmin / Downheapmax:
Misalkan n adalah elemen terkecil dari child atau grand-child dari suatu node
- Jika m adalah cucu dari node:
- Jika m < node: Tukar nilai mereka
- Jika m > node: Tukar nilai mereka dan lanjutkan downheapmin dari m
- Jika m adalah anak dari node:
- Jika m < node: Tukar nilai mereka
Downheapmax sama saja dengan downheapmin, hanya saja operator relasinya dibalik.
Heaps & Tries
Pengenalan
Red-Black Tree diciptakan pada tahun 1972, oleh Rudolf Bayer. Saat pertama kali diciptakan, tree ini disebut "Symmetric Binary B-Tree". Meskipun Red-Black Tree terbilang kompleks, tree ini memiliki running time yang cepat untuk setiap operasinya serta sangat efisien.
Sebuah Binary Tree bisa disebut Red-Black Tree jika memenuhi kondisi berikut:
- Setiap node memiliki warna, antara hitam atau merah
- Root dari tree selalu berwarna hitam
- Semua external node berwarna hitam
- Jika suatu node berwarna merah, maka kedua anaknya pasti hitam
Operasi
Insertion
Red-Black tree merupakan binary tree, karena itu peraturan-peraturan pada binary tree berlaku juga pada red-black tree. Bedanya, saat melakukan insertion pada red-black tree, kita harus memperhatikan kondisi berikut:
- Jika tree masih kosong. Buat node baru sebagai root dengan warna hitam
- Jika node tidak kosong. Buat node baru sebagai leaf node dengan warna merah
- Jika parent dari node baru berwarna hitam, kita tidak perlu lakukan penyesuaian tambahan
- Jika parent dari node baru berwarna merah, cek warna sibling dari parent. Lalu perhatikan kondisi berikut:
- Jika sibling berwarna hitam, lakukan rotation sesuai dengan kondisi tree. Kemudian lakukan recolor
- Jika sibling berwarna merah, lakukan recolor. Kemudian cek apakah parent dari parent node baru adalah root atau bukan. Jika bukan, lakukan recolor kemudian recek dan sesuaikan dengan kondisi yang ada
Contoh insertion:
Deletion
Sama seperti insertion, deletion pada red-black tree juga harus memperhatikan peraturan yang ada pada binary tree. Namun pada red-black tree, deletion memiliki tambahan kondisi yang membuatnya menjadi lebih kompleks.
Penghapusan / deletion hanya bisa dilakukan pada leaf. Node lain selain leaf node hanya mengosongkan value dari node, tanpa menghapus node tersebut.
Ketika suatu node dihapus, dia akan digantikan oleh child nodenya. Warna dari child node akan menimpa warna dari parent. Sehingga saat kita menghapus suatu black node (dan dia mempunyai 2 black child), dia akan menjadi double black (DB). Hal itu juga berlaku pada leaf node, karena setiap leaf node sebenarnya memiliki 2 anak black node yang NULL (secara default).
Berikut kondisi yang perlu diperhatikan:
- Jika node yang ingin dihapus (harus leaf) adalah red node, maka node boleh langsung dihapus tanpa perlu melakukan cek kondisi atau penyesuaian tertentu
- Jika sibling dari DB adalah hitam dan kedua childnya (child dari sibling) adalah black node, ikuti step berikut:
- Hilangkan DB
- Pindahkan hitam ke parent (warna parent berubah jadi hitam jika warna awalnya merah, dan DB jika warna awalnya hitam)
- Buat sibling menjadi merah
- Jika DB masih ada, cek dan sesuaikan dengan kondisi lain
- Jika sibling DB adalah merah, tukar warna antara parent dengan sibling. Lalu rotate parent ke arah DB
- Jika sibling DB adalah hitam, dan childnya (dengan posisi paling jauh dari node DB) adalah hitam dan child lainnya (dengan posisi paling dekat dengan DB) adalah merah:
- Tukarkan warna sibling dari DB dengan warna anaknya (yang paling dekat dengan DB)
- rotate sibling ke arah menjauhi DB
- Lakukan kondisi 5
- Jika sibling DB adalah hitam, dan child dari sibling (yang jauh) adalah merah:
- Tukarkan warna parent dengan sibling
- rotate parent ke arah DB
- Hilangkan DB
- Ganti warna anak sibling yg merah, menjadi hitam
Contoh deletion:
Red Black Tree
AVL Tree
Pengenalan
Ketinggian dari suatu Binary Search Tree (BST) bisa mencapai n-1, jika BST berbentuk miring. Sementara itu kecepatan berjalannya suatu fungsi pada BST seperti insertion, deletion, searching, dan fungsi lainnya, bergantung sepenuhnya pada tinggi BST tersebut. Jika tinggi suatu BST tidak dibuat seminimal mungkin, maka kecepatan suatu fungsi juga tidak akan optimal / lambat (O(n)). Oleh sebab itu kita memerlukan Balanced Binary Seacrh Tree.Fungsi dari Balanced BST adalah membuat tinggi dari BST menjardi seminimal mungkin, dengan begitu kecepatan berjalannya suatu fungsi akan optimal (O (log n)). Balanced BST sendiri memiliki beberapa jenis, contohnya: AVL Tree, B-Tree, dll.
Konsep AVL Tree
Pada Balance Tree kita mengenal yang namanya Balance Factor (Faktor keseimbangan), dimana faktor keseimbangan harus sebesar (-1), (0), atau (1). Faktor keseimbangan pada suatu Balanced Tree dihitung dengan rumus:BalanceFactor(N) = Tinggi(SubTree kiri) - Tinggi(SubTree kanan)
Untuk praktiknya silahkan lihat gambar di bawah ini,
 |
| Source: condor.depaul.edu/glancast/383class/docs/lecFeb22.html |
*Note: berikutnya dalam blog ini, Balance Factor akan disebut dengan singkatan BF
Pada gambar di atas tiap node telah disertai keterangan tinggi / height masing-masing. Tinggi suatu node dihitung dengan menjumlahkan tinggi maksimal anak dengan satu (maximum child height + 1). Contohnya tinggi dari node 500 adalah 3, karena tinggi maksimal dari anaknya adalah 2 (tinggi node 400) dan kita tambahkan 1. Sementara untuk node yang merupakan daun / leaf tingginya adalah 0, karena tidak memiliki anak.
Setelah mendapat tinggi dari node, barulah kita dapat menghitung BF. Sebagai contoh, kita akan menghitung BF dari node 450, 400, dan 500:
- BF node 450 = 1 - 1 = 0
- BF node 400 = 1 - 2 = -1
- BF node 500 = 3 - 2 = 1
Operasi AVL Tree
InsertionUntuk fungsi insertion pada AVL sama saja dengan BST biasa, node baru dimasukkan sebagai leaf. Namun, node baru tersebut bisa saja membuat tree menjadi tidak balanced. Untuk itu kita harus melakukan rebalance, yang dapat kita lakukan dengan cara memutar posisi node atau yang disebut rotation.
Ada 4 kondisi yang harus diperhatikan saat rebalance:
*Note: misalkan X = node yang harus di rebalance
- Node terendah ada pada SubTree kiri & merupakan anak kiri dari X
- Node terendah ada pada SubTree kanan & merupakan anak kanan dari X
- Node terendah ada pada SubTree kanan & merupakan anak kiri dari X
- Node terendah ada pada SubTree kiri & merupakan anak kanan dari X
Untuk kondisi 3 & 4, kita perlu menerapkan double rotation.
Jenis rotation:
- LL rotation (Left Rotation) : kesalahan muncul dari anak kanan SubTree kanan
- RR rotation (Right Rotation) : kesalahan muncul dari anak kiri SubTree kiri
- LR rotation (Left-Right): kesalahan muncul dari anak kiri SubTree kanan
- RL rotation (Right-Left) : kesalahan muncul dari anak kanan SubTree kiri
Perhatikan gambar berikut,
 |
| Source: javatpoint.com/ll-rotation-in-avl-tree |
Pada gambar diatas, node baru dimasukkan sebagai anak kiri dari T1 pada bagian SubTree kiri. Hal tersebut membuat BF dari "A" menjadi 2, untuk itu kita melakukan LL rotation dimana "A" menjadi anak kanan dari "B". Sementara itu, anak kanan mula-mula (T2) akan kita pindahkan menjadi anak kiri dari "A". Perpindahan tersebut sudah pasti memenuhi BST karena sejak awal T2 merupakan bagian dari SubTree kiri "A", sehingga sudah pasti T2 lebih kecil dari "A".
RR Rotation
Perhatikan gambar berikut,
 |
| Source: javatpoint.com/rr-rotation-in-avl-tree |
LR Rotation
Perhatikan gambar berikut,
 |
| Source: javatpoint.com/lr-rotation-in-avl-tree |
RL Rotation
Perhatikan gambar berikut,
 |
| Source: javatpoint.com/rl-rotation-in-avl-tree |
RL rotation memiliki konsep dan cara kerja yang sama dengan LR rotation hanya saja berbeda arah.
Contoh soal:
Insert → 5, 6, 7, 0, 4, 3, 8
Jawab:
Deletion
Untuk fungsi hapus sama saja seperti deletion pada BST biasa. Bedanya, kita harus kembali melakukan pengecekan BF setelah deletion sama seperti insertion.
Contoh soal:
Delete → 3, 4, 8
Jawab:
B-Tree
Pengenalan
B-tree adalah struktur data yang memungkinkan akses data dengan cepat, dimana data disimpan pada memori sekunder dengan membuat dan menggunakan indeks untuk mengakses data yang berukuran besar.Selama ini, kita telah belajar mengenai BST. Ciri khas dari BST adalah tiap node memiliki paling banyak 2 anak, karena itu BST bisa disebut juga two-way tree. Dari pernyataan tersebut, kita bisa mengelompokkan berbagai jenis tree sebagai M-way tree dimana M merupakan jumlah maksimal anak yang bisa dimiliki suatu node. Sementara B-tree merupakan balanced tree dari M-way tree.
Ciri-ciri B-tree dari suatu M-way tree:
- Setiap node memiliki paling banyak M anak
- Setiap node kecuali root memiliki minimal M/2 anak
- root harus memiliki minimal 2 anak (bila dia bukan leaf)
- Suatu node yang bukan leaf dengan n jumlah anak, harus memiliki keys sebanyak n-1
- Setiap data disimpan secara teratur / sorted
- Setiap leaf berada level yang sama
Operasi 2-3 tree
SearchingFungsi searching pada B-tree sangat mudah, karena data sudah sorted.Berikut adalah algortima untuk fungsi searching (bahasa C):
find(ptr, x)
If
ptr is NULL then not found
If
x = A then found
If
x < A then find(ptr->left, x)
If
ptr is 3-node
If
x = B then found
If
A < x and x < B then find(ptr->middle, x)
If
B < x then find(ptr->right,x)
Insertion
Aturan memasukkan node masih sama seperti BST, dimana node baru kita masukkan ke salah satu leaf. Bedanya, kita harus mengecek apakah leaf tersebut telah berisikan 2 node atau belum. Bila leaf belum penuh, masukkan node baru ke dalam leaf. Jika leaf sudah penuh, naikkan node tengah pada leaf ke parent dan pisahkan 2 node yang sebelumnya.
Agar lebih mudah dipahami, perhatikan contoh soal berikut:
Insert → 5, 6, 7, 0, 4, 3, 8
Jawab:
Deletion
Untuk deletion perhatikan kondisi berikut:
- Bila key yang ingin dihapus berada pada node x dan merupakan leaf, langsung hapus
- Bila key yang ingin dihapus berada pada node x dan merupakan internal node, maka sesuaikan dengan syarat:
- kalau parent punya 3 node, ambil salah satu isinya. kalau anak punya 3 node, push salah satunya ke parent. Kalau anak hanya 2 node, masukkan salah satu parent ke anak.
- kalau parent punya 2 node. jika anak punya 3 node, ambil salah satu node dari parent dan push satu isi dari anak ke parent. Selain kondisi tersebut, maka gabungkan parent dengan anak.
Delete → 3, 4, 8
Jawab:
Peraturan untuk fungsi pada 2-3 tree berlaku juga pada 4-5 tree, Namun batasan untuk isi suatu node lebih besar.
AVL and B - Tree
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node{
char productName[100];
int qty;
int price;
struct node *prev, *next;
}*head = NULL, *tail = NULL;
void pushData(char productName[], int qty, int price){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
//prepare newNode
strcpy(newNode->productName, productName);
newNode->qty = qty;
newNode->price = price;
newNode->next=NULL;
newNode->prev=NULL;
if(head==NULL){
head=tail=newNode;
}
else if(strcmp(productName, head->productName)<0){
newNode->next=head;
head->prev=newNode;
head=newNode;
}
else if(strcmp(productName, tail->productName)>0){
newNode->prev=tail;
tail->next=newNode;
tail=newNode;
}
else
{
struct node *ptr = head;
while(ptr!=NULL){
if(strcmp(productName,ptr->productName)<0){
newNode->next=ptr;
newNode->prev=ptr->prev;
ptr->prev->next=newNode;
ptr->prev=newNode;
break;
}
ptr = ptr->next;
}
}
}
void editData(char productName[], int qty, int price){
struct node *find = head->next;
if(strcmp(productName,head->productName)==0){
head->qty=qty;
head->price=price;
}
else
{
while(find!=NULL){
if(strcmp(productName,find->productName)==0){
find->qty=qty;
find->price=price;
break;
}
find=find->next;
}
}
}
void deleteData(char productName[]){
struct node *del = head->next;
if(head==tail)
{
if(strcmp(productName,head->productName)==0){
head=tail=NULL;
}
}
else if(strcmp(productName,head->productName)==0){
struct node *ptr = head;
head=head->next;
head->prev=NULL;
free(ptr);
}
else if(strcmp(productName,tail->productName)==0){
struct node *ptr2 = tail;
tail=tail->prev;
tail->next=NULL;
free(ptr2);
}
else{
while(del!=NULL){
if(strcmp(productName,del->productName)==0){
del->prev->next=del->next;
del->next->prev=del->prev;
del->next=NULL;
del->prev=NULL;
free(del);
break;
}
del=del->next;
}
}
}
void printData(){
struct node *ptr = head;
if(ptr==NULL){
printf("No product...\n");
}
else{
printf("| Product | QTY | Price |\n");
printf("=========================\n");
while(ptr!=NULL){
printf("| %s | %d | %d |\n", ptr->productName, ptr->qty, ptr->price);
ptr = ptr->next;
}
}
}
int main(){
int menu, qty, price, newQty, newPrice;
int up = 100000;
int low = 10000;
char productName[100], productFind[100], productDel[100];
do{
system("cls");
printf("=====================\n");
printf("TOKO KOH MORENO JAYA\n");
printf("=====================\n\n");
printData();
printf("\n\n=================");
printf("\n------MENU------\n");
printf("=================\n");
printf("1. Add product\n");
printf("2. Edit product quantity\n");
printf("3. Delete product\n");
printf("4. Checkout\n");
printf("Choose >> ");
scanf("%d", &menu); getchar();
switch(menu)
{
case 1:
printf("Input product name: ");
scanf("%[^\n]", &productName); getchar();
printf("Input product quantity: ");
scanf("%d", &qty); getchar();
price = (rand()%(up-low+1))+low;
pushData(productName, qty, price);
printf("Data Succesfully Added!");
break;
case 2:
printf("Select a product to change: ");
scanf("%[^\n]", &productFind); getchar();
printf("Input new quantity: ");
scanf("%d", &newQty); getchar();
newPrice = (rand()%(up-low+1))+low;
editData(productFind, newQty, newPrice);
printf("Data has been updated!");
break;
case 3:
printf("Select a product to remove: ");
scanf("%[^\n]", &productDel);
deleteData(productDel);
printf("Data has been removed");
break;
}
}while(menu!=4);
printf("Kindness is free ;)\n");
return 0;
}
#include <string.h>
#include <stdlib.h>
struct node{
char productName[100];
int qty;
int price;
struct node *prev, *next;
}*head = NULL, *tail = NULL;
void pushData(char productName[], int qty, int price){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
//prepare newNode
strcpy(newNode->productName, productName);
newNode->qty = qty;
newNode->price = price;
newNode->next=NULL;
newNode->prev=NULL;
if(head==NULL){
head=tail=newNode;
}
else if(strcmp(productName, head->productName)<0){
newNode->next=head;
head->prev=newNode;
head=newNode;
}
else if(strcmp(productName, tail->productName)>0){
newNode->prev=tail;
tail->next=newNode;
tail=newNode;
}
else
{
struct node *ptr = head;
while(ptr!=NULL){
if(strcmp(productName,ptr->productName)<0){
newNode->next=ptr;
newNode->prev=ptr->prev;
ptr->prev->next=newNode;
ptr->prev=newNode;
break;
}
ptr = ptr->next;
}
}
}
void editData(char productName[], int qty, int price){
struct node *find = head->next;
if(strcmp(productName,head->productName)==0){
head->qty=qty;
head->price=price;
}
else
{
while(find!=NULL){
if(strcmp(productName,find->productName)==0){
find->qty=qty;
find->price=price;
break;
}
find=find->next;
}
}
}
void deleteData(char productName[]){
struct node *del = head->next;
if(head==tail)
{
if(strcmp(productName,head->productName)==0){
head=tail=NULL;
}
}
else if(strcmp(productName,head->productName)==0){
struct node *ptr = head;
head=head->next;
head->prev=NULL;
free(ptr);
}
else if(strcmp(productName,tail->productName)==0){
struct node *ptr2 = tail;
tail=tail->prev;
tail->next=NULL;
free(ptr2);
}
else{
while(del!=NULL){
if(strcmp(productName,del->productName)==0){
del->prev->next=del->next;
del->next->prev=del->prev;
del->next=NULL;
del->prev=NULL;
free(del);
break;
}
del=del->next;
}
}
}
void printData(){
struct node *ptr = head;
if(ptr==NULL){
printf("No product...\n");
}
else{
printf("| Product | QTY | Price |\n");
printf("=========================\n");
while(ptr!=NULL){
printf("| %s | %d | %d |\n", ptr->productName, ptr->qty, ptr->price);
ptr = ptr->next;
}
}
}
int main(){
int menu, qty, price, newQty, newPrice;
int up = 100000;
int low = 10000;
char productName[100], productFind[100], productDel[100];
do{
system("cls");
printf("=====================\n");
printf("TOKO KOH MORENO JAYA\n");
printf("=====================\n\n");
printData();
printf("\n\n=================");
printf("\n------MENU------\n");
printf("=================\n");
printf("1. Add product\n");
printf("2. Edit product quantity\n");
printf("3. Delete product\n");
printf("4. Checkout\n");
printf("Choose >> ");
scanf("%d", &menu); getchar();
switch(menu)
{
case 1:
printf("Input product name: ");
scanf("%[^\n]", &productName); getchar();
printf("Input product quantity: ");
scanf("%d", &qty); getchar();
price = (rand()%(up-low+1))+low;
pushData(productName, qty, price);
printf("Data Succesfully Added!");
break;
case 2:
printf("Select a product to change: ");
scanf("%[^\n]", &productFind); getchar();
printf("Input new quantity: ");
scanf("%d", &newQty); getchar();
newPrice = (rand()%(up-low+1))+low;
editData(productFind, newQty, newPrice);
printf("Data has been updated!");
break;
case 3:
printf("Select a product to remove: ");
scanf("%[^\n]", &productDel);
deleteData(productDel);
printf("Data has been removed");
break;
}
}while(menu!=4);
printf("Kindness is free ;)\n");
return 0;
}
Program Toko Koh Moreno Jaya
Linked List I
- Linked List : sebuah struktur data linear yang terdiri dari data berurut sehingga tiap data berisi referensi ke data berikutnya dalam urutan.
- Elemen dalam Linked List disebut Node
- Linked List memungkinkan Insertion dan Deletion pada node di lokasi manapun dalam list
- Linked List dibagi kedalam dua bentuk : Single Linked List & Double Linked List
- Linked List hanya bisa diakses secara sekuensial (berurutan) sesuai jejak penyimpanan data
- Single linked list : setiap node hanya memiliki 1 pointer mengarah ke node lain
Linked List (ii)
Circular
Linked List : Circular Linked List adalah varian dari Linked List dimana node
pertama (head) menunjuk ke node terakhir (tail) dan kebalikannya. Circular
dapat dibentuk dengan single maupun double linked list
Circular
Doubly Linked List : Sama dengan yang single, hanya saja total pointer ada dua.
Double
linked list : Linked list dimana setiap node memiliki 1 pointer keareah node berikutnya
dan 1 pointer kearah node sebelumnya. Seperti halnya single linked list, double
linked list juga dapat melakukan insert dan delete.
Insert :
seperti single linked list, pertama kita harus mengalokasikan node baru
kedalam list, menetapkan value pada node tersebut, dan barulah kita sambungkan
ke list.
Contoh :
1. Jika kita ingin menaruh node baru tersebut dibelakang tail
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
struct tnode *node = (struct tnode*) malloc(sizeof(struct tnode));
node->value
= x;
node->next = NULL;
node->prev = tail;
tail->next = node;
tail =
node;
struct tnode *a = ??;
struct tnode *b = ??;
struct tnode *node = (struct
tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next =
b;
node->prev =
a;
a->next =
node;
b->prev =
node
Delete :
4 kondisi yang harus diperhatikan saat melakukan delete:
- Node yang akan dihapus adalah satu-satunya node di linked list
- Node berada di Head
- Node berada di Tail
- Node berada diantara Head dan Tail
- Jika sesuai kondisi (1)
free(head);
head = NULL;
tail = NULL;
head = NULL;
tail = NULL;
- Jika sesuai kondisi (2)
head = head->next;
free(head->prev);
head->prev = NULL
free(head->prev);
head->prev = NULL
- Jika sesuai kondisi (3)
tail =
tail->prev;
free(tail->next);
tail->next = NULL;
free(tail->next);
tail->next = NULL;
- Jika sesuai kondisi (4)
struct tnode *curr = head;
while ( curr->next->value != x ) curr = curr->next;
struct tnode *a = curr;
struct tnode *del = curr->next;
struct tnode *b = curr->next->next;
a->next = b;
b->prev = a;
free(del);
while ( curr->next->value != x ) curr = curr->next;
struct tnode *a = curr;
struct tnode *del = curr->next;
struct tnode *b = curr->next->next;
a->next = b;
b->prev = a;
free(del);
Stack
Stack merupakan struktur data yang menyimpan elemen-elemennya secara teratur menggunakan prinsip LIFO (Last in First out). Sesuai dengan artinya secara langsung, dalam prinsip LIFO data yang terakhir kali dimasukkan akan menjadi yang pertama saat dikeluarkan.Stack adalah struktur data linear yang dapat diimplementasikan dengan menggunakan Array atau Linked List.
Stack dengan array
Stack memiliki 2 variable :- TOP : menyimpan alamat elemen paling atas dari stack
Catatan :- Jika TOP = NULL, maka stack kosong
- Jika TOP = MAX - 1, maka stack full
- Jika TOP = integer tertentu, maka insertion dan deletion akan berakhir pada posisi tersebut
- MAX : menyimpan jumlah maksimum elemen yang dapat ditumpuk oleh stack
Stack dengan linked
Pada Linked Stack, setiap node mempunyai 2 bagian:- satu menyimpan data
- satu menyimpan alamat node berikutnya
Operasi pada Stack
push() : menambah objek kedalam stackpop() : menghilangkan sebuah objek dalam stack
top() : mengembalikan TOP objek dari stack
Infix, Prefix, dan Postfix
Prefix : operator ditaruh sebelum operand- contoh : + 5 * 3 4 = 17
- contoh : 5 + 3 * 4 = 17
- contoh : 5 3 4 * + = 17
Evaluasi untuk postfix (secara manual)
Scan dari kiri ke kanan
7 6
5 x 3
2 ^ – + , scan sampai menemukan operator pertama
7 6
5 x
3 2 ^
– + , hitunglah 6 * 5
7 30
3 2 ^
– + , scan lagi hingga menemukan operator berikutnya
7 30
3 2 ^ – + , hitung 32
7 30
9 – + , scan lagi hingga menemukan operator berikutnya
7 30 9 –
+ , hitung 30 - 9
7 21 + , scan lagi
7
21
+ ,
hitung 7 + 21
28 , Jawaban akhir
Evaluasi untuk prefix (secara manual)
Scan dari kanan ke kiri
+ 7
– x 6
5 ^ 3 2 , Scan hingga menemukan operator pertama
+ 7
– x 6
5 ^
3 2 , hitung 32
+ 7
– x 6
5 9 , Scan lagi hingga menemukan operator berikutnya
+ 7
– x
6 5
9 , hitunglah 6 * 5
+ 7
– 30 9 , Scan hingga menemukan operator berikutnya
+ 7 – 30
9 , hitung 30 - 9
+ 7 21 , Scan hingga menemukan operator berikutnya
+
7 21 , hitung 7 + 21
28 , Jawaban akhirCara konversi infix ke postfix
- Cari operator dengan precedence (prioritas) tertinggi
- Taruh operator tersebut dibelakang operand
- Ulangi hingga selesai
Cara konversi infix ke prefix
- Cari operator dengan precedence (prioritas) tertinggi
- Taruh operator tersebut setelah operand
- Ulangi hingga selesai
Depth First Search
Depth First Search adalah algoritma yang dipakai untuk pencarian jalur pada tree atau graph. Pencarian mulai dari akar kemudian merambat sejauh mungkin sepanjang masing-masing cabang dari tree lalu barulah melakukan backtracking.Penggunaan DFS:
- menemukan titik artikulasi dan menjembatani pada grafik
- menemukan komponen yang terhubung
- Topological sorting
- dan lain-lain
Queue
Queue dapat diimplementasikan dengan array atau Linked List.Elemen-elemen pada queue disimpan dengan metode First in First out (FIFO), sehingga data yang pertama kali masuk akan dikeluarkan pertama kali juga. Data dimasukkan melalui salah satu ujung (rear) dan keluar pada ujung lainnya (front).
Queue memiliki 2 variabel yaitu front dan rear yang menunjuk posisi dimana deletion dan insertion dilakukan.
Queue dengan Linked
Dalam linked queue setiap elemen memiliki 2 bagian:- satu menyimpan data
- satu menyimpan alamat untuk elemen berikutnya
Operasi dalam queue
- push() : menambah data pada rear
- pop() : menghilangkan data pada front
- front() / peek : mengembalikan value data paling depan dari queue
Circular Queue
Definisi dari circular queue sama saja dengan queue hanya saja posisi terakhir dihubungkan kembali dengan posisi awal.Pengaplikasian Queue
- Deques
- Priority Queue
- Breadth First Search
Deques
Deques (double-ended queue) adalah list dimana elemen dapat ditambahkan atau dihapus melalui ujung manapun.Dikenal juga dengan nama head-tail Linked List karena elemen dapat ditambahkan atau dihapus dari front (head) atau back / rear (tail).
Dua macam Deques:
- Input Restricted Deque : dalam deque ini hanya deletion yang dapat dilakukan dari kedua ujung
- Output Restricted Deque : dalam deque ini hanya insertion yang dapat dilakukan dari kedua ujung
Priority Queue
Priority queue adalah tipe data abstrak yang mirip dengan queue biasa. Namun, tiap elemen memiliki prioritas sendiri.Elemen dengan prioritas lebih tinggi akan diproses terlebih dahulu sebelum elemen dengan prioritas lebih rendah.
Elemen dengan tingkat prioritas yang sama akan diproses sesuai dengan urutan data yang pertama kali muncul / first come first serve (FCFS).
Breadth First Search
BFS sama saja dengan DFS, bedanya data structure yang digunakan adalah queue bukan stack.Hash
Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.Dalam hashing string akan diubah menjadi string yang lebih pendek sebagai keys (kunci kata) dari string originalnya.
Hashing digunakan untuk mengindeks dan mengambil data dalam database karena teknik mencari kata kunci ini lebih cepat daripada harus mencari langsung data originalnya.
Hashing juga dapat disebut sebagai konsep mendistribusikan keys dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut hash function.
Hash Table
Hash Table adalah tabel (array) tempat menyimpan string original.Index untuk array pada hash table disebut hashed key, sementara value adalah string original dari key tersebut.
Beberapa string bisa saja memiliki keys yang sama.
Hash Function
berikut beberapa method untuk meng-hash keys dari string:- Mid-square
- Division
- Folding
- Digit Extraction
- Rotating Hash
Value dari string dipangkatkan, kemudian sebagian angka dari hasil pangkat tersebut dipakai sebagai key.
Contoh:
value = 1254; hasil pangkat = 1572516; hash = 725
Division:
String/identifier dimodulo dengan suatu integer (biasanya memakai bil. prima, size dari tabel, atau size memori yang digunakan).
Contoh:
Misal kita punya string berupa "ABCD". Jumlahkan ASCII dari string tersebut dan bagi dengan salah satu angka prima misalnya 2.
(65 + 66 + 67 + 68) / 2 = 266 / 2 = 133
Folding:
Pisahkan string/identifier ke beberapa bagian, kemudian jumlahkan bagian-bagian tersebut.
Contoh:
Misal kita memiliki integer 6721, pisahkan menjadi 2 bagian yaitu 67 dan 21, kemudian jumlahkan menjadi 83.
Digit Extraction:
Mengambil beberapa digit dari angka yang diberikan dan digabungkan menjadi key.
Contoh:
Misal kita memiliki integer 1435462. Ambil digit ke-1, ke-3, dan ke-5 maka kita mendapat 134
Rotating Hash:
Gunakan method manapun untuk mendapat hash code/address kemudian putar balik angka yang telah didapat untuk mendapat hash code/address yang baru.
Contoh:
Misal kita menggunakan method division, putar balik hash yang didapat dari 133 menjadi 331
Collision
Collision terjadi saat beberapa string menggunakan hash key yang sama.Cara yang biasa digunakan untuk mengatasinya adalah:
- Linear Probing : Cari slot kosong berikutnya dan masukkan kesana
- Chaining : Memasukkan string sebagai list berantai (linked list)
Untuk chaining, kita hanya perlu melakukan iterate untuk mencari string yang diinginkan.
Tree
Tree adalah struktur data non-linear yang menggambarkan hubungan hierarki antara objek data.Untuk penggambaran, node pada tree tidak perlu digambarkan berdekatan dan boleh ditaruh dimana saja. Node pada tree dihubungkan dengan pointer.
Konsep Tree
- Node teratas disebut root
- Garis yang menyambungkan parent dengan child disebut edge
- Nodes yang tidak memiliki child disebut leaf
- Nodes dengan parent yang sama disebut sibling
- Total sub-tree suatu node disebut degree
- Maximum degree suatu node pada tree disebut height / depth
- Node yang berada diatas node lain dan saling terhubung disebut ancestor
- Node yang berada dibawah node lain dan saling terhubung disebut descendant
Binary Tree
Binary tree adalah struktur data rooted tree dimana masing-masing node paling banyak memiliki dua anak. (left child dan right child)Tiper-tipe binary tree:
- Perfect Binary Tree
- Complete Binary Tree
- Skewed Binary Tree
- Balanced Binary Tree
Complete binary tree : binary tree dimana setiap level kecuali yang terakhir, terisi penuh, dan semua anak node pada level terakhir harus menempati titik kiri.
Skewed binary tree : binary tree dimana setiap node setidaknya memiliki satu anak.
Balanced binary tree : jarak setiap leaf dengan root adalah sama.
Implementrasi binary tree pada array :
- Index untuk node root = 0
- Index left child = 2p + 1 (p = index parent)
- Index right child = 2p + 2 (p = index parent)
- Index parent = (p - 1) / 2
Threaded Binary Tree
Threaded Binary Tree sama saja dengan binary tree hanya saja berbeda dalam cara penyimpanan pointer NULL.Ruang node yang terbuang karena menyimpan NULL dapat dipakai secara lebih efisien.
Ruang tersebut dapat dipakai untuk menyimpan pointer ke in-order predecessor dan in-order successor (pointer-pointer ini disebut thread).
Binary Search Tree
Definition
Binary search tree adalah sebuah struktur data yang memungkinkan pencarian cepat, penyortiran cepat, serta penyisipan dan penghapusan data yang mudah.Binary serach tree (BST) juga dikenal sebagai sorted version of binary tree atau versi binary tree yang terurut.
Aturan node pada BST :
- Tangan kanan pada node akan menunjuk ke anak node dengan key lebih besar dari dia
- Tangan kiri pada node akan menunjuk ke anak node dengan key lebih kecil dari dia
BST Operations
BST memiliki 3 operasi dasar:- search( ) : untuk mencari key tertentu dalam BST
- insert( ) : untuk memasukkan key baru ke dalam BST
- remove( ) : untuk menghilangkan key tertentu dalam BST
Seacrh Operation
Operasi search dilakukan mulai dari root (node pertama). Jika root adalah node yang dicari maka operasi search selesai. Jika tidak, maka cek key dari node yang dicari apakah lebih besar atau lebih kecil dari root. Bila key yang dicari lebih kecil, maka search dilakukan secara rekursif pada sub-tree sebelah kiri dan kebalikannya jika key lebih besar.Insert Operation
Operasi insert dilakukan mulai dari root (node pertama). Node baru akan dimasukkan pada leaf (bagian dari tree yang belum memiliki child node sama sekali) dan menjadi leaf baru. Jika key dari node baru tersebut lebih kecil dari root maka dia akan melakukan rekursif hingga menemukan leaf pada sub-tree sebelah kiri. Berlaku kebalikan jika key dari node baru lebih besar dari root.Delete Operation
Operasi delete sedikit lebih rumit daripada operasi search dan insert. Dalam operasi delete kita harus memperhatikan 3 kondisi:- Jika key yang ingin dihapus ada pada leaf, langsung hapus node tersebut
- Jika key yang indin dihapus memiliki 1 child node, maka child node tersebut harus menggantikan posisi parent node yang akan dihapus.
- Jika key yang ingin dihapus memiliki 2 child node, maka pilih salah satu cara untuk menggantikan node tersebut. Cara pertama adalah dengan memilih node paling kanan dari sub-tree sebelah kiri, cara kedua adalah dengan memilih node paling kiri dari sub-tree sebelah kanan.
Tugas Kelas Besar
Berikut saya sertakan link untuk code tugas kelas besar: