Xaviet

Heaps & Tries

noreply@blogger.com (Felicia Angelina) — Sun, 17 May 2020 03:14:00 -0700

heaps itu terbagi menjadi 3 jenis:

min heap
max heap
min-max heap

heap itu selalu berurut, jika min heap maka root akan merupakan angka yang paling kecil dan semaikin kebawah semakin besar. dan ketika di insert baru dia akan selalu mencocokkan dengan parentnya terus hinga angka yang diatasnya lebih kecil daripada dia. dan ketika di delete dia akan mencari angka yang lebih kecil antara childnya. hal ini pun juga berlaku untuk max heap.

sedangkan dengan min-max heap mereka berbeda pada setiap levelnya. misalnya pada level genap akan selalu min dan ganjill max. jadi mereka membandingkan dengan kedua sisi atas bawah.

tries itu merupakan prefix tree dimana dia akan memanfaatkan huruf yang ada sebelumnya dan mencabang dari sana sehingga menghemat banyak tempat dalam penyimpanannya

AVL Tree

noreply@blogger.com (Felicia Angelina) — Sun, 3 May 2020 07:03:00 -0700

Pada pertemuan kali ini saya mempelejari tentang AVL Tree. AVL Tree merupakan salah satu contoh dari balanced binary search tree.

AVL Tree harus memiliki sisi yang jarangnya satu sama lain tidak boleh lebih dari 1. Jika lebih maka itu tidak balance dan harus segera diperbaiki. Dan lebih baik apabila tidak ada perbedaan sama sekali agar menjadi benar-benar balance.

Setiap AVL Tree melakukan insert maupun delete harus diperhatikan balance atau tidak.

Jika AVL Tree tersebut tidak balance maka akan ada 2 pilihan cara membenarkannya: yaitu, single rotation dan double rotation.

Sisanya secara dasar sama dengan tree biasa. Jika lebih besar dari parent akan dimasukkan ke sisi kanan dan jika lebih kecil akan dimasukkan ke sisi kiri.

Ketika melakukan insertion dapat terjadi 4 kasus dimana masing-masing tidak seimbang dan harus diperbaiki.

LL rotation, hal ini dapat diperbaiki dengan single rotation dengan mudahnya.
RR rotation, sama pula halnya seperti LL rotation hal ini dapat diperbaiki dengan single rotation
LR rotation, sedangkan dengan ini tidak bisa dengan single rotation tapi harus dengan double rotation.
RL rotation, sama halnya dengan LR rotation hal ini dapat dipeerbaiki dengan double rotation.

Rangkuman

noreply@blogger.com (Felicia Angelina) — Sat, 4 Apr 2020 08:59:00 -0700

array dan linked list bisa dibilang sama namun tak sama.
perbedaan array dan linked list adalah
array

kumupulan dari data
menyimpan datanya di memory yang beruurtan
bisa mengakses data mana saja secara langsung

linked list

kumpulan dari node
menyimpan node di memory yang secara acak
hanya bisa diakses secara berurutan

array dan linked list memiliki kelebihan dan kekurangan tersendiri.
contohnya adalah
kelebihan array

mudah digunakan
lebih cepat megakses data mana saja

kekurangan array

ukuran tidak dapat dirubah sehingga terkadang memakan banyak memory

kelebihan linked list

penggunaan memory sesuai banyaknya data yang ada sehingga irit
sistemnya fleksibel

kekurangan linked list

pengerjaan lebih komples

linked list terdapat banyak macam, beberapa contohnya adalah

circular linked list
double linked list

circular linked list dalam permasalahan yang berhubungan dengan head dan tail memang lebih cepat diselesaikan dan juga ia bisa ke node manapun.

namun apa bila tidak di coding dengan benar dapat terjadi infinite loop dan juga karena ia hanya satu arah, ia tidak bisa mundur sehingga jika ia harus mengelilingi list terlebih dahulu untuk mencapai sebuah node jika ia terletak disebelumnya.

linked list cara kerjanya adalah dengan cara menyimpan alamat satu sama lain bukan dengan menyimpan isi dari alamat tersebut.

setiap alamat akan mempunyai hubungan dengan alamat berikutnya sehingga mereka akan saling menyambung
seperti di atas cara kerjanya data pertama jika di next maka dia akan ke data b karena setelah data a itu tersimpan alamat dari data b.

head akan selalu ada pada data pertama sedangkan pada ujung akan bernama tail dan dia tidak akan menunjuk kemana-mana maka panak tersebut dituliskan NULL.

pada linked list biasa dia tidak bisa bergerak mundur maka ia akan selalu bergerak dari head ke tail.

seperti berikut adalah codingnya

coding di atas adalah untuk memasukan data kedalam linked list

sedangkan dibawah ini adalah cara menghapus data paling atas dari linked list

