Struktur Data – Binary Search Tree (BST)

30 December 2016  Comments Struktur Data , Tutorial C

Mahir Koding – Sebelum mengenal lebih jauh tentang Binary Search Tree, ada baiknya kita membahas struktur data Tree terlebih dahulu. Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.

Lalu, ada lagi yang namanya Binary Tree. Apa bedanya? Sebenarnya sama sama konsepnya dengan Tree. Hanya saja, kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0 (2 pilihan). Berarti, binary tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja. Untuk lebih jelasnya, lihat gambar di bawah ini.

Lanjut lagi, sekarang kita akan memasuki pembelajaran intinya yaitu 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();
}

Source code secara lengkap bisa dicek ke github saya, di link ini.

Jika ada pertanyaan yang kurang jelas silahkan berkomentar di bawah. Atau, jika ingin request tutorial juga dapat ke halaman ini. Dukung terus Mahir Koding agar dapat selalu mengupdate artikel dengan share dan like artikel ini. Terima Kasih.