Rangkuman Binary Search Tree

Binary Search Tree adalah salah satu cara penyimpanan data dengan menggunakan metode tree/pohon yang dimana setiap node maksimal hanya boleh memiliki 2 anak node. dalam binary search tree, terdapat beberapa aturan yaitu :
1. nilai node anak bagian kiri selalu lebih kecil dari node parent
2. nilai node anak bagian kanan selalu lebih besar dari node parent
3.bagian kiri atau kanan node sebuah anak bisa menjadi sebuah node parent dimana BST memiliki sifat Rekursif
4. Setiap node memiliki nilai value dan tidak ada node yang bernilai sama/ double

Ada 3 operasi yang bisa dilakukan dalam BST yaitu :
 A. Searching Data: mencari value x di dalam BST ( Find(x))

Terdapat 3 cara untuk melakukan searching data dalam BST yaitu :
1. Pre-Order : dimana print data terlebih dahulu lalu menelusuri node dari kiri ke kanan
2. InOrder : menelusuri node dari kiri lalu print data lalu kembali menelusuri node di kanan
3. Post-Order : menelusuri node dari kiri ke kanan lalu print data.

B. Insert Data : memasukan value baru x ke dalam BST (Insert(x))

Langkah-langkah yang dilakukan untuk insert data adalah :
1. dimulai dari node root
2. jika x lebih kecil dari node parent maka akan dimasukan ke node anak bagian kiri secara berulang (rekursif)
3. jika x lebih besar dari node parent maka akan dimasukkan ke node anak bagian kanan secara berulang (rekursif)
4. Dilakukan pengulangan sampai terdapat node yang kosong untuk memasukan value x

C. Delete Data : Menghapus value x dari BST (Delete(x))
terdapat 3 kasus dalam delete data yaitu :
1. jika value yang dihapus adalah leaf maka langsung dihapus
2. jika value yang dihapus hanya memiliki 1 node anak maka hapus nodenya dan node anaknya digabung dengan node parentnya
3. jika value memiliki 2 node anak maka ada 2 cara dimana bisa mencari left node paling terakhir ( leaf) atau bagian kanan node menggantikan menjadi parent node

Rangkuman Hashing Table dan Binary Tree

Sebelum kita masuk dalam Hashing Table dan Binary Tree, saya akan menjelaskan pengertian dan cara kerja double pointer. Double pointer adalah pointer yang menunjuk kepada sebuah pointer yang lain. Dimana, pointer pertama menunjuk pada lokasi alamat sebuah variabel dan pointer kedua menunjukkan kepada alamat pada pointer pertama. Cara mendeklarasi sebuah double pointer adalah:

int **variabel;

Hash adalah mengubah input dengan panjang berapapun dan memberikan output dengan panjang yang tetap. Output dengan panjang yang tetap biasanya menggunakan algoritma seperti SHA-256 yang berarti hasil output panjangnya tetap yaitu sepanjang 256-bit. Fungsi hash adalah menjaga keamanan sebuah inputan agar hasilnya tidak bisa dibaca orang yang tidak memiliki otoritas.

Hash Table atau yang bisa disebut dengan Pohon Merkle dimana setiap simpul non daun adalah hasil hash dari nilai simpul anaknya. node daun adalah node terendah dari sebuah pohon, root node adalah node teratas dari sebuah node dan dibawah root node adalah node anak.

Blockchain adalah daftar tertaut yang berisi data dari pointer hash yang menunjuk ke blok sebelumnya dimana cara kerja seperti double pointer yang sudah dijelaskan diatas. pointer hash bukan hanya berisi alamat dari blok tersebut tetapi juga berisi hash didalam blok tersebut. Hal ini menyebabkan jika ada perubahan dalam sebuah blok maka blok lain akan berubah juga.Apakah hashing table terpakai dalam blockchain? tentu saja, karena dalam sebuah blok berisi ribuan transaksi dan tidak efisien jika setiap data dalam blok disimpan dalam seri. maka menggunakan pohon merkle dalam blockchain mengurangi waktu yang diperlukan untuk mengetahui apakah sebuah transaksi berada dalam sebuah blok dimana kita bisa track dari transaksi di dalam sebuah blok dengan mengikuti jejak hash yang akan mengarah ke data.

