hashing table dan binary tree

HASHING TABLE AND BINARY TREE

A. HASHING TABLE



Hash table merupaka salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Yang perlu diperhatikan untuk membuat hash function adalah:

–       ukuran array/table size(m),

–       key value/nilai yang didapat dari data(k),

–       hash value/hash index/indeks yang dituju(h).

Berikut contoh penggunaan hash table dengan hash function sederhana yaitu memodulus key value dengan ukuran array : h = k (mod m)

Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).

Dengan hash function tersebut didapat :

k	H
7	7
13	0
25	12
27	1
39	0

Perhatikan range dari h untuk sembarang nilai k.

Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..

Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.

Misal : mencari data 25 → h = 25 (mod 13) = 12

Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.

Untuk meminimalkan collision gunakan hash function yang dapat mencapai seluruh indeks/alamat. Dalam contoh di atas gunakan m untuk me-modulo k. Perhatikan bila kita menggunakan angka m untuk me-modulo k maka pada indeks yang lebih besar dari dan sama dengan m di hash table tidak akan pernah terisi (memori yang terpakai semakin kecil), kemungkinan terjadi collision juga semakin besar.

Karena memori yang terbatas dan untuk masukan data yang belum diketahui tentu collision tidak dapat dihindari.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.      Linear Probing

Pada saat terjadi collision, maka akan mencari posisi yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti HashTable sudah penuh. Contoh deklarasi program:

struct { ... } node;

node Table[M]; int Free;

/* insert K */

addr = Hash(K);

if (IsEmpty(addr)) Insert(K,addr);

else {

/* see if already stored */

test:

if (Table[addr].key == K) return;

else {

addr = Table[addr].link; goto test;}

/* find free cell */

Free = addr;

do { Free--; if (Free<0) Free=M-1; }

while (!IsEmpty(Free) && Free!=addr)

if (!IsEmpty(Free)) abort;

else {

Insert(K,Free); Table[addr].link = Free;}

}

2.      Quadratic Probing

Penanganannya hampir sama dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … )

3.      Double Hashing

Pada saat terjadi collision, terdapat fungsi hash yang kedua untuk menentukan posisinya kembali.

B. binary tree

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.
Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya  dinamakan kiri dan kanan.
Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).

Mengapa pohon?

1. Salah satu alasan untuk menggunakan pohon mungkin karena Anda ingin menyimpan informasi yang secara alami membentuk hierarki. Misalnya, sistem file di komputer:

2. Pohon (dengan beberapa pemesanan misalnya, BST) menyediakan akses / pencarian moderat (lebih cepat dari Daftar Tertaut dan lebih lambat daripada array).

3. Pohon menyediakan penyisipan / penghapusan moderat (lebih cepat dari Array dan lebih lambat dari Daftar Tertaut yang Tidak Diurut).

4. Suka Daftar Tertaut dan tidak seperti Array, Trees tidak memiliki batas atas jumlah node karena node ditautkan menggunakan pointer.

Aplikasi utama pohon meliputi:

1. Memanipulasi data hierarkis.

2. Jadikan informasi mudah dicari (lihat traversal pohon).

3. Memanipulasi daftar data yang diurutkan.

4. Sebagai alur kerja untuk mengomposisikan gambar digital untuk efek visual.

5. Algoritma router

6. Bentuk pengambilan keputusan multi-tahap (lihat catur bisnis).

Binary Tree: Sebuah pohon yang unsur-unsurnya memiliki paling banyak 2 anak disebut pohon biner. Karena setiap elemen dalam pohon biner hanya dapat memiliki 2 anak, kami biasanya menamai mereka anak kiri dan kanan.

Representasi Biner Pohon di C: Sebuah pohon diwakili oleh pointer ke simpul paling atas di pohon. Jika pohon itu kosong, maka nilai root adalah NULL.

Node pohon berisi bagian-bagian berikut.

1. Data2. Pointer ke anak kiri3. Pointer ke kanan anak

Dalam C, kita dapat mewakili simpul pohon menggunakan struktur. Di bawah ini adalah contoh simpul pohon dengan data integer.

struct node 

{

  int data;

