Hashing Table & Binary Tree

Halo semuanya! Sekarang saya ingin membahas singkat tentang Hashing Table dan Binary Tree. 

A. Hashing Table

Hashing tree adalah sebuah struktur data yang terdiri dari sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap baris menjadi angka lokasi record tersebut dalam sebuah tabel.

 Keunggulan dari hash table ini sendiri adalah pencarian dan waktu akses yang cepat. Tetapi ada kenegatifannya juga dari hash table yaitu jika record(sesuatu yang kita cari dalam hash table) memiliki angka yang sama, maka hal ini dapat menyebabkan bentrokan/collision antar record. Untuk mengatasi masalah ini dibutuhkan collision resolution policy(kebijakan resolusi bentrokan) untuk menentukan lokasi record dalam tabel sehingga tidak menyebabkan bentrokan antar record kembali.

Operasi yang digunakan dalam hash table:

• insert: diberikan sebuah key dan nilai, insert nilai dalam tabel.
• find: diberikan sebuah key, temukan nilai yang sesuai dengan key.
• remove: diberikan sebuah key, temukan nilai yang sesuai dengan key, lalu hapus nilai tersebut.
• getIterator: mengembalikan iterator, yang memeriksa nilai satu demi satu.

Cara untuk mendeklarasikan hash table :

typedef struct hashtbl {

hash_size size;

struct hashnode_s **nodes;

hash_size (*hashfunc)(const char *);

} HASHTBL;

dibawah ini merupakan struct yang digunakan untuk menunjuk kepada unsur pertama yang terhubung dengan daftar :

struct hashnode_s {

char *key;

void *data;

struct hashnode_s *next;

}

B. Binary Tree

Binary Tree adalah pohon yang dimana setiap simpulnya hanya boleh memiliki dua anak/subtree kedua anak/subtree tersebut HARUS terpisah. Kegunaan dari binary tree ini sendiri adalah untuk mengurutkan data-data yang disusun secara ascending(dari kecil ke besar) maupun descending(dari besar ke kecil).

Mungkin sampai disini kalian masih bingung cara memakai binary tree bagaimana. Oleh karena itu, saya akan memberikan contoh pemakaian binary tree.

Misalnya kita memiliki angka yang diacak yaitu 4 2 7 1 3. Aturan saat “insert” kedalam binary tree ini adalah dengan membandingkan data yang akan dimasukkan dengan kondisi root saat itu. Ok, mari kita telaah! angka pertama yang akan menjadi “root” adalah 4, maka angka tersebut akan menjadi paling atas. Lalu berikut nya 2, nah disini kita akan membandingkan 2 dengan 4, 2 lebih kecil dibanding 4, maka dia akan diletakkan dikir. Lalu 7, karena 7 lebih besar dari 4, maka 7 diletakkan disebelah kanan. Lalu 1, 1 lebih kecil dibandingkan 4 maka akan masuk ke sebelah kiri, namun karena sebelah kiri sudah memiliki “root” yaitu 2, maka 1 akan dibandingkan kembali dengan 2, karena 1 lebih kecil dibandingkan dengan 2, maka 1 diletakkan disebelah kiri dari 2. Begitu juga berlaku dengan 3. Binary tree akan memiliki bentuk seperti berikut :

1. 4
2. / \
3. 2 7
4. / \
5. 1 3

Bagi kalian yang baru mengetahui tentang binary tree, berikut adalah istilah-istilah yang dimiliki oleh tree itu sendiri :

• Parent : predecssor satu level di atas suatu node.
• Child : successor satu level di bawah suatu node.
• Sibling : node-node yang memiliki parent yang sama dengan suatu node.
• Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
• Size : banyaknya node dalam suatu tree.
• Height : banyaknya tingkatan/level dalam suatu tree.
• Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
• Leaf : node-node dalam tree yang tak memiliki seccessor.
• Degree : banyaknya child yang dimiliki suatu node.

Dibawah ini merupakan contoh dari Binary tree :

Berikut adalah penjelasan singkat dari saya, jika ada salah dan mungkin ada yang kurang penjelasannya bisa bertanya di kolom komentar. Terima kasih.

Nama : Reinhart Perbowo Pujo Leksono

NIM : 2301857254

Sumber:

1. https://id.quora.com/Apa-kegunaan-Binary-Tree-dalam-pemrograman
2. https://www.google.com/search?q=binary+tree+example&tbm=isch&ved=2ahUKEwiN98uEi5LoAhVTHHIKHTgICxEQ2-cCegQIABAA&oq=binary+tree+example&gs_l=img.3...0.0..415221...0.0..0.0.0.......0......gws-wiz-img.ny0982zKyr8&ei=ZaxoXs2wK9O4yAO4kKyIAQ&bih=722&biw=1536&safe=strict
3. http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html