Pohon Pencarian Biner aka. Binary Search Tree (BST)

Tulisan ini saya tulis setelah seseorang bertanya atau lebih tepatnya meminta bantuan untuk mengerjakan tugas kuliahnya. sigh, anak muda sekarang memang….(heheh..), tapi mengingat dia sudah cukup bekerja keras kayaknya, dan belum berhasil, jadi kubantu. tugas kuliahnya simple sebenarnya, ini dia soalnya:

Anda   dimintakan  untuk  mengimplementasi   program menggunakan   struktur   data  BST. Program menerima  input  berupa sebuah  file yang pada setiap barisnya  terdapat  sebuah kata, misalnya: would described anyhow stylish be given contains outside nothing would File input tersebut dapat didownload melalui link berikut ini: http://www.math-usk.org/tfa/ds/stopwords.txt Program yang diimplementasi  harus membaca setiap kata dalam  file  tersebut   (baris per baris)  dan memasukkan kata  tersebut  ke dalam BST satu per  satu.  Setelah semua kata dalam file tersebut dimasukkan dalam BST,  telusuri BST tersebut menggunakan metode inorder dan cetak hasilnya dalam sebuah file output. Nama file input dan file output dapat ditulis secara langsung dalam kode program atau dapat pula ditentukan melalui command- line (terserah, mana yang mudah untuk diimplementasikan).

program dalam bahasa pemrograman c.

sebelum menyelesaikan soal itu, mari kita lihat teori binary search tree. anda boleh membaca wikipedia, disana ada penjelasannya, tapi disini saya akan mencoba menjelaskan dengan kalimat saya sendiri

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. lihat gambar:

sebuah bst, pada dasarnya adalah sebuah pohon biner (binary tree), oleh karena itu, kita dapat melakukan traversal pada setiap node dengan metode inorder, preorder maupun postorder. dan jika kita melakukan traversal dengan metode inorder, pada dasarnya kita telah melakukan traversal valuenya secara terurut dari kecil ke besar, jadilah ini sebagai sorting algoritma.

struktur data bst sangat penting dalam struktur pencarian, misalkan, dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan sangat cepat, jika kita menggunanan list contigue dan melakukan pencarian biner. akan tetapi, jika kita ingin melakukan perubahan isi list (insert atau delete), menggunakan list contigue akan sangat lambat, karena proses insert dan delete dalam list contigue butuh memindahkan banyak elemen setiap saat. mungkin kita bisa juga menggunakan linked-list, yang untuk operasi insert atau delete tinggal mengatur – atur pointer, akan tetapi pada n-linked list, kita tidak bisa melakukan pointer sembarangan setiap saat, kecuali hanya satu kali dengan kata lain hanya secara sequential. Sebaliknay binary tree memberikan jawaban sempurna atas semua permasalahan ini, dengan memanfaatkan binary tree kita dapat melakukan pencarian elemen/node value dalam kompleksitas algorimta (big O) O(n log n) langkah saja.

nah, sekarang kembali ke tugas tadi, untuk menyelesaikan tugas tersebut kita akan membuat sebuah bst dengan node yang akan memilik data berupa string (char*) dan dua buah pointer untuk anak kiri (left child) dan kanan (right child). begini nih definisnya:

struct tnode{
   char *data;
   struct tnode *lchild, *rchild;
};

1. untuk membuat sebuah bst dari sebuah bst yang ada sebelumnya (insert node) kita buat fungsi insert:

struct tnode *insert(struct tnode *p,char val[])
{
   struct tnode *temp1,*temp2;
   if(p == NULL)
   {
      p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/
      if(p == NULL)
      {
		printf("Cannot allocate\n");
		exit(0);
      }

      (*p).data = (char*)malloc(sizeof(char)*strlen(val));
      if ((*p).data == NULL){
		printf("Cannot allocate data\n");
		exit(0);
      }
      strcpy(p->data,val);

      p->lchild=p->rchild=NULL;
   }
  else // insert node
  {
	  temp1 = p;
	  /* traverse the tree to get a pointer to that node whose child will be the newly created node*/
	  while(temp1 != NULL)
	  {
		 temp2 = temp1;
		 //printf("data %s vs %s\n", temp1->data, val);
		 if( strcmp(temp1 ->data, val) > 0){
			  temp1 = temp1->lchild;
		}
		else{
			  temp1 = temp1->rchild;
		}
	  }

	  if( strcmp(temp2->data , val)> 0)
	  {
		printf("insert left\n ");
		/*inserts the newly created node as left child*/
		temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
		temp2 = temp2->lchild;
		if(temp2 == NULL)
		{
			printf("Cannot allocate\n");
			exit(0);
		}
	    (*temp2).data = (char*)malloc(sizeof(char)*strlen(val));
		strcpy(temp2->data,val);
		temp2->lchild=temp2->rchild = NULL;
	  }
	  else
	  {
		//printf("insert right\n ");
		/*inserts the newly created node as left child*/
		temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
		temp2 = temp2->rchild;
		if(temp2 == NULL)
		{
		  printf("Cannot allocate\n");
		  exit(0);
		}
	    (*temp2).data = (char*)malloc(sizeof(char)*strlen(val));
		strcpy(temp2->data,val);
		temp2->lchild=temp2->rchild = NULL;
	   }

	}
	return(p);
}

