Hashing and Hash Tables, Trees & Binary Tree

Hashing and Hash Tables, Trees & Binary Tree

Hashing : teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. 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.

Hash Table : tabel (array) tempat kita menyimpan string asli. Indeks tabel adalah kunci hash sementara nilainya adalah string asli. Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.

Hash Function : beberapa metode untuk membuat fungsi hash yaitu =

·       Mid-square : Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

·       Division (most common) : Membagi string / identifier dengan menggunakan operator modulus.

·       Folding : Partisi string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

·       Digit Extraction : Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

·       Rotating Hash : Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

Collision : Apa yang terjadi jika kita ingin menyimpan string ini menggunakan fungsi hash sebelumnya (gunakan karakter pertama dari setiap string). mendefinisikan, float, exp, char, atan, ceil, acos, floor. Ada dua cara umum untuk menangani tabrakan: Probing Linier (Cari slot kosong berikutnya dan letakkan talinya di sana) dan  chaining (Masukkan string ke dalam slot sebagai daftar rantai (daftar tertaut)).

Tree : struktur data non-linear yang mewakili hubungan hierarkis di antara objek data. Merupakan koleksi atas satu atau lebih node. Node di atas disebut sebagai root. Garis yang menghubungkan induk ke anak adalah edge. Node yang tidak memiliki anak disebut leaf. Node yang memiliki orang tua yang sama disebut siblings. Derajat simpul adalah total sub pohon node. Tinggi / Kedalaman adalah tingkat maksimum node dalam pohon. Jika ada garis yang menghubungkan p ke q, maka p disebut leluhur q, dan q adalah turunan dari p.

Binary tree :  struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Tipe-tipe binary tree :

·       PERFECT binary tree adalah pohon biner di mana setiap level berada pada kedalaman yang sama.

·       binary tree DONE adalah pohon biner di mana setiap level, kecuali mungkin yang terakhir, terisi penuh, dan semua node sejauh mungkin dibiarkan. Pohon biner sempurna adalah pohon biner lengkap.

·       binary tree SKEWED adalah pohon biner di mana setiap node memiliki paling banyak satu anak.

·       binary tree BALANCED adalah pohon biner di mana tidak ada daun yang jauh lebih jauh dari akar daripada daun lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").

Threaded Binary Tree : sama dengan pohon biner tetapi dengan perbedaan dalam menyimpan pointer NULL.

Inorder Traversal : Inorder Algoritma (pohon)

   1. Lintasi subtree kiri, serta Panggil Inorder (subtree kiri)

   2. Kunjungi root.

   3. Traverse subtree kanan, serta Panggil Inorder (subtree kanan)

Penggunaan Inorder : Dalam kasus pohon pencarian biner (BST), Inorder traversal memberikan node dalam pesanan yang tidak berkurang. Untuk mendapatkan node BST dalam pesanan yang tidak meningkat, variasi Inorder traversal di mana Inorder traversal terbalik dapat digunakan.

Preorder Traversal : Preorder Algoritma (pohon)

1. Kunjungi root.

2. Lintasi subtree kiri,  Panggil Preorder (subtree kiri)

3. Melintasi subtree kanan, Panggil Preorder (subtree kanan)

Penggunaan Preorder : Preorder traversal digunakan untuk membuat salinan pohon. Travers preorder juga digunakan untuk mendapatkan ekspresi awalan pada pohon ekspresi.

Postorder Traversal : Algoritma postorder (pohon)

1. Lintasi subtree kiri, Panggil Postorder (subtree kiri)

2. Melintasi subtree kanan, Memanggil Postorder (subtree kanan)

3. Kunjungi root.

Penggunaan Postorder : Travers postorder digunakan untuk menghapus pohon. Silakan lihat pertanyaan untuk penghapusan pohon untuk detailnya. Travers postorder juga berguna untuk mendapatkan ekspresi postfix dari pohon ekspresi.

Sumber : https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/