Binary Search Tree

Sebelum kita masuk kedalam pengertian Binary Search Tree(BST) saya akan menjelaskan kembali apa sih Binary Tree itu? Binary Tree adalah pohon yang dimana setiap simpulnya hanya boleh memiliki dua anak/subtree kedua anak/subtree tersebut HARUS terpisah. Kegunaan dari binary tree ini sendiri adalah untuk mengurutkan data-data yang disusun secara ascending(dari kecil ke besar) maupun descending(dari besar ke kecil).

Sekarang kalian telah mengetahui apa itu Binary Tree, selanjutnya adalah Binary Search Tree(BST). Sebenarnya BST tidak berbeda dengan Binary Tree, Binary Search Tree atau biasa kita sebut dengan BST adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap child 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.

Operasi-operasi yang terdapat dalam BST:

• find(x) : untuk menemukan elemen x dalam BST.
• insert(x) : untuk memasukan elemen baru x dalam BST.
• remove(x) : untuk mengeluarkan/mendelete elemen x dalam BST.

Sekarang saya akan memberitahu kalian tentang aturan dalam memasukan/menginsert key dalam BST:

1. Untuk root, kita bisa langsung memasukannya tanpa masalah.
2. Untuk child, jika child yang kita masukkan nilainya lebih kecil daripada parent maka nilai tersebut akan dimasukan kedalam cabang/subtree kiri dan sebaliknya jika nilainya lebih besar daripada parent maka nilai tersebut akan dimasukkan kedalam cabang/subtree kanan.

untuk bagian deletion merupakan hal yang menurut saya lumayan ribet dan susah karena memiliki banyak sekali syarat.

contoh : 

25

/     \

20      30

/           \

10          45

Jika kita mau menghapus leaf(bagian dimana dia tidak memiliki cabang lagi biasanya berada di bagian paling bawah). Kita dapat langsung mendelete bagian tersebut dengan cara remove(45)/remove(10) nanti key tersebut akan langsung dibuang.

Tetapi yang membuat BST menjadi susah adalah jika kita ingin mendelete key yang masih memiliki cabang. Nah cara untuk mendeletenya adalah kita harus menggantikan key dengan leaf. contohnya:

55

/     \

30      70

/  \       \

10  40     85

Jika kita ingin menghapus key yang memiliki cabang kita harus menggantikannya dengan cabang yang memiliki nilai lebih besar. misalnya kita mau mendelete key 70 maka, remove(70) kemudian diganti dengan childnya yaitu 85.

Jika kita ingin mengganti root maka kita harus mengganti root dengan child yang memiliki nilai paling besar dari cabang root kiri berarti kita harus memilih cabang yang kanan dalam child kiri.

misalnya remove(55) lalu kita ganti dengan child kana dari cabang kiri sehingga root yang baru adalah 40.

berikut adalah contoh source code BST

#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 atas perhatiannya, jika ada yang kurang jelas atau kurang materinya, tolong langsung saja komen dibawah 😁. 

Nama : Reinhart Perbowo Pujo Leksono

NIM : 2301857254

Source : 

- https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

- powerpoint Data Structure di Binusmaya.