Linked List

Hash Table and Binary Tree

Ketika kita diberikan data yang sangat banyak, kita harus membutuhkan suatu data structure yang cepat untuk melakukan banyak hal (insert, delete,dan search). Seharusnya kita mempunyai kunci(key) untuk dapat mengakses data tersebut, agar ketika kita mencari, kita hanya tinggal memakai key tersebut, sehingga waktu yang diperlukan untuk mencari data lebih efisien, karena sudah mendekati dimana lokasi data tersebut dibanginkan jika kita mencari data secara linear(satu per satu). Ada beberapa cara untuk mengimplementasi cara penggunaan key ini, contoh nya seperti, hash table, balanced binary search tree(bst) dan doubly linked list.

Hash Table

Untuk sekarang, saya akan menjelaskan tentang hash table. Hash table merupakan method tercepat yang dapat digunakan insert,delete dan search dibandingkan bst dan double linked list.

Di dalam hash table terdapat suatu function bernama hash function, hash function adalah function untuk menempatkan index dari suatu key dalam suatu array.

Ada banyak cara hash function seperti, salah satu contohnya division method, division method adalah salah satucara pada hash function dimana kita akan menaruh suatu index pada array h dimana
h(k) = k%m , k disini merupakan key dan m merupakan panjang arraynya.

dibawah ini merupakan contoh dari division method:

untuk contoh disamping, terdapat key 1276, maka index dari key tersebut akan disimpan dalam array ke - [6]

Namun, apa yang terjadi jika dalam array tersebut telah terdapat data yang telah disimpan? ini disebut hash collision. Ada banyak cara untuk mengatasi hash collisin ini, contohnya seperti open addressing dan closed addressing.

Open Addressing
suatu cara yang digunakan untuk mencari tempat kosong setelah tempat key tersebut terisi.

Contoh penggunaan open addressing pada bahasa C

Closed Addressing
cara yang digunakan untuk menempatkan suat data secara linked list.

Contoh penggunaan closed addressing

Binary Tree

Tree Concept

Tree adalah sebuah struktur data yang memiliki bentuk sebuah pohon, yang terdiri dari serangkaian node (simpul) berisi data yang saling berhubungan.

Binary tree

Binary Tree adalah sebuah pohon yang menyimpan data, keunikan binary tree adalah mensortir semua data yang dimasukkan. Sebuah binary search tree memiliki root dan cabang left serta right pada setiap nodenya.

dalam binary tree, kita dapat melakukan insert.
Contoh dari insert dalam binary tree: mencari dari parent dimana lokasi yang tepat untuk memasukkan nilai, dan jika ditemukan bahwa parentnya tersebut NULL, masukkan ke dalam parent

Berikut adalah contoh code di C jika kita ingin memasukkan data sesuai gambar diatas

Demikian penjelasan saya mengenai Hash Table dan Binary Tree, terima kasi telah membaca
^ ^