double hampir sama dengan linked list biasa namun bedanya dia bisa mundur
cara kerjanya seperti di bawah ini

Hashing

Hashing merupakan Teknik untuk menyimpan dan mengambil keys dengan cara yang cepat.

Hashing menyimpan keysnya di array yang bernama hash table dan menggunakan function yang sudah ditentukan yaitu hash function.

Hashing terdapat 5 jenis:

Mid-square
Division (paling sering digunakan)
Folding
Digit Extraction
Rotating Hash

Mid square caranya adalah dengan mempangkatkan angka yang ingin disimpan yang kemudian akan diambil angka tengahnya.

Divison caranya adalah dengan memodulus angka yang ingin disimpan dengan ukuran dari size table yang diberikan/digunakan.

Folding caranya adalah dengan membagi setiap angka menjadi 2 bagian yang kemudian akan saling ditambahkan.

Digit extraction caranya adalah mengambil digit pada letak-letak terntetu yang sudah ditentukan sebelumnya dan angka tersebut kemudian akan menjadi hash addressnya.

Rotating hash caranya adalah menggunakan mid-square atau division terlebih dahulu buat dapet hash adressnya dan kemudian dibalik angkanya.

Hashing pada saat ini digunakan dalam blockchain, terutama dalam cryptocurrency. Hashing sangatlah penting dalam pengaturannya. Hash bagaikan backbone dalam cryptocurrency.

Hash membantu dalam menyimpan data yang sangat banyak dalam blockchain.

Collision

Collasion terjadi ketika ada string yang memiliki hash key yang sama contohnya seperti float dan floor dimana sama-sama berawalan f.

Collison bisa diatasi dengan 2 cara:

Linear probing
Chaining

Linear probing adalah mencari tempat kosong selanjutnya dan menaruhnya disana. Namun, cara ini sangatlah tidak efisien karena ketika string tersebut ingin dicari looping yang dilakukan akan banyak.

Chaining adalah meletakkan string tersebut sebagai linked list jadi apa bila floor terletak di hash key 5 maka ia linked list ke float jadi tidak membuang-buang waktu untuk mencarinya.

Tree

Tree merupakan struktur yang menunjukan hirarki antar non-linear data.

Node dalam tree tidak perlu disimpan secara berurut, ia dapat disimpan secara asal dan kemudian dihubungkan dengan pointer.

Konsep tree

Node yang paling diatas disebut root.
Line yang menghubungankan antara parent dan child disebut edge.
Node yang tidak memiliki children disebut leaf.
Node yang memiliki parent yang sama disebut sibling.
Degree of node mereupakan jumlah dari sub tree sebuah node.
Height/Depth merupakan maksimum degree dalam sebuah tree.
Jika ada line yang menghubungkan antara p dan q, maka p disebut ancestor dari q, dan q adalah descendant dari p.

Binary tree

Konsep binary tree

Binary tree merupakan struktur data tree dimana setiap node maksimal memiliki 2 node.
Setiap 2 children tersebut biasanya dibedakan sebagai left child atau right child.
Node yang tidak memiliki children disebut leaf.

Tipe binary tree

Perfect binary tree
Complete binary tree
Skewed binary tree
Balanced binary tree

Perfect binary tree adalah dimana setiap level mempunyai height/depth yang sama.

Complete binary tree adalah binary tree yang setiap levelnya, kecuali yang terakhir terisi penuh dan semua node dipenuhkan pada sisi kiri tree. Semua perfect binary tree merupakan complete binary tree.

Skewed binary tree merupakan tree yang setiap nodenya maksimal memiliki 1 child.

Balanced binary tree merupakan tree dimana leaf yang satu tidak boleh lebih jauh levelnya dari leaf yang lain jadi harus seimbang.

Berikut adalah codingan untuk menu sebuah supermarket dengan double linked list

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

struct data{
char nama[100];
int harga;
int qty;
struct data *next;
struct data *prev;
}*head, *tail;

void push(char vnama[100], int vqty, int vharga){
struct data *node = (struct data*)malloc(sizeof(struct data));

strcpy(node->nama, vnama);
node->qty = vqty;
node->harga = vharga;

node->next = node->prev = NULL;

if(head == NULL){
head = tail = node;
}else if(strcmp(head->nama, vnama)>0){
node->next = head;
head->prev = node;
head = node;
}else if(strcmp(tail->nama, vnama)<0){
node->prev = tail;
tail->next = node;
tail = node;
}else{
struct data *curr = head;
while(strcmp(curr->next->nama, vnama)<0){
curr = curr->next;
}
curr->next->prev = node;
node->next = curr->next;
curr->next = node;
node->prev = curr;
}
}

