BINARY SEARCH TREE (BST)
Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
Ciri-ciri dalam binary searcy tree (bst) :
Dalam Binary Search Tree ada subtree kiri dan subtree kanan. Sebuah binary search tree (bst) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing – masing subpohon tersebut (kiri&kanan) itu sendiri adalah juga bst.
Binary Search tree memfasilitasi operasi utama seperti search, insert, dan delete.
Delete menjadi yang paling kompleks memiliki banyak kasus, misalnya, simpul no child, simpul dengan one child, dan simpul dengan two child.
Algoritma ini digunakan dalam solusi dunia nyata seperti game, data autocomplete, dan grafik.
Aturan main Binary Search Tree :
Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.
Lalu, ada 3 jenis cara untuk melakukan penelusuran data pada BST :
PreOrder : Print data, telusur ke kiri, telusur ke kanan
InOrder : Telusur ke kiri, print data, telusur ke kanan
Post Order : Telusur ke kiri, telusur ke kanan, print data
Saturday, 21 March 2020
HASHING TABLE AND BINARY TREE
HASHING TABLE
Hashing adalah metode yang efisien untuk menyimpan dan mengambil elemen. Persis sama dengan halaman indeks buku. Di halaman indeks, setiap topik dikaitkan dengan nomor halaman. Jika kita ingin melihat beberapa topik, kita bisa langsung mendapatkan nomor halaman dari indeks.
Demikian juga, dalam hashing setiap nilai akan dikaitkan dengan kunci. Dengan menggunakan kunci ini, kita dapat menunjukkan elemen secara langsung.
Hash Table adalah struktur data yang menyimpan data secara asosiatif. Dalam tabel hash, data disimpan dalam format array di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data menjadi sangat cepat, jika kita mengetahui indeks dari data yang diinginkan.
Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.
Operasi Pada Hash Tabel
Insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key lalu hapus nilainya
getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu.
Implementasi Program C Hash Table :
#include<stdio.h>
#define size 7
int arr[size];
void init()
{
int i;
for(i = 0; i < size; i++)
arr[i] = -1;
}
void insert(int value)
{
int key = value % size;
if(arr[key] == -1)
{
arr[key] = value;
printf("%d inserted at arr[%d]\n", value,key);
}
else
{
printf("Collision : arr[%d] has element %d already!\n",key,arr[key]);
printf("Unable to insert %d\n",value);
}
}
void del(int value)
{
int key = value % size;
if(arr[key] == value)
arr[key] = -1;
else
printf("%d not present in the hash table\n",value);
}
void search(int value)
{
int key = value % size;
if(arr[key] == value)
printf("Search Found\n");
else
printf("Search Not Found\n");
}
void print()
{
int i;
for(i = 0; i < size; i++)
printf("arr[%d] = %d\n",i,arr[i]);
}
int main()
{
init();
insert(10); //key = 10 % 7 ==> 3
insert(4); //key = 4 % 7 ==> 4
insert(2); //key = 2 % 7 ==> 2
insert(3); //key = 3 % 7 ==> 3 (collision)
printf("Hash table\n");
print();
printf("\n");
printf("Deleting value 10..\n");
del(10);
printf("After the deletion hash table\n");
print();
printf("\n");
printf("Deleting value 5..\n");
del(5);
printf("After the deletion hash table\n");
print();
printf("\n");
printf("Searching value 4..\n");
search(4);
printf("Searching value 10..\n");
search(10);
return 0;
}
BINARY TREE
Binary Tree
adalah jenis struktur data di mana setiap node memiliki paling banyak dua anak
(anak kiri dan anak kanan). Pohon biner digunakan untuk mengimplementasikan
pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian dan
penyortiran yang efisien. Pohon biner adalah kasus khusus dari pohon K-ary, di
mana k adalah 2. Operasi umum untuk pohon biner termasuk penyisipan,
penghapusan, dan traversal. Kesulitan melakukan operasi ini bervariasi jika
pohon seimbang dan juga apakah simpulnya adalah simpul daun atau simpul cabang.
Untuk pohon seimbang, kedalaman sub pohon kiri dan kanan setiap node berbeda 1
atau kurang. Ini memungkinkan kedalaman yang dapat diprediksi juga dikenal
sebagai ketinggian. Ini adalah ukuran dari simpul dari akar ke daun, di mana
akar adalah 0 dan simpul berikutnya adalah (1,2..n). Ini dapat diekspresikan
oleh bagian integer dari log2 (n) di mana n adalah jumlah node di pohon.
g s 9
/ \ / \ / \
b m f u 5 13
/ \ / \ / \
c d t y 11 15
Operasi yang dilakukan pada pohon memerlukan pencarian di salah satu dari dua cara utama: Pencarian Kedalaman Pertama dan pencarian Breadth-first. Depth-first search(DFS) adalah algoritma untuk melintasi atau mencari struktur data pohon atau grafik. Satu dimulai pada root dan mengeksplorasi sejauh mungkin sepanjang masing-masing cabang sebelum mundur. Ada tiga jenis penelusuran penelusuran kedalaman pertama: kunjungan sebelum pemesanan, kiri, kanan, kiri berurutan, kunjungan, kanan, kiri pasca pesanan, kanan, kunjungan.
Breadth-first search (BFS) adalah algoritma untuk melintasi atau mencari struktur pohon atau grafik. Dalam level-order, tempat kami mengunjungi setiap node pada level sebelum pergi ke level yang lebih rendah.
Conton Program C Yang Umum Pada Binary Tree
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node* left;
struct node* right;
};
struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insert(struct node* root, int data)
{
if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
void inorder(struct node* root){
if(root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}
int main(){
struct node *root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 1);
insert(root, 6);
insert(root, 7);
insert(root, 10);
insert(root, 14);
insert(root, 4);
inorder(root);
}
STACK AND QUEUE
STACK
Stack merupakan jenis linked list yang menerapkan konsep LIFO (Last In Fist Out) artinya elemen dari struktur (node) yang dimasukkan pertama kali ke dalam rangkaian akan dikeluarkan (diproses) terakhir kali sedangkan elemen yang masuk terakhir akan diproses / dikeluarkan pertama. Dengan kata lain setiap transaksi atau aktifitas yang ada dalam stack dilakukan pada kepalanya (head) saja. Pada stack hanya ada 2 fungsi utama yaitu Push atau menambah/memasukkan node (struktur) ke dalam stack, dan Pop atau mengeluarkan/menghapus node dari stack.
cara kerja stack dapat di ilustrasikan sebagai berikut:
| D | ---> atas
| C |
| B |
| A | ---> bawah
Anggaplah gambar diatas sebagai tumpukan data, D sebagai node(struktur) yang atas (terkhir dimasukkan) dan A sebagai node yang bawah (pertamakali dimasukkan). Jika kita melakukan operasi Push (menambah), misalnya E, maka penambahan akan dilakukan pada nilai yang paling atas, yaitu D, sehingga menjadi
| E | ---> atas
| D |
| C |
| B |
| A | ---> bawah
Sehingga nilai E menjadi nilai atas yang baru, dan jika dilakukan operasi pop, maka stack akan menjadi seperti gambar yang pertama diatas, yaitu nilai D menjadi nilai atas, dan nilai E akan dihapus dari tumpukan (stack).
Contoh kodingan yang paling umum
#include <stdio.h>
#define MAX 5
int top;
/*Fungsi PUSH*/
void push (int stack[], int item)
{
if (top == (MAX-1))
printf("\nStack Full");
else
{
++top;
stack [top] = item;
}
}
/*Fungsi POP*/
int pop (int stack[])
{
int ret;
if (top == -1)
{
ret = 0;
} else {
ret = stack [top];
--top;
}
return ret;
}
/*Fungsi Display*/
void display (int stack[])
{ int i;
printf ("\nIsi Stack: ");
if (top == -1){
printf ("\nStack Kosong\n\n");
} else {
for (i=top; i>=0; --i)
printf ("\n--------\n|%3d |\n--------", stack[i]);
}
printf ("\n");
}
/*Main Program*/
int main()
{
int stack[MAX], item;
int pilihan;
top = -1;
do
{
do
{
printf ("MAIN MENU\n");
printf ("1.Push / Insert Stack\n");
printf ("2.POP / Delete Stack\n");
printf ("3.Exit\n");
printf ("Pilihan: ");
scanf ("%d", &pilihan);
if (pilihan<1 || pilihan>3)
printf ("\nPilhan Salah, Silahkan Ulangi Lagi.");
} while (pilihan<1 || pilihan>3);
switch (pilihan)
{
case 1:
printf ("\nElemen Push : ");
scanf ("%d", &item);
push (stack, item);
display (stack);
break;
case 2:
item = pop (stack);
if(item == 0){
printf("\nStack Kosong\n\n");
} else {
display (stack);
}
break;
default:
printf ("\nExit");
}
} while(pilihan != 3);
return 0;
}
QUEUE
Queue merupakan jenis Linked list yang menerapkan konsep FIFO (First In First Out) atau kebalikan dari Stack (LIFO). pada Queue elemen yang dimasukkan pertama kali apabila dilakukan pemrosesan makan elemen tersebut yang akan diproses terlebih dahulu. ilustrasinya seperti saat kita akan membeli tiket di Bioskop, disitu orang yang datang untuk mengantri pertama kali akan dilayani terlebih dahulu dan yang mengantri terakhir akan dilayani terakhir.
Fungsi dasar queue sebagai berikut :
- Menginisialisasi queue menjadi empty queue.
- Menentukan / memastikan apakah queue dalam keadaan penuh ( is full) atau kosong (is Empty).
- Apabila queue belum penuh, maka data baru akan insert ke pada bagian ujung pangkal queue, dan jika queue kososng, maka remove dari data bagian ujung depan queue.
Terdapat 2 Operasi dasar dari Queue:
- Enqueue: proses penambahan elemen di posisi belakang
- Dequeue: proses pengambilan elemen di posisi depan Selain operasi dasar di atas,
Contoh kodingan queue paling umum dalam bahasa C
#include <stdio.h>
#define MAX 10
typedef struct
{
int Item [MAX];
int Front;
int Rear;
int Count;
}
Queue;
void Inisialisasi(Queue *q)
{
q->Front = q->Rear = -1;
q->Count = 0;
}
void Tambah (Queue *q, int item)
{
if ((q->Rear == MAX-1 && q->Front == 0) || (q->Rear + 1 == q->Front))
{
printf ("\nAntrian Penuh");
return;
}
if (q->Rear == MAX - 1)
q->Rear = 0;
else
q->Rear++;
q->Item[q->Rear] = item; q->Count++;
if (q->Front == -1) q->Front = 0;
}
int Hapus (Queue *q)
{
int data ;
if (q->Front == -1)
{
printf("\nAntrian Kosong");
return NULL;
}
else
{
data = q->Item[q->Front];
q->Count--;
if (q->Front == q->Rear)
q->Front = q->Rear = -1;
else
{
if (q->Front == MAX-1)
q->Front = 0;
else
q->Front++;
}
}
return data;
}
void Tampil(Queue *q)
{
for(int i=0; i<q->Count; i++)
printf("\nData : %d", q->Item[i]);
}
main()
{
Queue q;
int data;
Inisialisasi (&q);
Tambah (&q,11);
Tambah (&q,12);
Tambah (&q,13);
Tambah (&q,14);
Tambah (&q,15);
Tambah (&q,16);
Tambah (&q,17);
Tambah (&q,18);
Tambah (&q,19);
Tambah (&q,20);
Tambah (&q,21);
Tampil (&q);
data = Hapus(&q);
printf("\nHapus Item = %d ", data); data = Hapus(&q);
printf("\nHapus Item = %d ", data); data = Hapus(&q);
printf("\nHapus Item = %d ", data); Tampil(&q);
}
LINKED LIST
Linked List
Linked List atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.
- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
- Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list
Link list adalah sebuah rangkaian struktur sejenis (bertipe sama) yang dihubungkan dengan menggunakan salah satu (beberapa) field yang bertipe pointer. Untuk dapat memahaminya ,perhatikan pendefinisian struktur di bawah ini.
struct node{
int info;
struct node* next;
} node;
Di atas kita memiliki sebuah struktur dengan nama node, dimana di dalamnya terdapat dua buah field, yaitu info(bertipe int) dan next (bertipe pointer ke struktur node). Field info akan digunakan untuk menyimpan nilai, sedangkan pointer next digunakan untuk menyimpan alamat dari struktur node lainnya yang terdapat dalam rangkaian.
Ada beberapa macam Linked List, yaitu :
Single List
artinya node-node tersebut saling terhubung satu sama lain. Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
contoh codingannya :
struct Mahasiswa{
char nama[25];
int usia;
struct Mahasiswa *next;
}*head,*ta
Double Linked List
Double Linked List adalah jenis linked list yang berisi pointer ke berikutnya serta node sebelumnya dalam urutan yang lebih kompleks, oleh karena itu, terdiri dari tiga bagian yaitu : data, pointer ke node berikutnya, dan pointer ke sebelumnya.
contoh codingannya :
struct Mahasiwa{
char nama[25];
int usia;
struct Mahasiswa *next,*prev;
}*head,*tail;
Circular Double Linked List
Merupakan double linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Subscribe to:
Comments (Atom)