Hash and binary tree

Hashing and Hash Tables, Trees & Binary Tree 

Hashing and Hash Table
Tabel hash adalah tabel tempat kita menyimpan string asli. Indeks tabel adalah kunci hash, sementara nilainya adalah string asli. Ukuran tabel hash biasanya beberapa kali lipat lebih rendah dari jumlah total string yang mungkin Jadi, beberapa string mungkin memiliki kunci yang sama.

Contoh :
kita mempunyai 3 string dengan isi "nama","jurusan",dan "idsiswa" dengan size 20. Maka, fungsi hash yang akan kita gunakan adalah mengubah karakter pertama dari setiap string menjadi angka antara 0..19.

h[ ]	Value
0	idsiswa
1
2	jurusan
3
4	nama
sampai size 19

maka, idsiswa disimpan di h[0] karena i terdapat di index 0.

jurusan disimpan di h[2] karena j terdapat di index 2, dan seterusnya.

Fungsi Hash yang biasa digunakan : 

1. Division

Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan.

2. Mid-Square
adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus.

3. Folding
Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

Tree dan Binary Tree

Tree merupakan kumpulan dari satu node atau lebih. 

Di dalam Tree terdapat : 

1. Prodecessor : node yang berada diatas node tertentu.
2. Successor : node yang berada di bawah node tertentu.
3. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
5. Parent : predecssor satu level di atas suatu node.
6. Child : successor satu level di bawah suatu node.
7. Sibling : node-node yang memiliki parent yang sama dengan suatu node.
8. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
9. Size : banyaknya node dalam suatu tree.
10. Height : banyaknya tingkatan/level dalam suatu tree.
11. Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
12. Leaf : node-node dalam tree yang tak memiliki seccessor.
13. Degree : banyaknya child yang dimiliki suatu node

Binary Tree merupakan struktur data potoh yang di rootnya memiliki paling banyak dua child.

contoh implementasi binary tree 

1. #include <stdio.h>

2. #include <malloc.h>

4. struct node {

5.     struct node * left;

6.     char data;

7.     struct node * right;

8. };

10. struct node *constructTree( int );

11. void inorder(struct node *);

13. char array[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' };

14. int leftcount[ ] = {  1,   3,   5,   -1,   9,  -1,  -1,   -1,   -1,  -1 };

15. int rightcount[ ] = {  2,   4,   6,   -1,  -1,  -1,  -1,   -1,   -1,  -1 };

17. void main() {

18.     struct node *root;

19.     root = constructTree( 0 );

20.     printf("In-order Traversal: \n");

21.     inorder(root);

22. }

24. struct node * constructTree( int index ) {

25.     struct node *temp = NULL;

26.     if (index != -1) {

27.         temp = (struct node *)malloc( sizeof ( struct node ) );

28.         temp->left = constructTree( leftcount[index] );

29.         temp->data = array[index];

30.         temp->right = constructTree( rightcount[index] );

31.     }

32.     return temp;

33. }

35. void inorder( struct node *root ) {

36.     if (root != NULL) {

37.         inorder(root->left);

38.         printf("%c\t", root->data);

39.         inorder(root->right);

40.     }

41. }