Hashing and Binary tree

HASHING

Hashing adalah suatu teknik untuk menyimpan dan menemukan kunci secara cepat dengan  mengubah string menjadi kunci yang lebih pendek.
Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

Hash Table

Tabel hash adalah tabel  tempat  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.

Dalam Hash table, ada beberapa feature / support yang bisa digunakan, yaitu:

1. Search

2. Insert

3. Delete

Salah satu contoh koding yang menggunakan feature insert:

void insert(int key, int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));

   item->data = data;  

   item->key = key;

   int hashIndex = hashCode(key);

   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {

      ++hashIndex;

      hashIndex %= SIZE;

   }

   hashArray[hashIndex] = item;

}

BINARY TREE

Binary tree struktur data menyerupai pohon guna menyimpan data. Syarat dari suatu binary tree adalah bahwa setiap node nya hanya boleh maksimal 2 anak.

Terdapat 3 jenis binary tree yaitu:

• Full Binary Tree:
  Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
• Complete Binary Tree:
  Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
• Skewed Binary Tree:
  yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.