Data Structure(Hash Table ,Tree, &Binary Tree)

Hashing Table, Tree,& Binary

Hashing :

      Hashing adalah suatu teknik dalam pemrograman untuk menyimpan dan mengambil data itu kembali secara cepat menggunakan keys atau suatu kunci pengenal suatu data yang disimpan. Dalam hashing menggunakan index untuk mengambil data / item yang diinginkan dalam suatu database karena lebih cepat mendapatkan datanya dikarenakan menggunakan keys yang merupakan value yang lebih kecil daripada data aslinya.

      Dalam data linier (array) yang menggunakan keys pada setiap datanya disebut Hash Table sedangkan function yang menggunakan hashing disebut Hash Function. Dalam penggunaannya bisa dikatakan bahwa Hashing merupakan gabungan dari array dan Linked list.

Hash Function :

      Hash Function memiliki beberapa methods :

• Mid-square : Dengan mengkuadratkan atau pow() key yang didapat lalu mengekstrak r bits tengah dari hasil sebelumya.

• Division : Dimana paling umum digunakan dan lebih sederhana pemrogramanya. Yaitu dengan dari key yang didapat kita menjumlahkan valuenya lalu memoduluskannya dengan size memory atau batas array penyimpanan yang digunakan.

• Folding : Membagi key value menjadi beberapa bagian lalu menjumlahkan value yang sudah terbagi itu dan kemudian mengambil dua digit terakhir dari hasil penjumlahan bagian-bagian value tersebut.

• Digit Extraction : Digit yang diambil dianggap sebagai hash address dan mengekstrak beberapa digit dari address tersebut dan menjadikannya hash codenya. 

• Rotating Hash : Method yang menggunakan method lainnya terlebih dahulu ( seperti division dan mid-square) untuk mendapatkan hash code/address kemudian melakukan pertukaran seperti contoh : hasil hash : 123 -> menjadi 321.

Collision :

Dalam Hash Function akan sering ditemui permasalahan seperti yang terutama tabrakan/ collision dimana ada data yang mempunyai key yang sama dengan data sebelumnya sudah ada di database.

Secara umum ada dua cara mengatasi nya dengan :

• Linier Probing ( Array ) : Mencari slot kosong berikutnya dan mengisi data di slot tersebut. 

• Chaining ( Linked List ) :  Memasukan data dalam slot menggunakan chain list.

Linier Probing relatif akan memiliki complexity searching paling buruk daripada chaining apabila mendapatkan banyak data collision.

Implementation in BlockChain Technology :

Dalam BlockChain ada yang namanya ekripsi dimana yang pada Hashing menggunakan key yang kemudian digunakan untuk tidak hanya sebagai pencari data juga sebagai penyimpan rahasia suatu data. 

Panjang suatu hash tidak bisa ditentukan sehingga dapat mencegah seseorang untuk melakukan crack pada database

Seperti pada Bitcoin dimana juga digunakan untuk mengecek track atau history dari transaksi yang dilakukan juga disaat ada data transaksi baru yang masuk akan masuk terlebih dahulu ke proses mining untuk mencocokan  dan validasi dengan kode yang digunakan database sehingga keamanan nya pun lebih aman.

Tree 

    Tree adalah non linier data struct yang menunjukan tingkatan atau hierakhi antar data satu dengan lainnya seperti sisilah keluarga pada makhluk hidup. Node dalam tree tidak perlu untuk disimpan secara terus menerus dan bisa disimpan dimana saja dan dihubungkan menggunakan pointer.

Tree Concept :

• Node paling atas disebut root
• Garis yang menghubungkan node parent dengan anak adalah edge
• Node paling akhir / tidak mempunyai node anak disebut leaf
• Total sub node dari node tersebut disebut degree
• Maximum degree dari node atau maximum level nya disebut height

Binary Tree Concept

Data structure dari Tree yang dimana masing-masing node maksimal memiliki node anak 2. Dimana kedua anak tersebut biasa disebut node kiri dan node kanan. Node yang tidak mempunyai node anak disebut leaf.

Tipe dari Binary Tree :

• PERFECT binary Tree : Binary Tree dimana setiap level nya memiliki height/ jumlah node anak yang sama 
• Complete binary Tree : Binary Tree dimana setiap levelnya memiliki height yang sama kecuali untuk node terakhir yang paling ujung
• Skewed binary Tree : Binary Tree dimana setiap node nya mempunyai satu node anak
• Balanced binary Tree : Binary Tree yang dimana tidak ada leaf yang lebih jauh ke root daripada ke leaf berikut nya.

Maximum height dari sebuah  h Tree adalah 2^(h+1) -1. Sedangkan untuk minimumnya adalah ^2 log(n).

Implementation Tree :

1. Menggunakan Array dimana index 0 menjadi root nya dan index anak kiri adalah 2p+1 dan untuk index anak kanan 2p+2. Dan untuk mencari index parent (p-1)/2.
2. Menggunakan Linked List 

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Expression of Tree Concept :

• Postfix
• Infix
• Prefix

Threaded Binary Tree concept :
Binary Tree merupakan threaded apabila semua anak kiri dan kanan yang awalnya akan menunjuk ke NULL point ke penerus dari node nya atau pendahulunya

• One-way = Dimana setiap node nya akan menunjuk ke node penerusnya atau ke pendahulu ( Bisa node kiri maupun kanan) sehingga masih akan ada node anak kiri dan kanan menunjuk ke node yang sama.

• Two-way = Sedangkan untuk Two-way dimana nodenya menunjuk ke node penerus dan pendahulu yang berlaku untuk node kiri dan kanan.

Sumber :
https://en.wikipedia.org/wiki/Threaded_binary_tree
https://www.geeksforgeeks.org/hashing-data-structure/