Hashing Table & Binary Tree

Hashing

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.

Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut hash function.

Hash Table

Tabel hash adalah tabel tempat menyimpan string asli. Indeks tabel adalah kunci hash dan nilainya adalah string asli. Ukuran tabel hash biasanya berupa urutan yang besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki kunci hash yang sama.

Hash Function

Ada beberapa cara untuk membuat fungsi hash. 

1. Mid-Square

a. Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.

b. Jika kuncinya adalah string, maka akan dikonversi ke angka.

2.Division

a. Membagi string / pengidentifikasi dengan menggunakan operator modulus.

b. Divison merupakan metode hashing integer yang paling sederhana.

3.Folding

Cara melakukan folding yaitu, buat string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash.

4.Digit Extraction

Pada metode ini, Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

5.Rotating Hash

a. Gunakan metode hash mid-square.

b. Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi.

c. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Tree

Tree merupakan struktur data non-linear yang mewakili hubungan hierarkis(one to many) di antara objek data. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop. Contoh:

1. Node di atas disebut sebagai root.
2. Garis yang menghubungkan induk ke anak adalah edge.
3. Node yang tidak memiliki anak disebut leaf.
4. Node yang memiliki orang tua yang sama disebut sibling.
5. Degree dari simpul adalah total sub tree dari simpul.
6. Height/Depth adalah tingkat maksimum node dalam tree.
7. Jika ada garis yang menghubungkan p ke q, maka p disebut ancestor dari q, dan q adalah descendant dari p.

Binary Tree

Binary tree adalah struktur data rooted tree di mana setiap node memiliki paling banyak dua anak.

Macam-macam binary tree:

1. Perfect binary tree adalah pohon biner di mana setiap level berada pada depth yang sama.
2. Complete adalah pohon biner di mana setiap level kecuali yang terakhir terisi penuh dan semua node diletakkan sejauh mungkin. Perfect binary tree juga merupakan Complete binary tree.
3. Skewed binary tree adalah pohon biner di mana setiap node memiliki paling banyak satu anak.
4. Balanced binary tree adalah pohon biner dimana tidak ada leaf yang lebih jauh dari root daripada leaf lainnya.

Konsep binary tree

• Jumlah maksimum node pada level k dari pohon biner adalah 2k.
• Jumlah maksimum node pada pohon biner dengan tinggi h adalah 2^h+1 - 1.
• Ketinggian pohon adalah jumlah level atau level tertinggi h.
• Tinggi minimum pohon biner dari n node adalah 2log (n).
• Tinggi maksimum pohon biner dari n node adalah n - 1.

Expression Tree

Prefix  : *+ab/-cde

Postfix : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Expression tree dapat dibuat dari prefix dengan rekursif.

Struktur Tree yang digunakan:

struct tnode {

  char chr;

  struct tnode *left;

  struct tnode *right;
};

main function

struct tnode *root = newnode(s[0]);

f(root);

char s[MAX];

int  p = 0;

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);}}

Prefix Traversal

void prefix(struct tnode *curr) {

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

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

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

Postfix Traversal

void postfix(struct tnode *curr) {

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

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

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

Infix Traversal

void infix(tnode *curr) {

if ( is_operator(curr->chr) ) putchar( '(' );

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

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

if ( curr->right != 0 ) infix(curr->right);

if ( is_operator(curr->chr) ) putchar( ')' );}

Threaded Binary Tree

Threaded Binary Tree hampir sama dengan pohon biner, namun berbeda dalam menyimpan pointer NULL. Jika thread muncul di bidang kiri disebut left threaded binary tree. Sebaliknya, jika thread muncul di bidang kanan disebut right threaded binary tree. Selain itu, ada juga two way threaded binary tree dimana setiap node di-threaded ke arah pendahulu dan penggantinya secara berurutan (kiri dan kanan) berarti semua pointer nol kanan akan mengarah ke penerus inorder DAN semua pointer nol kiri akan menunjuk ke inorder pendahulu.

Kelebihan Threaded Binary Tree

1. memungkinkan lintasan linier elemen pada pohon.
2. menghilangkan penggunaan tumpukan yang menghabiskan banyak ruang memori dan waktu komputer.
3. memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer orangtua secara eksplisit.