Summary AVL Tree

AVL Tree

AVL Tree merupakan salah satu jenis dari BST (Binary Search Tree). Di mana tujuan dari BST (Binary Search Tree) itu sendiri adalah untuk mempersingkat waktu pencarian data. Tapi, bagaimana jika setiap node-node yang dimasukkan ke dalam BST itu hanya menumpuk di bagian sebelah kanan root ataupun bagian sebelah kiri root? Tree menjadi tidak seimbang dan akan memakan banyak waktu ketika kita ingin mencari data dari suatu node yang ada di kanan bawah ataupun kiri bawah. Konsep seperti itu tidak berbeda dengan Konsep Linked List, bukan? Inilah worst-case yang mungkin kita dapat dari BST (Binary Search Tree). Maka dari itu, dibuatlah AVL Tree dengan tujuan untuk menyeimbangkan antara anak dari sebelah kanan root dengan anak yang berada di sebelah kiri root. AVL Tree ini ditemukan oleh G.M. Adelson Veleskii dan E.M. Landis.

AVL Tree sendiri merupakan Binary Search Tree (BST) yang hanya memiliki perbedaan height (tinggi) 1 antara subtree kiri dan subtree kanan. Dengan adanya penyeimbangan ini, pencarian data akan semakin cepat dilakukan. Dalam menyeimbangkan node, dikenal istilah yang bernama Balance Factor sebagai penanda yang jika melebihi aturan AVL Tree akan dilakukan Rotation.

AVL Tree mempunyai aturan yang tidak boleh dilanggar di mana Balance Factor harus mempunyai nilai -1, 0, dan 1. Tidak boleh kurang atau lebih dari nilai tersebut. Jika lebih, harus diseimbangkan kembali dengan melakukan Rotation. Balance Factor dapat ditentukan dengan:

                     Balance Factor = Height of Left Subtree - Height of Right Subtree

Berikut adalah contoh dari AVL Tree. Kita dapat melihat jika Balance Factor nya tidak melebihi -1, 0, dan 1 yang artinya Tree ini merupakan AVL Tree.

Dari gambar tersebut, Tree memiliki height = 4 dan balance factor yang ada tidak melebihi atau kurang dari -1, 0, dan 1. Height ditentukan dengan berapa jumlah level anak ke bawah yang dimiliki oleh Tree dihitung dari root (level 1). Balance factor ditentukan dari hasil selisih antara height anak kiri dengan height anak kanan. Ambil contoh node (14), mempunyai height 2 dan balance factor 1. Node (14) memiliki 1 anak kiri dengan height 1 dan 1 anak kanan dengan height 2. Hasil pengurangannya adalah 1. Itulah balance factor.

INSERTION : AVL TREE

Terdapat 4 kasus penambahan node baru (insert) yang seringkali menyebabkan Tree menjadi tidak seimbang, di antaranya:

1.  Left-Left (LL)

Node terdalam terletak pada subtree bagian kiri dari anak kiri T (node yang harus diseimbangkan).

2. Right-Right (RR)

Node terdalam terletak pada subtree bagian kanan dari anak kanan T (node yang harus diseimbangkan).

3. Right-Left (RL)

Node terdalam terletak pada subtree bagian kanan dari anak kiri T (node yang harus diseimbangkan).

4. Left-Right (LR)

Node terdalam terletak pada subtree bagian kiri dari anak kanan T (node yang harus diseimbangkan).

Penyelesaian dari kasus ini adalah dengan melakukan Rotation. Ada 2 cara untuk melakukan Rotation, yaitu:

a. Single Rotation

Single rotation dilakukan bila node dari Tree searah ke arah kiri (Left-Left) atau searah ke arah kanan (Right-Right) yang menyebabkan terjadinya ketidakseimbangan. Kasus 1 dan kasus 2 dapat diselesaikan dengan Single Rotation ini. Pada kasus 1, akan dilakukan right rotate. Pada kasus 2 akan dilakukan left rotate.

Berikut contoh dari Single Rotation.

Pada kasus di atas, penambahan node (12) menyebabkan tree menjadi tidak seimbang. Pada gambar, terjadi kasus 1 (left-left) di mana root (30) memiliki balance factor 2. Hal ini melanggar peraturan dari AVL Tree dengan balance factor yang melebihi 1. Untuk menyelesaikan kasus ini, dilakukan single rotation. Kasus left-left ini dapat diselesaikan dengan melakukan right rotate. Node (22) akan menjadi root, kemudian node (15) akan menjadi anak kiri dari node (22) dan node (30) menjadi anak kanan node (22).

