Hashing, Hashing Tables and Binary Trees

Hashing, Hashing Tables and Binary Trees

Hashing

hashing adalah suatu teknik untuk menyimpan dan menemukan kunci secara cepat dengan cara mengubah string menjadi kunci yang lebih pendek.

Metode:

- MidSquare: hashing dengan cara menkuadratkan nilai dari key dan mengambil nilai tengah dari hasil tersebut.
- Division: Hashing dengan cara menggunakan sisa bagi dari kunci.
- Folding: Hashing dengan cara membelah key lalu menjumlahkan keduanya dan mengambil dua digit terakhir.
- Digit Extraction: Hashing dengan cara mengambil nilai dari beberapa index tertentu dari kunci.
- Rotating Hash: Hashing ini dapat menggunakan metode hashing apapun lalu melakukan pergerakan nilainya agar mendapatkan nilai baru.

Collision

Apabila terjadi string dengan hash key yang sama maka terdapat beberapa cara untuk menanganinya:
- linear Probing: Mencari slot kosong berikutnya
- Chaining: menggunakan linked list untuk mengikatnya.

Tree

Data stucture yang memiliki banyak node dan setiap nod maksimal memiliki 2 node.
Setiap node memiliki link parent, left, dan right.

Expression tree:

Membuat expression tree dari sebuah prefix menggunakan rekurif

void f(struct tnode *curr) {

  if ( is_operator(s[p]) ) {

  p++; curr->left  = newnode(s[p]);

  f(curr->left);

  p++; curr->right = newnode(s[p]);

  f(curr->right);

  }
}

(untuk menjelaskan algoritma diatas menggunakan rekursif agar apabila node adalah sebuah operator aritmatika maka akan memanggil dirinya sendiri hingga operaator terakhir lalu kembali)

Algoritma membuat prefix dari expression tree:

void prefix(struct tnode *curr) {

  printf( “%c “, curr->chr );

  if ( curr->left  != 0 ) prefix(curr->left);

  if ( curr->right != 0 ) prefix(curr->right);
}

Algoritma membuat postfix dari expression tree:

void postfix(struct tnode *curr) {

    if ( curr->left  != 0 ) postfix(curr->left);

    if ( curr->right != 0 ) postfix(curr->right);
    printf( “%c“, curr->chr );

}