hash dan tree table

Hash Table and Tree
Trees dan Binary tree:
Tree

pemograman Tree adalah Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon. Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya. 

Ada Beberapa Jenis TREE di antaranya :

BINARY TREE

Tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua sub pohon dan kedua subpohon harus terpisah.

Kelebihan struktur Binary Tree :

–          Mudah dalam penyusunan algoritma sorting

–          Searching data relatif cepat

–          Fleksibel dalam penambahan dan penghapusan data

FULL BINARY TREE

Semua node, kecuali leaf pasti memiliki 2 anak dan tiap subpohon memiliki panjang path yang sama.

COMPLETE BINARY TREE

 Tree yang mirip dengan full binary tree, tapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node (kecuali leaf) memiliki 2 anak.

SKEWED BINARY TREE

Binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak.

Contoh Pemograman Tree Sederhana di C++

#include<stdio.h>
typedef struct node{
char data;
node *kiri;
node *kanan;
};

node *akar=NULL;
addNode(node **akar, char isi) {
if((*akar)==NULL){
node *baru;
baru= new node;
baru->data = isi;
baru->kiri = NULL;
baru->kanan = NULL;
(*akar)=baru;
}
}

preOrder(node *akar) {
if(akar !=NULL) {
printf(“%c “, akar->data);
preOrder(akar->kiri);
preOrder(akar->kanan);
}
}

inOrder(node *akar) {
if(akar !=NULL) {
inOrder(akar->kiri);
printf(“%c “, akar->data);
inOrder(akar->kanan);
}
}

postOrder(node *akar) {
if(akar !=NULL) {
postOrder(akar->kiri);
postOrder(akar->kanan);
printf(“%c “, akar->data);
}
}

Hash and Hashing table:

Hash table merupakan 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.Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. 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).

Source code hash table dengan linked list:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_TABLE 5 // size of table
#define MAX_KEY 8 // include null
#define MAX_DATA 12 // num of datas for hash table
#define DELETE_COUNT 6 // num of datas for deletion
#define FIND_COUNT 8 // num of datas for finding

struct Node {
 char key[MAX_KEY];
 int value;
 Node * next;
};

Node * tb[MAX_TABLE]; // hash table
char keys[MAX_DATA][MAX_KEY]; // keys
int values[MAX_DATA]; // values