b. Double Rotation

Double rotation dilakukan bila node dari Tree mempunyai anak kanan dan anak tersebut mempunyai anak kiri (Right-Left) atau node dari tree mempunyai anak kiri dan anak tersebut mempunyai anak kanan (Left-Right) sehingga terjadi ketidakseimbangan. Kasus 3 dan kasus 4 dapat diselesaikan dengan Double Rotation. Di mana ada 2x rotasi yang dilakukan. 

Pada kasus 3, langkah pertama adalah dengan melakukan right rotate kemudian dilanjutkan dengan left rotate. Pada kasus 4, langkah pertama adalah dengan melakukan left rotate kemudian diikuti dengan right rotate.

Berikut contoh dari Double Rotation.

Pada kasus di atas, terjadi ketidakseimbangan pada tree. Kasus yang terjadi adalah left-right. Diperlukan double rotation untuk menyeimbangkannya. Langkah pertama adalah dengan melakukan left rotate pada node (22) dan node (27) menjadi seperti pada gambar di atas. Setelah itu, dilakukan 1x rotasi lagi karena masih belum seimbang. Dilakukan right rotate dengan menjadikan node (27) menjadi root, node (22) menjadi anak kiri dari node (27), dan node (30) menjadi anak kanan dari node (27).

DELETION : AVL TREE

Terdapat 2 kasus yang biasanya terjadi ketika melakukan penghapusan (delete) node, di antaranya:

1. Jika node yang berada di posisi paling bawah (leaf), node akan dapat langsung dihapus.

2. Jika node yang akan dihapus memiliki anak, harus dicek kembali apakah setelah penghapusan node tree akan menjadi tidak seimbang atau tidak. Pengecekan penyeimbangan node ini sama seperti pada saat Insertion.  Jika tree menjadi tidak seimbang, maka harus diseimbangkan lagi.

Berikut contoh dari Deletion.

Pada gambar di atas, node (30) akan dihapus. Node (30) ini merupakan leaf dari tree sehingga pengoperasian deletion dapat langsung dilakukan. Namun setelah operasi deletion dilakukan, terjadi ketidakseimbangan pada tree. Node (20) memiliki balance factor 2 di mana hal ini melanggar aturan dari AVL Tree itu sendiri. Tree harus diseimbangkan. Pada kasus di atas, terjadi kasus left-left di mana kita harus melakukan rotation untuk menyeimbangkannya kembali. Kita lakukan right rotate dengan menjadikan node (10) menjadi root dengan anak kanan node (20) dan anak kiri node (5). Ternyata balance factor dari node (10) sudah memenuhi syarat AVL Tree yaitu -1. Maka, tree sudah seimbang.

Summary Hashing Table dan Implementasi Hash pada Blockchain

HASHING TABLE

Pada post kali ini saya akan membahas mengenai implementasi Hash Table dalam pembuatan Blockchain. Sebelum itu kita harus tau apa itu Hash Table yang di dalamnya terdapat Hash Function dan Collision. Saya akan membahas secara lengkap mengenai semuanya itu pada blog kali ini.

Hash Table adalah sebuah struktur data sebagai tempat kita menyimpan data. Hash Table terdiri atas tabel dan fungsi yang bertujuan memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Tujuan dari Hash Table sendiri adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Namun pada kenyataannya, sering kali ditemukan angka hash yang bertabrakan (collision) record-recordnya. Maka, untuk mengatasi hal ini diterapkan Kebijakan Resolusi Bentrokan (Collision Resolution Policy). Kebijakan ini berguna untuk menentukan lokasi record dalam tabel.

Operasi pada Hash Table:

·       Insert  =  Penambahan data dalam tabel

int hashtbl_insert(HASHTBL *hashtbl, const char *key, void

*data)

{

struct hashnode_s *node;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) {

node->data=data;

return 0;

}

node=node->next;

}

//Jika tidak menemukan key yang sama

if(!(node=malloc(sizeof(struct hashnode_s)))) return -1;

if(!(node->key=mystrdup(key))) {

free(node);

return -1;

}

node->data=data;

node->next=hashtbl->nodes[hash];

hashtbl->nodes[hash]=node;

return 0;

}

·        Find    =  Pencarian data yang berhubungan dengan key

void *hashtbl_get(HASHTBL *hashtbl, const char *key)

{

struct hashnode_s *node;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) return node->data;

