Hashing and Hash Tables, Tree & Binary Tree

Materi Data Structure 10 Maret 2020

Hal yang akan dibahas pada pertemuan kali ini adalah :
1. Hashing
2. Hash Table
3. Hash Function
4. Collision
5. Tree Introduction
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. Apa itu hashing ?

- Hasing adalah teknik yang digunakan untuk menyimpan dan menggambil kunci dengan cepat.

- Hashing juga disebut sebagai proses memetakan sejumlah besar item data ke tabel yang lebih kecil    dengan bantuan fungsi hasing.

- Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat            menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya                      menggunakan nilai asli.

2.Hash Table

Hash table adalah tabel tempat untuk menyimpan string asli. indeks tabel adalah  hash key, sementara Valueya adalah string asli.

ukuran hash table biasanya besarnya kurang dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hash key yang sama.

3. Hash Function

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

1.  Mid-square

jika hash key nya adalah string maka diubah menjadi interger terlebih dahulu

langkah-langkah :

   1.Square the value of the key. (k2)

   2. Extract the middle r bits of the result obtained in Step 1

contoh :

2. Division

- Divide the string/identifier by using the modulus operator.

- It's the most simple methd of hashing an integer x

contoh :

jika hash key nya adalah string maka diubah menjadi interger terlebih dahulu dengan menggunakan ASCII

3. Folding

langkah-langkah :

1.Divide the key value into a number of parts

2.Add the individual part (leading is ignored)

contoh :

4. Digit Extraction

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

contoh:

 x = 14,568

If we extract the 1st, 3rd, and 5th digit, we will get a hash code of : 158. 

5. Rotating Hash

langkah-langkah :

1. melakukan hash rotation setelah mendapatkan hash address

2. rotation dilakukan dengan menggeser digit untuk mendapatkan alamat baru

contoh :

–Given hash address = 20021

–Rotation result: 12002 (fold the digits)

4. Collision

Terdapat 2 cara untuk melakukan Collision yaitu :
1. Linear probing
dengan cara mencari slot kosong berikutnya dan letakan string disana

linear probing merupakan skema dalam pemrograman komputer untuk menyelesaikan collision dalam hash table

contoh :

The collision between John Smith and Sandra Dee (both hashing to cell 873) is resolved by placing Sandra Dee at the next free location, cell 874.

2. Chaining
dengan cara masukkan string ke dalam slot sebagai linked list

dalam chaining, kita menyimpan masing-masing string ke dalam rantai (linked list)
jadi jika terjadi collision kita hanya perlu beralih pada rantai itu

contoh :

5. Tree Introduction
Tree adalah struktur data non-linear yang mewakili hubungan hirarkis di antara objek data

6. Tree Concept

Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

Edge - is a line connecting the parent to the child

Leaf − The node which does not have any child node is called the leaf node

Sibling - The node which is have the same parent

Degree of the node is the total sub tree of the node

Height/Depth - is the maximum degree of nodes in a tree

If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p. 

7. Binary Tree Concept
Binary tree adalah struktur data rooted tree, dimana setiap node memiliki paling banyak dua anak.

karena setiap elemen dalam binary tree hanya dapat memiliki 2 anak, biasanya dinamai dengan anak kiri dan kanan.

contoh binary tree :

8. Type of Binary Tree
Terdapat beberapa tipe binary tree yaitu :

1. Perfect Binary Tree
yaitu binary tree yang dimana semua node interior memiliki dua anak dan semua leaf memiliki kedalaman yang sama atau level yang sama

2. Complete Binary Tree
yaitu binary tree yang dimana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node berada sejauh mungkin

3. Skewed Binary Tree
yaitu binary tree yang dimana setiap node paling banyak memiliki 1 anak

4. Balanced Binary Tree

 A binary tree is height balanced if it satisfies the following constraints:

1. The left and right subtrees' heights differ by at most one, AND
2. The left subtree is balanced, AND
3. The right subtree is balanced

An empty tree is height balanced.

9. Property of Binary Tree
- Maximum number of nodes on level k of a binary tree is 2k
- Maximum number of nodes on a binary tree of height h is 2h+1 - 1.
- Minimum height of a binary tree of n nodes is 2log(n).
- Maximum height of a binary tree of n nodes is n - 1.

10. Expression Tree Concept
Terdapat beberapa expression dalam tree yaitu :
1. Prefix 
2. Postfix
3. Inflix
 yang akan dijelaskan dalam gambare berikut 

11. Threaded Binary Tree Concept

A threaded binary tree is defined as follows:

"A binary tree is threaded by making all right child pointers that would normally be null point to the in-order successor of the node (if it exists), and all left child pointers that would normally be null point to the in-order predecessor of the node"

Berikut adalah perbedaan binary tree dengan threaded binary tree

kelebihan dari threaded binary tree

- Ini memungkinkan lintasan linier elemen di pohon

-Treanversal linear menghilangkan penggunaan tumukan yang pada gilirannya akan menghabiskan banyak ruang memori dan waktu

-ini memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer orangtua secara eksplisit

Nama : Timothy Gilbert
NIM : 2301851036
Kelas Besar : CB01
Kelas Kecil : LK01