Binary tree adalah tree dalam data structure dimana sebuah node memiliki anak yang dimana node anak maksimal memiliki 2 node yaitu anak kiri dan anak kanan.fungsi binary tree adalah sebagai akses node bedasarkan sebuah value dan representasi data dengan struktur bifurkasi yang relevan

Rangkuman Linked List

Dalam pelajaran kelas CB01 Data Structure hari ini, kita belajar mengenai Single Linked List.
Single Linked List adalah banyaknya data yang saling berhubungan satu dengan yang lain dimana setiap node memiliki alamat node yang lain dan bersifat satu arah dimana node hanya mengetahui alamat node yang lain, bukan alamat node yang ditanya. Kita bisa meng-analogikan seperti aku menanyakan kepada John alamat Bill dan John yang mengetahui alamat Bill bisa memberitahukan kita alamat Bill tetapi John tidak tahu alamat kita. Jika dalam analogi ini JOhn mengetahui alamat aku maka itu bisa disebut dengan Double Linked List.

   Single Linked List memiliki beberapa bagian :
1. Head = bagian awal dari rantai Linked List.
2. Tail = bagian akhir dari rantai Linked List.
3. NULL = bagiam setelah Tail yang bernilai NULL/0

   Dalam mengerjakan Single Linked List, ada beberapa metode dalam mengupdate sebuah Linked List.ada beberapa seperti :
1. Insert/Push : kata-kata ini biasanya dipakai untuk menambahkan sebuah node yang belum berada dalam sebuah linked list ke dalam rantai linked list.
2. Delete/Pop: kegunaannya adalah untuk menghapus node yang berada dalam sebuah rantai Linked List

   Ada beberapa metode yang bisa dilakukan dalam melakukan insert/ push maupun delete/pop seperti:
a. Depan/Head : menambah/menghapus node kedepan sebuah rangkai Linked List.
b. Belakang/Tail : menambah/menghapus node ke bagian paling belakang sebuah rantai Linked List.
c. Mid : menambah/menghapus node yang berada di tengah Tail dan Head.

Contoh code untuk Linked List:

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

struct data{
int value;
struct data *next;
}*head,*tail,*curr;

void insertFront(int x){
struct data *node = (struct data*)malloc(sizeof(struct data));
node->value = x;

if(head == NULL){
head = tail = node;
tail->next;
}
else{
node->next = head;
head = node;
}
}

void insertBack(int x){
struct data *node = (struct data*)malloc(sizeof(struct data));
node->value = x;

if(tail == NULL){
head = tail = node;
tail->next;
}
else{
tail->next=node;
tail=node;
tail->next=NULL;
}
}

void delHead(){
curr = head;
head = curr->next;
free(curr);
}

void delTail(){
curr = head;
while(curr!=NULL){
if(curr->next==tail) break;
else curr = curr->next;
}
tail = curr;
free(tail->next);
tail->next = NULL;
}
void insertBefore(int x, int p){
struct data *node = (struct data*)malloc(sizeof(struct data));
node->value = x;
curr=head;
while(curr->next->value!=p) curr=curr->next;
node->next = curr->next;
curr->next = node;
}

void view(){
curr=head;
while(curr!=NULL){
printf("%d",curr->value);
if(curr->next!=NULL) printf(" ");
else printf("\n");
curr = curr->next;
}
}

int main (){
insertFront(5);
insertFront(6);
insertFront(1);
insertBack(9);
insertBack(7);
view();
insertBefore(3,6);
view();
return 0;
}