node=node->next;

}

return NULL;

}

·    Delete/remove  =  Penghapusan data setelah diberi key, kemudian menemukan nilai yang berhubungan dengan key dan setelahnya akan dihapus.

int hashtbl_remove(HASHTBL *hashtbl, const char *key)

{

struct hashnode_s *node, *prevnode=NULL;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) {

free(node->key);

if(prevnode) prevnode->next=node->next;

else hashtbl->nodes[hash]=node->next;

free(node);

return 0;

}

prevnode=node;

node=node->next;

}

return -1;

}

Hashing Function

Teknik-teknik pada Hash Function:

·         Division :

String yang kita input akan dimoduluskan dengan sejumlah memori agar nilai (value) yang didapatkan dari hasil modulus kemudian dijadikan indeks tempat nilai itu disimpan.

·         Mid-Square :

Setiap nilai yang kita terima akan dipangkatkan dua. Jika memori hash kita ada 100, memori itu terdiri dari 0-99 maka angka yang menjadi hash kita adalah 2 digit dari nilai tengahnya.

·         Folding      :

Memecahkan nilai dari hash tersebut menjadi beberapa bagian.

Collision (Tabrakan)

Keterbatasan table hash menyebabkan terdapat 2 angka yang jika dimasukkan ke dalam fungsi hash menghasilkan nilai yang sama. Peristiwa ini disebut dengan Collision.

Misalkan kita ingin menginput string floor dan float (hash-key : 5) dengan huruf awal f. Di sini terdapat 2 hash index yang sama. Jika bentrok ini dinamakan collision. Kejadian ini harus bisa ditangani.

Cara penanganan collision:

·        Collision Resolution Open Addressing

Menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori di luar array yang digunakan. Cara ini mencari alamat lain apabila alamat yang akan dituju sudah terisi data. Ada 3 cara untuk mencari alamat lain tersebut:

1.      Linear Probing

Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.

2.      Quadratic Probing

Penanganannya hampir sama dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … ).

3.      Double Hashing

Alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi.

·        Collision Resolution Chaining

Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Kerugian:

-          Overhead pada memory tinggi jika jumlah entry sedikit.

Keunggulan dibandingkan open addressing:

-          Proses insert dan remove lebih sederhana.

