Hashing & Binary Tree

hashing table 

Apa itu Hashing

Hashing atau juga yang dikenal sebagai Hashing Algorithm adalah transformasi dari beberapa input menjadi fixed-value yang lebih pendek, dan simple dibanding dengan alamat data aslinya, yang mewakili input aslinya.  
 
Hash atau Hashing berarti memenggal dan kemudian menggabungkan, dari konsep hashing tersebut Hash dapat membantu dalam proses mengindeksdan megambil data dalam database karena Memiliki keuntungan lebih cepat dalam insertion dan searching value yang ada di array, dari pada mencari dengan nilai aslinya. 
 

Komponen yang harus dimiliki dalam hashing adalah:

• key atau disebuh dengan hashed key adalah cara membuat karakter yang akan menjadi identifikasi baru dari value agar lebih mudah dicari datanya, dan  akan dimasukan ke dalam hashing table.
• Value adalah data yang dimasukkan ke dalam array.

Hash Table

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value didapatlah hash value. Tujuan dari hash table adalah untuk mempercepat proses pencarian dari banyak data yang disimpan. Karena dalam penyimpanan data di Hash table menggunakan key penyimpanan, sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) menjadi lebih cepat.

Ada beberapa cara hashing string menjadi key, diantaranya:

• Mid-square
• Division
• Folding
• Digit extraction
• Rotating hash 

Implementasi Hashing Table pada BlockChain
blockchain adalah implementasi peer-to-peer, yang berarti bahwa seluruh blockchain disimpan di setiap peer. List pada blockchain tersebut dapat terus bertambah hingga tak terhingga. Setiap blok memiliki nilai hash dari blok sebelumnya, waktu pembuatan blok, dan data. Desain blockchain yang seperti itu membuah tercegahnya resisten terhadapat pengubahan, karena setiap perubahan pada suatu blok akan membuat blok selanjutnya menjadi tidak valid. Untuk menambah keamanan, blockchain disimpan dalam jaringan terdistribusi dengan protokol peer-to-peer tertentu. Sehingga list blok tersebut terduplikasi di banyak server.

===========================================================

Binary Tree

Merupakan salat Satu bentuk Struktur Data tidak linier Yang menggambarkan hubungan Yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree Bisa didefinisikan sebagai kumpulan Simpul / node dengan Satu elemen KHUSUS Yang disebut root Dan Node lainnya terbagi menjadi Himpunan-Himpunan Yang tak saling berhubungan Satu sama lainnya (disebut subtree). Untuk jelasnya, di Bawah Akan diuraikan istilah-istilah umum dalam tree.

Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

• Istilah umum dalam tree :

1.    Predecessor : node yang berada diatas node tertentu

2.    Successor : node yang berada di bawah node tertentu

3.    Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama

4.    Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama

5.    Parent : Predecessor level di atas suatu node

6.    Child : successor satu level di bawah suatu node

7.    Sibling : node-node yang memiliki parent yang sama dengan suatu node

8.    Subtree : bagian dari tree yang berupa suatu node beserta descendant nya dan memiliki semua karakteristik dari tree tersebut

9.    Size : banyaknya node dalam suatu tree

10. Height : banyaknya tingkatan/level dalam suatu tree

11. Root : satu-satunya node khusus dalam tree yang tak punya predecessor

12. Leaf : node-node dalam tree yang tak memiliki successor

13. Degree : banyaknya child yang dimiliki suatu node

Tipe - tipe binary tree

• Perfect Binary Tree, yaitu Binary Tree yang tiap nodenya memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

• Complete Binary Tree, Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

• Skewed Binar Tree, Binary Tree yang semua nodenya hanya memiliki satu child.

• Balanced Binary Tree, adalah jenis tree yang tidak ada daun yang lebih jauh dariakar daripada daun lainnya.

Implementasi Binary Tree

•         double pointer, maka fungsi insert / push, akan jadi seperti ini :

Perbedaan cara memanggil fungsi single dan double pointer adalah seperti ini :

o   Contoh single: push(root,50);

o   Contoh double: push2(&root,50);

Jika dilihat dari code di atas, code double pointer kita bisa melakukan passing by address. Sehingga ketika kita melakukan malloc atau memanggil newNode pada fungsi push2, maka root yang aslinya akan kena malloc juga. Berbeda dengan single pointer, jika kita melakukan node = newNode(a), maka root yang asli tidak akan ikut kena malloc, Karena ini merupakan passing by value.