Data Structures - Hashing Table dan Binary Tree

HASHING TABLE

Hashing Table adalah struktur data yang menyimpan data dengan cara yang terkait. Dalam Hashing Table, data disimpan dalam format array, dengan setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat jika kita mengetahui indeks dari data yang diperlukan.

Akibatnya, struktur data di mana penyisipan dan pencarian sangat cepat terlepas dari ukuran data. Hashing Table menggunakan array sebagai media penyimpanan dan menggunakan teknologi hashing untuk membuat indeks dari mana item akan dimasukkan atau ditempatkan.

Hashing

Hashing adalah teknik untuk mengubah rentang nilai dasar menjadi serangkaian indeks matriks. Ini akan menggunakan operator modulo untuk mendapatkan satu set nilai dasar. Pertimbangkan contoh tabel hash ukuran 20, dan item berikut akan disimpan. Elemen dalam format (key,value).

Linear Probing

Mungkin saja teknologi hashing digunakan untuk membuat indeks dari array yang sudah digunakan. Dalam kasus seperti itu, kita dapat mencari posisi kosong berikutnya dalam array dengan melihat cell berikutnya sampai kita menemukan cell kosong. Teknik ini disebut Linear Probing.

Basic Operation

Di bawah ini adalah operasi dasar dasar tabel partisi.

·       Search - Mencari item dalam tabel hash.

·       Insert - Menyisipkan item ke tabel hash.

·       Delete - Menghapus item dari tabel hash.

Search

Saat mencari item, hitung hash code dari kunci yang dilewati dan cari item dengan hash code itu sebagai indeks dalam array. Gunakan pemindaian linier untuk meneruskan item jika item tidak ditemukan dalam code hash yang dihitung.

Insert

Ketika item dimasukkan, hitung hash code dari kunci yang dilewati dan cari indeks menggunakan hash code ini sebagai indeks dalam array. Gunakan cek linear situs kosong, jika elemen ditemukan dalam hash code yang dihitung.

Delete

Ketika item dihapus, hitung hash code kunci yang dilewati dan cari indeks dengan hash code itu sebagai indeks dalam array. Gunakan Linear Probing progres item jika item tidak ditemukan dalam hash code yang dihitung. Ketika Anda menemukannya, simpan item dummy di sana untuk menjaga kinerja Hash Table apa adanya.

BINARY TREE

Ini memperluas konsep struktur data yang terkait dengan struktur node dengan lebih dari satu bidang referensi-sendiri. Pohon biner terdiri dari node, dengan setiap node memiliki referensi "kiri", referensi "kanan" dan elemen data. Node atas di pohon disebut root.

Setiap node (kecuali untuk root) di pohon diikat ke tepi tepatnya dari node lain. Simpul ini disebut orang tua. Di sisi lain, setiap node dapat dihubungkan ke sejumlah node acak, yang disebut anak-anak. Node tanpa anak disebut daun, atau external node. Node yang tidak memiliki daun disebut internal node. Kontrak dengan orang tua yang sama disebut saudara.