Hash Table & Binary Tree

Nama : Raymon Elnardi
Nim   : 2310908620
Kelas : LL01
=======================================================================
       Hari ini saya akan membahas Hashing, Hash Table dan Binary Tree


          Hashing
=======================================================================
       Hashing adalah data structure yang berfungsi untuk memetakan nilai berdasarkan original sting yang kita masukkan kedalam index kata kunci tertentu, kedalam Hash Table. Hash table adalah sebuah array untuk menampung nilai.  Hashing digunakan untuk memanggil fungsi yang spesial yang disebut hash function.




       Terdapat banyak macam cara menggunakan Hashing, tetapi kita akan membahas 5 buah teknik yang paling umum digunakan yaitu : Mid-square, Division, Folding, Digit Extraction, Rotating Hash


       Mid-square
Mid-square adalah cara yang menggunakan bagian tengah dari original string sebagai key
   Function : h(k) = s
   k = original string
   s = bagian tengah dari string
misal : original string = 561380 maka key = 13

       Division
Division adalah cara yang me-modulus original string dengan nilai tertentu menjadi sebuah key
   Function : h(z) = z mod M
   z = original string
   M = nilai tertentu
misal :  original string = 7763 dan M = 10 maka key = 3

      Folding
Folding adalah cara yang membagi original string menjadi beberapa bagian kemudian, dari bagian-bagian tersebut dapat diolah menjadi sebuah value
misal : original string = 190274 dan kemudian dibagi untuk setiap 2 digit menjadi 19, 02, 74 dan semua bagian ingin dijumlahkan, maka key = 19 + 2 + 74 = 95

      Digit Extraction
Digit Extraction adalah cara yang menghapus bagian dari original string berdasarkan angka angka yang telah ditentukan misal : original string = 12345 dan yang ingin yang dihapus adalah 3 dan 4 maka key = 125

      Rotating Hush
Rotating Hush adalah cara yang memutar balik original string menjadi key
misal : original string = 012396 maka key = 693210


       Collision
=======================================================================
      Collision adalah sebuah masalah yang terjadi jika ada 2 buah original string yang akan disimpan pada key yang sama maka akan terjadi bentrokan (collision). Ada 2 buah cara untuk menangani kasus ini

  1.  Linear Probing
   Linear Probing adalah teknik mengecek dari atas sampai bawah apakah ada slot yang kosong

  2. Chaining

  Chaining adalah teknik yang menggunakan Linked List kedalam satu buah index yang memiliki 2 buah original string

          Binary Tree

=======================================================================

       Tree adalah kumpulan data yang non-linear berbeda dengan linked list yang merupakan kumpulan data yang linear.

 Ada beberapa bagian dari tree yang perlu di ketahui

- Root              : Bagian puncak dari tree

- Edge              : Garis yang menghubungkan node parent dan node child

- Leaf               : Node yang tidak memiliki garis yang terhubung ke node child

- Sibiling          : Node yang memiliki parent yang sama

- Degree           : Jumlah garis keturunan

- Heigth/Depth : Jumlah maksimal degree dari atas ke paling bawah

- Ancestor        : Semua node yang diatas dan terhubung dalam 1 garis pada suatu node

- Descendant    : Semua node yang dibawah dan terhubung dalam 1 garis pada suatu node

       Ada yang disebut sebagai Binary Tree. Binary Tree adalah rooted tree yang dimana semua nodenya memiliki maksimal 2 child node

     Ada 5 macam Binary Tree yang perlu kamu ketahui yaitu :

- Full Binary Tree, Binary Tree yang memiliki 0 atau 2 child pada setiap level

- Complete Binary Tree, Binary Tree yang semua levelnya terisi penuh kecuali level yang paling                                                terakhir

- Degenerate / Skewed Binary Tree, Binary Tree yang setiap node hanya memilik satu buah child

- Perfect Binary Tree, Binary Tree yang pada semua levelnya terisi penuh

- Balanced Binary Tree, Binary Tree yang pada subtree kiri dan subtree kanan yang berjarak 1 height

       Binary Tree memiliki macam macam sifat :

-Node maximum pada setiap level dapat dihitung dengan 2^k (k adalah level dari Binary Tree),

-Total dari semua Node dapat dihitung dengan 2^h - 1 (h adalah height dari Binary Tree)

- Height dari Tree adalah total dari level Tree (kecuali root)

- Jika diberikan total dari jumlah node, maka kamu dapat membentuk height minimum dengan ^2log(n) dan height maximum adalah n-1 (n adalah total dari node)