Binary Search Tree (BST)
Kenapa harus membedakan
kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi
terhadap proses searching. Jika 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
-
PostOrder : Telusur ke kiri, telusur ke
kanan, print data
OPERATIONS
Pada dasarnya operasi
dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi
insert, update, dan delete.
1. Insert
: Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang
tepat. (Lokasi tidak ditentukan oleh user sendiri).
2. Update
: Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada
posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree
tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada
tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap
menjadi Binary Search Tree.
3. Delete
: Seperti halnya update, delete dalam Binary Search Tree juga turut
mempengaruhi struktur dari tree tersebut.
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();
}
Sumber :
Comments
Post a Comment