Hashing Table and Binary Tree

HASHING TABLE AND BINARY TREE

HASHING TABLE AND BINARY TREE

A. Hashing Table

            

              Hash Table adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat jika kita mengetahui indeks dari data yang diinginkan.

Dengan demikian, itu menjadi struktur data di mana operasi penyisipan dan pencarian sangat cepat terlepas dari ukuran data. Tabel hash menggunakan array sebagai media penyimpanan dan menggunakan teknik hash untuk menghasilkan indeks di mana elemen yang akan dimasukkan atau harus ditempatkan dari.

              Hashing adalah teknik untuk mengubah rentang nilai-nilai kunci menjadi rentang indeks array. Kita akan menggunakan operator modulo untuk mendapatkan rentang nilai kunci. Pertimbangkan contoh tabel hash ukuran 20, dan item berikut ini harus disimpan. Item dalam format (kunci, nilai).

Operasi Pada Hash Tabel

•   insert : diberikan sebuah key dan nilai, insert nilai dalam tabel
•   find   :  diberikan sebuah key, temukan nilai yang berhubungan dengan key
•   remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus                   nilai tersebut
•   getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Struktur dan Fungsi pada Hash Tabel

          Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

         Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

            k(x) = fungsi pembangkit field kunci (1)

            h(x) = hash function (2)

B. BINARY TREE

       Pohon yang unsurnya paling banyak memiliki 2 anak disebut Binary Tree (Pohon Binary). Karena setiap elemen dalam Binary Tree hanya dapat memiliki 2 anak, kami biasanya menamai mereka anak kiri dan kanan.

       

Binary Tree terdiri dari beberapa bagian :

• Data
• Pointer to left child
• Pointer to right child

Tipe-tipe Binary Tree

1. PERFECT Binary Tree : adalah binary tree dimana setiap levelnya berada di depth yang sama.

                                      

      2. COMPLETE Binary Tree :  adalah binary tree yang setiap levelnya, kecuali kemungkinan yang terakhir, telah   lengkap terisi,  dan semua node sejauh mungkin dibiarkan. Pohon biner sempurna adalah pohon biner lengkap.

     3. SKEWED Binary Tree : adalah binary tree dimana setiap nodenya memiliki paling banyak 1 anak.

     4. BALANCED Binary Tree : adalah binary tree dimana tidak ada daun yang lebih jauh dari akar dibandingkan dengan                                                             daun yang lain.

Mengimplementasikan Binary Tree

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;