AVL DAN B-TREE

Pada kesempatan kali ini saya akan membahas tentang AVL dan B-TREE .

AVL

AVL merupakan kepanjangan dari Adelson Veleskii Landis Tree. AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan.

AVL tree digunakan dalam binary search tree untuk menyeimbangkan dan menyederhanakan BST agar mudah untuk dicari, BST yang selisih Heightnya kurang dari -1 dan lebih dari 1 akan memerlukan Balancing.

Balancing memiliki beberapa kondisi, yaitu:

1. Jika ada Unbalance pada anak kiri subtree kanan, maka dapat dilakukan rotasi kiri-kanan.
2. Jika ada Unbalance  pada anak kiri subtree kiri, maka dapat dilakukan rotasi kanan.
3. Jika ada Unbalance  pada anak kanan subtree kanan, maka dapat dilakukan rotasi kiri.
4. Jika ada Unbalance  pada anak kanan subtree kiri, maka dapat dilakukan rotasi kanan-kiri.

Insert AVL TREE

Ada 4 kasus yang biasanya terjadi saat operasi insert dilakukan, yaitu :

1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)
2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)
3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)
4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

      T adalah node yang harus diseimbangkan kembali.

 4 kasus tersebut dapat diselesaikan dengan melakukan rotasi yaitu:
 Kasus 1 dan 2 dengan single rotation

       Kasus 3 dan 4 dengan double rotation.

Delete AVL TREE

Deletion dalam AVL Tree sama seperti teknik deletion dalam binary search tree yang tidak seimbang.

Ada 2 kasus yang biasanya terjadi saat operasi delete dilakukan yaitu 
Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Binary Search Tree dengan perbedaan tinggi / level maksimal 1.

Anggap T adalah node yang harus diseimbangkan kembali

 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

B-TREE

B-Tree adalah pohon seimbang yang dioptimalkan untuk situasi saat sebagian atau seluruh pohon harus dipertahankan dalam penyimpanan sekunder seperti disk magnetik . Karena akses disk yang mahal ( memakan waktu ) operasi , b-tree mencoba untuk meminimalkan jumlah akses disk . Sebagai contoh, b - tree dengan ketinggian 2 dan faktor percabangan 1001 dapat menyimpan lebih dari satu miliar kunci tetapi membutuhkan paling banyak dua akses disk untuk mencari setiap node.

Karakteristik B-Tree:

1. Semua daun akan dibuat pada level yang sama.
2. B-Tree ditentukan oleh sejumlah derajat, yang juga disebut "urutan" (ditentukan oleh aktor eksternal, seperti programmer), disebut sebagai m 
3. Subtree kiri dari node akan memiliki nilai lebih rendah dari sisi kanan subtree. Ini berarti bahwa node juga diurutkan dalam urutan menaik dari kiri ke kanan.
4. Jumlah maksimum node anak, sebuah simpul root serta simpul turunannya dapat dihitung dengan rumus ini: m-1

Keuntungan menggunakan B-Tree:

1. Mengurangi jumlah pembacaan yang dilakukan pada disk
2. Pilihan yang baik untuk memilih ketika proses reading dan writing pada blok data yang besar
3. B Tree dapat dengan mudah dioptimalkan untuk menyesuaikan ukurannya (yaitu jumlah node anak) sesuai dengan ukuran disk
4. Ini adalah teknik yang dirancang khusus untuk menangani sejumlah besar data.
5. Algoritma yang paling tepat untuk database dan sistem file.

Insert

Syarat insertion yaitu:

·        Pertama tentukan dahulu dimana key akan diletakkan menggunakan algoritma search,        key pasti ditempatkan pada node leaf.

·        Jika node tadi adalah 2-node, maka letakkan saja key tersebut disitu.

·        Jika nodenya adalah 3-node, maka jadikan data tengah dari key, A, dan B

Delete

Syarat Deletion yaitu:

·         Tentukan di node mana data yang ingin dihapus,

·         Jika berada dalam 3-node, langsung hapus saja datanya.

·         Jika berada dalam 2-node :

• 
  

  Jika parent adalah 3-node : ambil satu data dari parent.Jika sibling adalah 3-node, ambil salah satu data nya untuk  dijadikan data pada parent (agar parent menjadi 3-node lagi).Jika sibling adalah 2-node, buat parent menjadi 2-node dengan menggabungkan (merge) sibling dengan node tempat data didelete. 
• Jika parent adalah 2-node : Jika sibling adalah 3-node, turunkan data parent ke node dan ambil satu data dari sibling untuk menggantikan parent. Jika sibling 2-node, gabungkan sibling dengan node yang dihapus datanya.       

BST

Binary Search Tree atau sering disingkat BST. Apalagi BST itu? Dan apa bedanya dengan yang dua diatas? Sebenarnya mirip-mirip saja, 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.

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

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 (traversal) 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

Berikut adalah contoh implementasi Binary Search Tree pada C beserta searching datanya :

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

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar();
}

RANGKUMAN

Disini saya mau membuat rangkuman dari materi yang telah saya buat.

Linked List merupakan koleksi linear dari data, yang disebut sebagai nodes, dimana setiap node akan menunjuk pada node lain melalui sebuah pointer. Linked List dapat didefinisikan pula sebagai kumpulan nodes yang merepresentasikan sebuah sequence.