void pop(char vnama[100]){
if(head != NULL){
if(head==tail && strcmp(head->nama,vnama)==0){
free(head);
head =tail = NULL;
}else if(strcmp(head->nama,vnama)==0){
head = head->next;
free(head->prev);
head->prev = NULL;
}else if(strcmp(tail->nama,vnama)==0){
tail = tail->prev;
free(tail->next);
tail->next = NULL;
}else{
data *node = head->next;
while(node!=tail && strcmp(node->nama, vnama)!=0){
node = node->next;
}
if(strcmp(node->nama, vnama)==0){
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);
node = NULL;
}else{
printf("There is no data\n");
}
}
}else{
printf("There is no data\n");
}
}

void popall(){
while(head!=NULL){
if(head==tail){
free(head);
head =tail = NULL;
}else{
data *curr=head;
head=head->next;
free(curr);
}
}
}

void edit(char vnama[100], int vqty){
if(head != NULL){
data *node = head;
while(node!=NULL && strcmp(node->nama, vnama)!=0){
node = node->next;
}
if(strcmp(node->nama, vnama)==0){
node->qty = vqty;
}else{
printf("There is no data\n");
}
}else{
printf("There is no data\n");
}
}

void viewALL(){
int total=0;
if(head==NULL){
printf("No Items to Checkout\n");
}else{
data *node = head;
while(node!=NULL){
printf("%-15s %-3d Rp.%-5d Rp.%d\n", node->nama, node->qty, node->harga, node->qty*node->harga);
total+=node->qty*node->harga;
node = node->next;
}
printf ("\nHere is Your Total Rp.%d\n", total);
}
}

void viewcart(){
if(head==NULL){
printf("\n");
}else{
data *node = head;
while(node!=NULL){
printf("%-15s %-3d\n", node->nama, node->qty);
node = node->next;
}
}
}

int main(){
int menu;
char nama[100];
int qty, co;
int harga;
srand(time(0));
do{
printf("\nDREAMMERS MARKET\n");
printf("^^^^^^^^^^^^^^^^\n");

printf("\nCart:\n");
viewcart();

printf("\nMenu :\n");
printf("1. Add goods\n");
printf("2. Change qty\n");
printf("3. Delete goods\n");
printf("4. Checkout\n");

printf(">> Input choice : ");
scanf("%d", &menu);getchar();
printf("\n");
switch(menu){
case 1:

printf("Masukan Nama Barang: ");
scanf("%[^\n]", &nama);

printf("Masukan Qty[1-100]: ");
scanf("%d", &qty);

harga = (rand()%100)*1000;

push(nama,qty,harga);

printf("--- Add goods Success ---\n");
break;

case 2:
printf("Masukkan nama barang(pastikan namanya sama saat input): ");
scanf("%[^\n]", &nama);
printf("Masukan Qty[1-100]: ");
scanf("%d", &qty);
edit(nama,qty);
printf("--- Change goods qty Success ---\n");
break;

case 3:
printf("Masukkan nama barang(pastikan namanya sama saat input): ");
scanf("%[^\n]", &nama);
pop(nama);
printf("--- Delete goods Success ---\n");
break;

case 4:
printf("Here is your bill\n\n");
viewALL();
printf("\nDo you wish to pay?\n");
printf("1. Yes\n2. No\n");
printf(">> Input choice : ");
scanf("%d", &co);
if(co == 1){
printf("Kindness is free\n");
popall();
break;
}else{
printf("It's okay kindness is free\n");
popall();
break;
}

}

}while(menu!=4);

}

HASHING & BINARY TREE

noreply@blogger.com (Felicia Angelina) — Tue, 10 Mar 2020 05:16:00 -0700

Hashing

Hashing merupakan Teknik untuk menyimpan dan mengambil keys dengan cara yang cepat.

Hashing menyimpan keysnya di array yang bernama hash table dan menggunakan function yang sudah ditentukan yaitu hash function.

Hashing terdapat 5 jenis:

Mid-square
Division (paling sering digunakan)
Folding
Digit Extraction
Rotating Hash

Mid square caranya adalah dengan mempangkatkan angka yang ingin disimpan yang kemudian akan diambil angka tengahnya.

Divison caranya adalah dengan memodulus angka yang ingin disimpan dengan ukuran dari size table yang diberikan/digunakan.

Folding caranya adalah dengan membagi setiap angka menjadi 2 bagian yang kemudian akan saling ditambahkan.

Digit extraction caranya adalah mengambil digit pada letak-letak terntetu yang sudah ditentukan sebelumnya dan angka tersebut kemudian akan menjadi hash addressnya.

Rotating hash caranya adalah menggunakan mid-square atau division terlebih dahulu buat dapet hash adressnya dan kemudian dibalik angkanya.

Hashing pada saat ini digunakan dalam blockchain, terutama dalam cryptocurrency. Hashing sangatlah penting dalam pengaturannya. Hash bagaikan backbone dalam cryptocurrency.

