Hashing and Hash Table, Tree and Binary Tree

Materi Pembelajaran

1. Hashing
2. Hash Table
3. Hash Function
4. Collision
5. Tree Intoduction
6. Tree Concept
7. Binary Tree Concept
8. Type of Binary Tree
9. Property of Binary Tree
10. Expression Tree Concept
11. Threaded Binary Tree Concept

1. Hashing

Hashing dapat diartikan sebagai teknik untuk menyimpan dan mengambil kunci dengan cepat. Biasanya ini juga dapat disebut sebagai proses memetakan sejumlah besar item data ke tabel yang lebih kecil. 

2. Hash Table

Hash Table merupakan sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang memiliki tujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. 

Keuntungan dari hash table ini adalah waktu aksesnya yang cukup cepat. Namun pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Operasi yang digunakan dalam Hash Table:

1. insert = memasukkan nilai dalam tabel
2. find= mencari nilai dalam tabel
3. remove= mencari nilai dalam tabel, lalu dihapus
4. getIterator= memeriksa nilai satu per satu

3. Hash Function

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode untuk membangun fungsi hash:

1. Mid-square

Kuadratkan string lalu gunakan jumlah bit yang sesuai dari tengah kotak agar mendapatkan hash-key. Jika kuncinya adalah string, dikonversi ke angka.

2. Division

Membagi string dengan operator modulus. Metode hashing integer ini merupakan metode yang paling sederhana.

3. Folding

Partisi string atau identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4. Digit Extraction

Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap alamat hash.

5. Rotating Hash

Menggunakan metode hashing lalu ketika mendapatkan kode atau alamat hash dari metode tersebut,  maka lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

4. Collision

Ada dua cara untuk melakukan Collision :

1. Linear Probing, yaitu dengan mencari slot kosong berikutnya dan meletakkan string disana
2. Chainning, yaitu memasukkan string ke dalam slot sebagai linked list.

5. Tree Concept

1. Node A disebut sebagai root atau akar.
2. Garis yang menghubungkan induk ke anak adalah edge atau garis.
3. Node yang tidak memiliki anak disebut daun. Contohnya node E, F, G, dan H
4. Node memiliki orang tua yang sama disebut saudara. Contohnya node B.
5. Derajat simpul adalah total sub pohon simpul.
6. Tinggi atau kedalamanan tingkat maksimum node dalam pohon.
7. Jika ada garis yang menghubungkan A ke B, maka A leluhurnya B, dan B adalah keturunan A.

6. Binary Tree Concept

Sama seperti rooted tree, namun setiap node memiliki 2 anak. Node yang tidak memiliki anak disebut daun.

7. Type of Binary Tree

Tipe-tipe Binary Tree:

1. Perfect Binary Tree= setiap level memiliki kedalaman yang sama.

2. Complete Binary Tree

3. Skewed Binary Tree

8. Property of Binary Tree

1. Jumlah maksimum node pada k di binary tree adalah 2k

2. Jumlah maksimum node pada pohon biner tinggi h adalah 2h+1 - 1.

3. Tinggi minimum biner dari n node adalah 2log(n).

4. Tinggi maksimum biner dari n nide adalah n-1.

9. Expression Tree Concept

1. Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menulis tanda kurung (). Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.

2. Infix adalah cara penulisan ungkapan dengan meletakkan operator diantara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi (). Contoh pemakaian infix adalah 

A+B, A+B-C, (A+B)*(C-D).
3. Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung ().

10. Threaded Binary Tree Concept

Pohon biner berulir sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL. Dalam representasi tertaut, sejumlah node berisi pointer NULL baik di bidang kanan atau kiri atau keduanya. Ruang yang terbuang untuk menyimpan tunjuk NULL ini dapat digunakan untuk menyimpan kedamaian informasi bermanfaat lainnya.

3.

Refrensi : 

1. Binus Maya
2. https://www.google.com/url?sa=i&url=http%3A%2F%2Fyoutubesusanqenglmichelle.changeip.com%2Fuse-of-threaded-binary-tree.html&psig=AOvVaw0M4-eHdsIUnMmAPob31jtB&ust=1583950331759000&source=images&cd=vfe&ved=0CA0QjhxqFwoTCNDYnPnAkOgCFQAAAAAdAAAAABAP

Nama : Isaac Andrean Yoshua

NIM   : 2301927046