Ada beberapa macam Linked List, yaitu  :

1. Single Linked List
2. Double Linked List
3. Circular Linked List
4. Multiple Linked List

SINGLE LINKED LIST

Sebuah linked list yang hanya memiliki 1 penghubung ke node lain.

DOUBLE LINKED LIST

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

CIRCULAR LINKED LIST

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL. 

Ada 2 jenis Circular Linked List, yaitu :

1. Circular Single Linked List

2. Circular Double Linked List

MULTIPLE LINKED LIST

Multiple Linked List merupakan suatu linked list yang memiliki lebih dar 2 buat variabel pointer.

Hash Table adalah sebuah struktur data yang terdiri atas sebuah table dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap recor(baris) menjadi angka(hash) lokasi record tersebut dalam sebuah table.

     Ada beberapa fungsi hash untuk mengubah string menjadi key:

1. Mid-square
2. Division (most common)
3. Folding
4. Digit Extraction
5. Rotating Hash

     Implementasi hashing table in blockchain

     Hashing table memiliki peranan dalam menajga keamanan data atau disebut crypthographic dan hubungannya dengan blockchain adalah blockhain merupakan catatan traksaksi digital yang dihubungkan dari individu dan dihubungkan ke daftar. Sehingga blockchain sangat memerlukan hashing table untuk menjaga keamanan datanya.

     Salah satu contoh teknologi yang menggunakan blockchain adalah bitcoin. Fungsi dari hash di dalam bitcoin adalah untuk menambahkan data baru ke dalam blockchain dengan cara menambang. Sehingga hash berperan penting agar data yang sedang diproses menjadi lebih aman karena prosesnya yang lama.

      Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkir(hubungan one to many) antar elemen. Tree juga bisa disimpulkan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubung satu sama lain(subtree).

     Binary Tree merupakan tree yang memiliki hanya 2 child disetiap nodenya dan tidak boleh kurang.

    Jenis-jenis binary tree:

    

1. Perfect Binary Tree : binary tree  yang setiap level (kedalaman) nya berada di kondisi  yang sama.
2. Complete Binary Tree : suatu pohon biner yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja).
3. Skewed binary Tree :Suatu pohon biner yang setiap nodenya hanya memiliki 1 anak.
4. Balanced Binary Tree : suatu pohon biner yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu.

Binary Search Tree atau sering disingkat BST. Apalagi BST itu? Dan apa bedanya dengan yang dua diatas? Sebenarnya mirip-mirip saja, 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.

Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.

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 (traversal) 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

Berikut adalah contoh implementasi Binary Search Tree pada C beserta searching datanya :

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

//inisialisasi struct
struct data{
 int number;
 //pointer untuk menampung percabangan kiri dan kanan
 data *left, *right;
}*root;

//fungsi push untuk menambah data
void push(data **current, int number){
 //jika pointer current kosong maka akan membuat blok data baru
 if((*current)==NULL){
  (*current) = (struct data *)malloc(sizeof data);
  //mengisi data
  (*current)->number=number;
  (*current)->left = (*current)->right = NULL;
 //jika tidak kosong, maka akan dibandingkan apakah angka yang 
 //ingin dimasukkan lebih kecil dari pada root
 //kalau iya, maka belok ke kiri dan lakukan rekursif 
 //terus menerus hingga kosong
 }else if(number < (*current)->number){
  push(&(*current)->left, number);
 //jika lebih besar, belok ke kanan
 }else if(number >= (*current)->number){
  push(&(*current)->right, number);
 }
}

//preOrder : cetak, kiri, kanan
void preOrder(data **current){
 if((*current)!=NULL){
  printf("%d -> ", (*current)->number);
  preOrder(&(*current)->left);
  preOrder(&(*current)->right);
 }
}

//inOrder : kiri, cetak, kanan
void inOrder(data **current){
 if((*current)!=NULL){
  inOrder(&(*current)->left);
  printf("%d -> ", (*current)->number);
  inOrder(&(*current)->right);
 }
}

//postOrder : kiri, kanan, cetak
void postOrder(data **current){
 if((*current)!=NULL){
  postOrder(&(*current)->left);
  postOrder(&(*current)->right);
  printf("%d -> ", (*current)->number);
 }
}

//searching data
void search(data **current, int number){
 //jika pointer current memiliki data
 if((*current)!=NULL){
  //cek, apakah datanya lebih kecil. Jika iya, belok ke kiri
  if(number<(*current)->number){
   search(&(*current)->left,number);
  //jika lebih besar, maka belok ke kanan
  }else if(number>(*current)->number){
   search(&(*current)->right,number);
  //jika sama dengan, maka angka ketemu
  }else{
   printf("Found : %d", (*current)->number);
  }
 //jika tidak ada data lagi (not found)
 }else{
  printf("Not Found.");
 }
}

void main(){
 push(&root, 11);
 push(&root, 22);
 push(&root, 13);
 push(&root, 15);
 push(&root, 9);
 inOrder(&root);
 printf("\n");
 preOrder(&root);
 printf("\n");
 postOrder(&root);
 printf("\n");
 search(&root,91);
 getchar();
}

TERIMA KASIH TELAH MEMBACA BLOG SAYA.....