nah untuk inorder traversal, kita memilih yang rekursif saja, lebih mudah:

/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
      if(p != NULL)
      {
           inorder(p->lchild);
           fprintf(fp,"%s\n",(*p).data);
           inorder(p->rchild);
      }
}

fungsi diatas traverse bst dengan model inorder dan menuliskan value tiap nodenya dalam file fp.

 

sekarang main functionnya ku buat seperti ini:

void main(int argc, char* argv[])
{
   struct tnode *root = NULL;
   int n;
   char x[20];
   if (argc >= 3){
	   printf("input : %s\n", argv[1]);
	   printf("output : %s\n", argv[2]);
	   fp = fopen(argv[2],"a");
	   fr = fopen(argv[1],"r");
	   while (!feof(fr)){
		fscanf(fr,"%s\n",&x);
		if (x[0] != '\n')	// kita ga mau line kosong masuk
			root = insert(root,x);
	   }
		// tulis hasil secara inorder
		inorder(root);
		fclose(fp);
		fclose(fr);
    }else{
		printf("command: bst <namainput> <namaoutput>");
    }
 }

setalah di compile, jalanin program ini tinggal panggila
$>bst stopwords.txt result.txt
selesai:

source code lengkapnya kayak gini:

#include
#include 
#include 

FILE *fp;
FILE *fr;

struct tnode
{
   char *data;
   struct tnode *lchild, *rchild;
};

/* a function to binary tree in inorder */
void inorder(struct tnode *p)
{
      if(p != NULL)
      {
           inorder(p->lchild);
           fprintf(fp,"%s\n",(*p).data);
           inorder(p->rchild);
      }
}

struct tnode *insert(struct tnode *p,char val[])
{
   struct tnode *temp1,*temp2;
   if(p == NULL)
   {
      p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/
      if(p == NULL)
      {
		printf("Cannot allocate\n");
		exit(0);
      }
      (*p).data = (char*)malloc(sizeof(char)*strlen(val));
      if ((*p).data == NULL){
		printf("Cannot allocate data\n");
		exit(0);
      }
      strcpy(p->data,val);

      p->lchild=p->rchild=NULL;
   }
  else // insert node
  {
	  temp1 = p;
	  /* traverse the tree to get a pointer to that node whose child will be the newly created node*/
	  while(temp1 != NULL)
	  {
		 temp2 = temp1;
		 //printf("data %s vs %s\n", temp1->data, val);
		 if( strcmp(temp1 ->data, val) > 0){
			  temp1 = temp1->lchild;
		}
		else{
			  temp1 = temp1->rchild;
		}
	  }

	  if( strcmp(temp2->data , val)> 0)
	  {
		//printf("insert left\n ");
		/*inserts the newly created node as left child*/
		temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));
		temp2 = temp2->lchild;
		if(temp2 == NULL)
		{
			printf("Cannot allocate\n");
			exit(0);
		}
	    (*temp2).data = (char*)malloc(sizeof(char)*strlen(val));
		strcpy(temp2->data,val);
		temp2->lchild=temp2->rchild = NULL;
	  }
	  else
	  {
		//printf("insert right\n ");
		/*inserts the newly created node as left child*/
		temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));
		temp2 = temp2->rchild;
		if(temp2 == NULL)
		{
		  printf("Cannot allocate\n");
		  exit(0);
		}
	    (*temp2).data = (char*)malloc(sizeof(char)*strlen(val));
		strcpy(temp2->data,val);
		temp2->lchild=temp2->rchild = NULL;
	   }

	}
	return(p);
}

void main(int argc, char* argv[])
{
   struct tnode *root = NULL;
   int n;
   char x[20];
   if (argc >= 3){
		printf("input : %s\n", argv[1]);
		printf("output : %s\n", argv[2]);
	   fp = fopen(argv[2],"a");
	   fr = fopen(argv[1],"r");
	   while (!feof(fr)){
		fscanf(fr,"%s\n",&x);
		if (x[0] != '\n')	// kita ga mau line kosong masuk
			root = insert(root,x);
	   }
		// tulis hasil secara inorder
		inorder(root);
		fclose(fp);
		fclose(fr);
    }else{
		printf("command: bstq  namafileinput namafileoutput");
    }
 }

notes: includenya ilang, dihapus sama engine wordpress, ini gantinya
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

update: source codenya telah diparsing oleh wordpress, sehingga kayaknya rusak, download langsung saja bst (jangan lupa renama .doc jadi .c)