GSLC | Hashing & Binary Tree Jordy Ferdian-2301888524

Hashing

Hashing adalah sebuah teknik untuk mengubah sebuah string karakter menjadi sebuah key yang mempresentasikan string karakter aslinya tersebut. 

Tujuannya adalah untuk mempercepat pencarian dan pengambilan item dari sebuah database, karena mencari dengan hash key yang sudah disingkatkan lebih cepat dibandingkan mencari dengan string karakter aslinya.

Hash Table

Hash table adalah array dimana kita menyimpan string kita. Index dari array hash table adalah hash key yang disingkatkan dari string sedangkan value yang disimpan adalah string tersebut.

Hash Function

Hash function adalah teknik-teknik untuk membuat hash kay.

1. Mid Square

Mendapatkan hash key dengan cara mengkuadratkan string lalu mengambil tengah nya untuk menjadi key.

Contoh: terdapat nilai 675248 maka akan di kuadratkan terlebih dahulu, kemudian diambil tengahnya.

675248->455959861504-> 959861(hash keynya)

2. Division

Mendapatkan hash key dengan cara memodulus stringnya. Hasil modulusnya adalah hash key.

Contoh:

asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai kunci sebagai berikut : 12,21,68,38,52,70,44,18.

Maka:

(12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 dilokasi 2

(21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11

(68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3

(38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6

(52 mod 11) + 1 = 9 + 1 = 10 ; simpan 52 dilokasi 10

(70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5

(44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1

(18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8

Sehingga :

Index 1 2 3 4 5 6 7 8 9 10 11

Nilai Key 44 12 68 – 70 38 – 18 52 – 21

3. Folding

Mendapatkan hash key dengan cara mempartisi string menjadi beberapa bagian lalu menjumlahkannya (tanpa carry).

Contoh : 

Kunci 123456, 234351, 222456 dilipat menjadi 2 bagian, setiap 3 digit.
Maka :
123+654 = 777 ; simpan 123456 dilokasi 777
234+153 = 387 ; simpan 234351 dilokasi 387
222+654 = 876 ; simpan 222456 dilokasi 876

 

      4. Digit Extraction

Mendapatkan hash key dengan cara mengambil digit-digit tertentu dari sebuah string untuk dijadikan 

 hash keynya.

Contoh: terdapat string yaitu 123456

jika kita mengambil digit ke-1 , ke-4 dan ke-6 maka hash keynya adalah 146

          5. Rotating hash

Mendapatkan hash key dengan cara merotasikan hash key yang didapatkan dengan function-function diatas.

Contoh: terdapat hashkey 146 dari digit extraction tadi maka rotating hash akan merotate hash key tersebut menjadi  641.

Collision

Collision adalah ketika beberapa string memiliki hash key yang sama. Untuk menyelesaikannya terdapat 2 teknik yaitu Linear Probing dan Chaining.

          1. Linear Probing

Menyelesaikan collision dengan mencari slot yang kosong di array lalu menyimpan string tersebut disana.

Pada contoh dibawah ceil dan char memiliki hash key sama sehingga saat mau menyimpan ceil sudah terdapat char di h[2] oleh karena itu ceil dimasukkan ke tempat yg kosong yaitu h[6].

          2. Chaining

Menyelesaikan collison dengan cara menaruh string tersebut sebagai chained list/linked list dari slot hash key yang sama.
Pada contoh dibawah acos dan atan memiliki hash key yang sama sehingga saat mau menyimpan acos di h[0] terdapat atan. Jadi dibuatlah linked list dari atan yang menunjuk pada acos.

Binary Tree

Binary tree adalah sebuah data structure tree yang setiap node nya memiliki paling banyak 2 child.

Node yang tidak memiliki child disebut leaf.

Jenis-jenis Binary Tree

          1. Perfect Binary Tree

Binary tree dimana setiap level berada di depth yang sama.

          2. Complete Binary Tree

Binary tree dimana semua level kecuali yang terakhir terisi penuh dan semua node berada di kiri. Sebuah perfect binary tree adalah complete binary tree.

          3. Skewed Binary Tree

Binary tree dimana semua node memiliki paling banyak 1 child.

4. Balanced Binary Tree

Binary tree dimana tidak ada leaf yang paling jauh dari root dari semua leaf.

Sifat-sifat binary tree

          1. Jumlah node maksimal dalam sebuah level adalah 2^level;

          2. Jumlah node maksimal dalam sebuah binary tree adalah 2^height+1 – 1

          3. Height dari sebuah tree adalah jumlah level atau level tertinggi di tree tersebut.

          4. Minimum height tree yang memiliki n nodes adalah ²log(n).

          5. Maximum height tree yang memiliki n nodes adalah n - 1.

Berikut adalah gambaran binary tree untuk mempermudah:

Source code Binary tree:
struct node {

                int data;

                struct node *left; //Pointer mengarah ke child leftnya

                struct node *right;  //Pointer mengarah ke child rightnya

                struct node *parent;  //Pointer mengarah ke parentnya

};

struct node *root = NULL;

Expression Tree
Expression tree adalah binary tree dimana setiap node internal adalah operator dan node leaf adalah operand.
Contoh Expression tree dari 3 + ((5+9)*2)

Dalam expression tree terdapat 3 cara traversal yaitu:
1. Infix (InOrder Traversal) adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand. Contoh Infix diatas: 3+(5+9)*2

2. Prefix (Preorder Traversal) adalah notasi yang terbentuk atas operator dengan operand, dimana operator didepan operand. Contoh Prefix diatas:  +3*+592

3. Postfix (Postorder Traversal)  adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand. Contoh Postfix diatas adalah 3+59+2*