Hash membantu dalam menyimpan data yang sangat banyak dalam blockchain.

Collision

Collasion terjadi ketika ada string yang memiliki hash key yang sama contohnya seperti float dan floor dimana sama-sama berawalan f.

Collison bisa diatasi dengan 2 cara:

Linear probing
Chaining

Linear probing adalah mencari tempat kosong selanjutnya dan menaruhnya disana. Namun, cara ini sangatlah tidak efisien karena ketika string tersebut ingin dicari looping yang dilakukan akan banyak.

Chaining adalah meletakkan string tersebut sebagai linked list jadi apa bila floor terletak di hash key 5 maka ia linked list ke float jadi tidak membuang-buang waktu untuk mencarinya.

Tree

Tree merupakan struktur yang menunjukan hirarki antar non-linear data.

Node dalam tree tidak perlu disimpan secara berurut, ia dapat disimpan secara asal dan kemudian dihubungkan dengan pointer.

Konsep tree

Node yang paling diatas disebut root.
Line yang menghubungankan antara parent dan child disebut edge.
Node yang tidak memiliki children disebut leaf.
Node yang memiliki parent yang sama disebut sibling.
Degree of node mereupakan jumlah dari sub tree sebuah node.
Height/Depth merupakan maksimum degree dalam sebuah tree.
Jika ada line yang menghubungkan antara p dan q, maka p disebut ancestor dari q, dan q adalah descendant dari p.

Binary tree

Konsep binary tree

Binary tree merupakan struktur data tree dimana setiap node maksimal memiliki 2 node.
Setiap 2 children tersebut biasanya dibedakan sebagai left child atau right child.
Node yang tidak memiliki children disebut leaf.

Tipe binary tree

Perfect binary tree
Complete binary tree
Skewed binary tree
Balanced binary tree

Perfect binary tree adalah dimana setiap level mempunyai height/depth yang sama.

Skewed binary tree merupakan tree yang setiap nodenya maksimal memiliki 1 child.

Balanced binary tree merupakan tree dimana leaf yang satu tidak boleh lebih jauh levelnya dari leaf yang lain jadi harus seimbang.

Pada coding diberikut akan terbentuk seperti ini

1 <-- root

/ \

2 3

Linked list

noreply@blogger.com (Felicia Angelina) — Tue, 3 Mar 2020 04:43:00 -0800

Pertemuan GSLC

array dan linked list bisa dibilang sama namun tak sama.
perbedaan array dan linked list adalah
array

kumupulan dari data
menyimpan datanya di memory yang beruurtan
bisa mengakses data mana saja secara langsung

linked list

kumpulan dari node
menyimpan node di memory yang secara acak
hanya bisa diakses secara berurutan

array dan linked list memiliki kelebihan dan kekurangan tersendiri.
contohnya adalah
kelebihan array

mudah digunakan
lebih cepat megakses data mana saja

kekurangan array

ukuran tidak dapat dirubah sehingga terkadang memakan banyak memory

kelebihan linked list

penggunaan memory sesuai banyaknya data yang ada sehingga irit
sistemnya fleksibel

kekurangan linked list

pengerjaan lebih komples

linked list terdapat banyak macam, beberapa contohnya adalah

circular linked list
double linked list

circular linked list dalam permasalahan yang berhubungan dengan head dan tail memang lebih cepat diselesaikan dan juga ia bisa ke node manapun.

namun apa bila tidak di coding dengan benar dapat terjadi infinite loop dan juga karena ia hanya satu arah, ia tidak bisa mundur sehingga jika ia harus mengelilingi list terlebih dahulu untuk mencapai sebuah node jika ia terletak disebelumnya.

Pertemuan ketiga

pada pertemuan ini saya mempelajari cara kerja linked list dalam bentuk codingnya dan double linked list secara singkat.

linked list cara kerjanya adalah dengan cara menyimpan alamat satu sama lain bukan dengan menyimpan isi dari alamat tersebut.

setiap alamat akan mempunyai hubungan dengan alamat berikutnya sehingga mereka akan saling menyambung
seperti di atas cara kerjanya data pertama jika di next maka dia akan ke data b karena setelah data a itu tersimpan alamat dari data b.

head akan selalu ada pada data pertama sedangkan pada ujung akan bernama tail dan dia tidak akan menunjuk kemana-mana maka panak tersebut dituliskan NULL.

pada linked list biasa dia tidak bisa bergerak mundur maka ia akan selalu bergerak dari head ke tail.

seperti berikut adalah codingnya

coding di atas adalah untuk memasukan data kedalam linked list

sedangkan dibawah ini adalah cara menghapus data paling atas dari linked list

double hampir sama dengan linked list biasa namun bedanya dia bisa mundur
cara kerjanya seperti di bawah ini