-          Ukuran Array bukan batasan (tetapi harus tetap meminimalisir collision.

IMPLEMENTASI HASHING PADA BLOCKCHAIN

Sebelum masuk lebih dalam kita harus tahu apa itu blockchain. Blockchain adalah catatan transaksi digital berdasarkan strukturnya, di mana catatan individu, yang disebut blok, dihubungkan bersama dalam satu daftar, yang disebut chain (rantai). Blockchain digunakan untuk mencatat transaksi yang dilakukan dengan cryptocurrency, seperti Bitcoin dan memiliki banyak aplikasi lain.

Pada era sekarang ini, kriptografi menjadi peran penting dalam jaringan blockchain yang terus berkembang. Salah satunya adalah proses perhitungan sebuah data secara konkret dan unik. Metode ini dikenal dengan Hash. Kode unik yang kita temukan dalam Blockchain itu menggunakan metode Hash.

Nilai berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik untuk mencegahnya ialah dengan pemberian kode unik.

Data tersebut akan aman dan pastinya menjadi orisinalitas data dari orang lain. Hanya orang yang terkait berhak dan bisa masuk ke akses data tersebut. Saat ini beragam proses pengamanan data, mulai dari sidik jari, sidik mata, dan di sistem Blockchain menggunakan kode unik (Hash).

Tak hanya itu saja, Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri. Ini yang tidak didapatkan pada jaringan biasa. Selain itu, setiap data dokumen dengan panjang berapa pun akan menghasilkan nilai hash yang punya nilai panjang berbeda tergantung spesifikasi Hash yang digunakan.

Sejumlah hash yang digunakan saat ini karena fungsi dan keamanannya beragam dan memiliki kemampuan transaksi data yang cepat :

1.     SHA256

SHA256 adalah hash pertama sekali muncul dan digunakan di jaringan blockchain publik. Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai Hash. Pengguna ini sudah mulai dicetus sejak tahun 2001 oleh NIST (National Institute of Standard and Technology).

SHA256 merupakan generasi kedua dari hash jenis Sha, penggunaan angka 256 karena dasar data yang dihasilkan adalah 256 bit. SHA26 sendiri banyak digunakan oleh berbagai sistem blockchain lainnya karena punya kapasitas mengirim yang relatif kecil dan cepat. Terlebih lagi untuk proses transaksi besar.

2.      RIPEMD160 (Race Integrity Primitive Evaluation Message Digest)

Konsep dari algoritma dari RIPEMD160 dikembangkan oleh MD4. Jumlah data transaksi yang dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.

Tentu saja hal ini membuktikan RIPEMD lebih cepat dan bertenaga, sehingga proses pending data berkurang. Peran utama yang diemban oleh RIPEMD160 adalah dengan membuat alamat Bitcoin yang diakumulasi berdasarkan pada kunci publik.

3.     Beragam Hash pada Monero
      Pada Monero, penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Blake, Grostl, JH, dan Skein pada CryptoNote. Konsep dari Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous.

Monero menilai bahwa perlu adanya keamanan khusus dan beragam pada Hash. Inilah yang menjadi dasar lahirnya konsep CryptoNote. Pengguna yang mengirimkan transaksi atau data tidak dapat diidentifikasi oleh publik karena ada beberapa kunci tersebut. 

 

Demikian penjelasan yang dapat saya sampaikan mengenai Hash Table, Hash Function, Collision serta pengimplementasian dan peran Hash pada jaringan Blokchain. Semoga bermanfaat.

Summary Linked List, Stack & Queue

LINKED LIST

Merupakan struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. 

Dalam Linked List biasanya terdapat istilah Head dan Tail.

• Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

• Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Linked List sendiri terdiri dari beberapa macam, yaitu:

1. Single Linked List -> Linked List yang hanya mempunyai 1 variabel pointer saja.
2. Double Linked List -> Linked List yang memiliki 2 variabel pointer yang di mana                                        salah satu pointer nya menunjuk ke node selanjutnya dan                                             pointer satunya menunjuk ke node sebelumnya                        
3. Circular Single Linked List -> Linked List yang di mana Tail menunjuk ke Head                                                         yang menyebabkan tidak ada pointer yang menuju                                                        NULL.
4. Multiple Linked List -> Linked List yang memiliki lebih dari 2 variabel pointer

Sekarang kita akan membahas mengenai Double Linked List dan Circular Single Linked List. Single Linked List sudah dibahas pada post sebelumnya.

A. Circular Single Linked List  

Seperti dijelaskan sebelumnya, Circular Single Linked List adalah suatu linked list yang tail (node terakhir) nya menunjuk ke head (node pertama). Jadi, tak ada pointer yang menuju NULL.

 

B. Double/Two Way Linked List

Double Linked List adalah suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

Double/Two Way Linked List ini dapat mengatasi kelemahan-kelemahan yang ada pada Single Linked List

Operasi pada Double Linked List :

a. Insert First -> Penyisipan pada awal sehingga pointer head akan berpindah ke elemen baru

b. Insert Last -> Penyisipan pada akhir sehingga pointer tail akan berpindah ke  elemen baru

d. Delete First ->  Penghapusan di awal list, pointer head akan berpindah ke node                                                               selanjutnya,sementara node awal akan didealokasi.

e. Delete Last -> Penghapusan di akhir list, pointer tail akan berpindah ke node sebelumnya                                            sementara node akhir akan didealokasi.

f. Delete Node -> Penghapusan node dengan data tertentu.

STACK & QUEUE

STACK

Sesuai dengan artinya, stack seolah-olah seperti menumpukkan suatu data di atas data lainnya.

Stack sendiri bersifat LIFO (Last In First Out) di mana data yang terakhir masuk ke dalam stack akan menjadi data yang keluar terlebih dahulu dari stack.

Stack sendiri dapat diimplementasikan dengan block chain atau linked list.

 

Kita mengenal 5 operasi dasar Stack, yaitu:

1. Push       -  Menambahkan item pada bagian paling atas dari stack.

2. Pop        -  Mengambil item dari tumpukan paling atas.

3. Clear      - Mengosongkan stack.

4. IsEmpty - Fungsi yang digunakan untuk mengecek apakah stack sudah kosong.

5. IsFull      - Fungsi yang digunakan untuk mengecek apakah stack sudah full/terisi.

INFIX, POSTFIX & PREFIX

Infix  =  Operator dituliskan di antara operand

Postfix  =  Operator dituliskan setelah operand

Prefix  =  Operator dituliskan sebelum operand

Contoh :

((1 + 3) / (100 * 5) ^ 30)

Prefix : ^ + 1 3 / * 100 5 30

Postfix : 1 3 + / 100 5 + * 30 ^

Perlu diketahui, komputer tak mampu membaca tanda kurung ( ) pada operasi aritmatika. Maka, dibuatlah 3fix (Infix, Prefix, Postfix) yang membuat komputer dapat melakukan operasi aritmatika dengan benar.

Depth Search First (DFS) menggunakan metode Stack.

QUEUE

Disebut juga antrian. Queue adalah sekumpulan data yang penambahan elemennya hanya dapat dilakukan di salah satu ujung depan (front) atau ujung belakang (rear).

Jika pada Stack menggunakan prinsip LIFO (Last In First Out) maka pada Queue menggunakan prinsip FIFO (First In First Out). Di mana data yang pertama kali masuk akan keluar pertama kali.

Kita mengenal 3 operasi dasar queue:

1. Push  =  Menambah item dari bagian belakang queue.

2. Pop  =  Menghapus item dari bagian depan (front) queue.

3. Front  =  Menyatakan item paling depan dari suatu queue. (Top)

Front dapat dikenal juga sebagai Peek (Stack).

Queue dapat memasukkan data dari array terakhir dan dapat melakukan delete array di awal. Namun, ketika array sudah mencapai batas kita tak bisa menambah data lagi padahal array awal masih kosong. Maka dari itu, terdapat Circular Queue yang dapat mengatasi masalah ini dengan dapat berulang terus-menerus.

DEQUES (Cara membaca : Deck/Dequeue)

Dapat mengacak-acak (add atau delete) data semau user dari array manapun.

• Input Restricted Deque - Push (Input) hanya boleh/dibatasi 1x.
• Output Restricted Deque - Output nya dibatasi hanya 1.

Breadth First Search (BFS) menggunakan metode Queue.

 

Summary Pointer, Array & Linked List

DATA STRUCTURE

• Pointer & Array
• Linked List

Data Structure : Bagaimana cara mengolah data yang bergerak secara efektif dan efisien. 

POINTER & ARRAY

• POINTER

Sebuah variabel yang bertugas untuk menunjuk. 

Setiap variabel pada C mempunyai sebuah nilai dan juga lokasi / alamat memori dan setiap compiler memiliki cara akses memori yang berbeda. Ketika variabel dideklarasi, suatu blok spesifik memori pada komputer akan dialokasikan untuk mempertahankan suatu niali(value). Size dari Integer dapat berbeda dari satu sistem ke sistem lainnya. Pada sistem 32 bit, suatu variabel Integer dialokasikan 4 bytes. Jika pada sistem 16 bit, dialokasikan 2 bytes.

Terdapat 2 operator penting pointer :

1. & -> the address operator(menyatakan posisi)

2. * -> the dereferencing operator(menyatakan isinya)

Pointer digunakan untuk membuat struktur data yang kompleks, yaitu trees, linked list, linked stack, linked queue, and graphs. Pointer menggunakan Dynamic Memory Allocation. Contoh : Belanja di online shop dan pesan makanan online.

• ARRAY

Mengapa indeks array dimulai dari nol[0]?

Jika indeks mulai dari 1[1] maka memori yang dipakai tidak akan efisien.

Array merupakan sekumpulan dari elemen yang memiliki tipe data yang sama. Antara satu variabel dengan variabel lain di dalamnya dibedakan berdasarkan Subscript. Di mana, Subscript merupakan suatu bilangan dalam kurung siku [].

Contoh penggunaan Array : 

int Arr[10]

Artinya, array mempunyai indeks dari [0-9] yang merupakan sekumpulan data bertipe data integer.

• LINKED LIST

Linked List -> Harus terdapat pointer next yang berhubungan.

                   -> Posisinya random (yang menunjukkan di mana posisinya adalah pointer next).

Terdapat Single Linked List dan Double Linked List.

1. Single Linked List -> Tak dapat berbalik (hanya 1 arah). Maka, dibuat prev. agar dapat berbalik di                                         mana salah satu menunjuk ke NULL dan satu lagi menunjuk ke yang lain.

2. Double Linked List -> Linked list dengan node yang memiliki data dan dua buah reference link                                               (biasanya disebut next dan prev) yang menunjuk ke node sebelum dan node                                           sesudahnya.

Linked List Vs Array

Linked List -> Dynamic Memory Allocation (Malloc : Mengembalikan void*, maka membutuhkan                                                                              typecasting).

Linked List sangatlah berguna, karena kita tak bisa membatasi jumlah user.