Hashing Table & Binary Tree

   1.      Hashing and Hash Table

·        Hashing

Hashing adalah sebuah teknik untuk menyimpan data  dengan menggunakan index (key) dari string tersebut.
Fungsi hashing adalah untuk mendapat index (key) untuk menentukan lokasi data.
Contoh Hashing :
Misalkan kita ingin menyimpan 5 data string : “define”,”float”,”exp”,”char”,”atan” ke dalam hash table dengan size 26. Hash function yang kita gunakan adalah mengubah karakter pertama dalam string tersebut menjadi angka antara 0 sampai 25.
Hasilnya :
- define “d” = 3
- float “f” =  5
- exp “e” = 4
- char “c” = 2
- atan “a” = 0

              

·        Hash Table
Hash table adalah sebuah tabel / array dimana kita menyimpan string / data kita.
Index dari tabel adalah hashed key, sedangkan value (isi) di dalamnya adalah value dari data kita.

Contoh Hash Table :
5 string yang sudah dihashing akan disimpan sesuai nilai key yang didapatkan. Kita cuma memakai karakter pertama dari string.

-        atan disimpan di h[0] karna a = 0  

-        char disimpan di h[2] karna c = 2  

-        define disimpan di h[3] karna d = 3  

-        exp disimpan di h[4] karna e = 4  

-        float disimpan di h[5] karna f = 5  

·        Collision
Apa yang akan terjadi apabila kita ingin menyimpan string kita dengan metode hashing dengan menggunakan karakter pertama dari string :

“define”,”float”,”exp”,”char”,”atan”,”ceil”,”acos”,”floor”
Ada 3 pasang string yang mempunyai hash key yang sama, yaitu : “float” dan “floor, “char” dan “ceil”, “atan” dan “acos”.

Karena ada string yang mempunyai hash key yang sama, maka dapat terjadi collision.
Ada 2 cara untuk collision :

-        Linear Probling
Metode yang akan dilakukan adalah cari tempat yang kosong da nisi string tersebut di tempat kosong tersebut.

-        Chaining
Metode chaining adalah dengan menjadikan string tersebut ke dalam linked list.

·        Linear Probling
Contoh :

String : “define”,”float”,”exp”,”char”,”atan”,”ceil”,”acos”,”floor”

- “acos” berada di h[1]
- “ceil” berada di h[6]
- “floor” berada di h[7]

Ketika kita ingin menyimpan “ceil”, di h[2] sudah terpakai, jadi
kita menempatkannya di tempat kosong selanjutnya yaitu h[6].

Kekurangannya adalah kompleksitas searching jika terjadi banyak collision.
Ketika kita ingin mencari “ceil”, hash key dari “ceil” menunjukkan 2. Tetapi ceil tidak ada disana, jadi terus dilakukan looping sampai “ceil” ditemukan.

·        Chaining

Di dalam chaining, kita menyimpan setiap setiap ke dalam linked list.
Jadi, ketika terjadi collision, kita cuma perlu melakukan pengulangan di
linked listnya.  

   2.      Tree and Binary Tree

·       Tree
Tree adalah sebuah struktur data tidak linear yang menggambarkan hubungan hirarki antara satu data dengan yang lainnya.
Tree memiliki koleksi dari satu atau lebih node.

    Degree dari Tree = 3
Degree dari C = 2
Height = 3
Parent dari C = A
Children dari A = B,C,D
Sibling dari F = G
Ancestor dari F = A,C
Descendant dari C = F,G

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

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

-        Height : banyaknya tingkatan/level dalam suatu tree.

-        Root : node yang berada di paling atas.

-        Edge : garis yang menghubungkan parent to child.

-        Leaf : node yang tidak memiliki children.

-        Degree : banyaknya child yang dimiliki suatu node.

·        Binary Tree
Binary Tree adalah struktur data berbentuk tree yang di dalam setiap node memiliki 2 children. Children tersebut akan dibagi menjadi left child dan right child.
Node yang tidak memiliki child disebut leaf.

Contoh Binary Tree :

Terdapat 9 noda di dalam binary tree tersebut,
yang rootnya adalah 18

Leaf adalah noda dengan nilai 9,12,10 dan 23.

·        Jenis Binary Tree

-        Perfect Binary Tree
Binary Tree yang di dalam setiap levelnya memiliki depth yang sama.

-        Complete Binary Tree
Binary tree yang di dalam setiap levelnya, dan node kiri yang diutamakan diisi terlebih dahulu. Perfect binary tree adalah contoh dari complete binary tree.

-        Skewed Binary Tree
Binary tree yang di dalam setiap nodenya mempunyai maksimal 1 child.

-        Balanced Binary Tree
Binary tree yang tidak memiliki leaf (seimbang).