  struct node *left;

  struct node *right;

};

Pohon Sederha Pertama di C

Mari kita buat pohon sederhana dengan 4 node di C. Pohon yang dibuat akan seperti berikut.

tree
      ----
       1    <-- root
     /   \
    2     3  
   /   
  4

struct node 

{

    int data;

    struct node *left;

    struct node *right;

};

  

/* newNode() allocates a new node with the given data and NULL left and 

   right pointers. */

struct node* newNode(int data)

{

  // Allocate memory for new node 

  struct node* node = (struct node*)malloc(sizeof(struct node));

  

  // Assign data to this node

  node->data = data;

  

  // Initialize left and right children as NULL

  node->left = NULL;

  node->right = NULL;

  return(node);

}

  

  

int main()

{

  /*create root*/

  struct node *root = newNode(1);  

  /* following is the tree after above statement 

  

        1

      /   \

     NULL  NULL  

  */

    

  

  root->left        = newNode(2);

  root->right       = newNode(3);

  /* 2 and 3 become left and right children of 1

           1

         /   \

        2      3

     /    \    /  \

    NULL NULL NULL NULL

  */

  

  

  root->left->left  = newNode(4);

  /* 4 becomes left child of 2

           1

       /       \

      2          3

    /   \       /  \

   4    NULL  NULL  NULL

  /  \

NULL NULL

*/

  

  getchar();

  return 0;

}




TIPE - TIPE BINARY TREE




Full Binary Tree




Binary Tree penuh jika setiap node memiliki 0 atau 2 anak. Berikut ini adalah contoh pohon biner penuh. Kita juga dapat mengatakan pohon biner penuh adalah pohon biner di mana semua simpul kecuali daun memiliki dua anak.




 18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40

             18
           /    \   
         15     20    
        /  \       
      40    50   
    /   \
   30   50

               18
            /     \  
          40       30  
                   /  \
                 100   40




Dalam Full Binary, jumlah node daun adalah jumlah node internal ditambah 1         L = I + 1 Di mana L = Jumlah node daun, I = Jumlah node internal Lihat Handshaking Lemma and Tree untuk bukti.




Complete Binary Tree

Pohon Biner adalah Pohon Biner lengkap jika semua level terisi penuh kecuali mungkin level terakhir dan level terakhir memiliki semua kunci yang tersisa sebanyak mungkin Berikut ini adalah contoh Pohon Biner Lengkap

   18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40
     /  \   /
    8   7  9 







Perfect Binary Tree

Binary tree adalah Binary Tree Sempurna di mana semua node internal memiliki dua anak dan semua daun berada pada level yang sama.

Berikut ini adalah contoh Pohon Biner Sempurna.

    18
           /       \  
         15         30  
        /  \        /  \
      40    50    100   40


               18
           /       \  
         15         30  

Pohon Biner Sempurna dengan tinggi h (di mana tinggi adalah jumlah node pada jalur dari akar ke daun) memiliki simpul 2h - 1.

Contoh pohon biner sempurna adalah leluhur dalam keluarga. Jaga agar seseorang tetap di akar, orang tua sebagai anak-anak, orang tua dari orang tua sebagai anak-anak mereka.

Balanced Binary Tree

Pohon biner seimbang jika ketinggian pohon adalah O (Log n) di mana n adalah jumlah node. Sebagai contoh, pohon AVL mempertahankan tinggi O (Log n) dengan memastikan bahwa perbedaan antara ketinggian sub pohon kiri dan kanan paling tinggi 1. Pohon Merah-Hitam mempertahankan tinggi O (Log n) dengan memastikan bahwa jumlah simpul Hitam pada setiap jalur akar ke daun sama dan tidak ada simpul merah yang berdekatan. Pohon-pohon Pencarian Biner Seimbang adalah kinerja yang baik karena mereka menyediakan O (log n) waktu untuk pencarian, masukkan dan hapus.

A degenerate (or pathological) tree 

Pohon tempat setiap simpul internal memiliki satu anak. Pohon-pohon seperti ini memiliki kinerja yang sama dengan daftar tertaut.

   10
      /
    20
     \