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:

image

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-&gt;data,val);

      p-&gt;lchild=p-&gt;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-&gt;data, val);
		 if( strcmp(temp1 -&gt;data, val) &gt; 0){
			  temp1 = temp1-&gt;lchild;
		}
		else{
			  temp1 = temp1-&gt;rchild;
		}
	  }

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

	}
	return(p);
}

void main(int argc, char* argv[])
{
   struct tnode *root = NULL;
   int n;
   char x[20];
   if (argc &gt;= 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",&amp;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)

About these ads

28 thoughts on “Pohon Pencarian Biner aka. Binary Search Tree (BST)

    • gak, gak harus (*p).data sebenarnya sama saja dengan p->data, masalahnya datanya adalah berupa pointer ke karakter
      misal

      (*p).data = (char*)malloc(sizeof(char)*strlen(val));
      sama saja dengan
      p->data = (char*)malloc(sizeof(char)*strlen(val));

      CMIIM,

      iya itu gak tahu kenapa kok di bawah di parse jadi gitu ( [->]), padahal yang di atas bisa ane ingat, yang bagian atas kayaknya ana edit/tulis pada bagian visual, yang di bawah, pada htmlnya, kayaknya gitu :-?

      jazaakaallah khaiyran katsiir ya, mau meriksa :)

  1. wa iyyaak.

    tanya kim, yang di bawah

    if( strcmp(temp2->data , val)> 0)

    itu bisa dijadikan satu kode ya? maksudnya tnode dibuat dulu (sebelum “if” tersebut) baru dicek dan dimasukkan ke lchild atau rchild? (bukannya kodenya sama ya?).

    Satu lagi, jika fungsi insert hasilnya adalah exit(0), apa yang terjadi pada ini?

    root = insert(root,x);

    Btw, fungsi insert ini yang menurutku bisa mengembalikan void karena inputnya berupa pointer. cmiiw.

    jazaakumullaahu khayran informasinya, agak-agak lupa materi kuliah ini :)

    • alhamdulillah, senang ada pembaca yang kritis seperti ini, syukron akh. waba’du :

      hmm, gak bisa (atau koreksi saya :|), pada while bagian atas itu kita mencari posisi node yang tepat untuk di insert node baru, sedangkan

      if( strcmp(temp2->data , val)> 0){..}else{...}

      itu hanya menaruhnya di kiri atau kanan node yang telah ditemukan, jadi tanpa pemeriksaan itu kita tidak tahu apakah sebaiknya membuat node di kiri atau kanan node yang ditemukan (kalau buat dulu sebelum strcmp, mana yang diinisiasi/alokasi, lchild atau rchild kan gak tahu)

      tentang exit, itu gak jadi masalah, karena exit(0) = EXIT_SUCCES atau exit(1) = EXIT_FAILURE itu tidak akan return apa2 ya, exit begitu saja, itu terminasi/mematikan proses. jadi gak akan sempat sampai pada

      root = insert(root,x);

      sudah mati duluan prosesnya.
      kira2 kalau itu terjadi, akan muncul
      teks: “cannot allocate” program keluar.

  2. sebelumnya saya mu ucapakan terima kasih
    karena dengan jawaban ini saya juga dapat ngerjain tugas
    tapi
    kenapa programnya agak error???
    fopennya ga ada…so data yang udah diurutin nya kemana??
    dibalas ya…
    makasih

    • sama2,
      jangan copas (copy & paste) langsung dari code yang di tulis itu, download link yang di bawah, ganti ekstensinya jadi .c, fopen (both read & write) ada di main function. hapus yang gak perlu (misal debug printf(“sesuatu”); ). hasilnya ada di file output yang anda spesifikasikan waktu manggil program.

      semoga bermanfaat :)

  3. ada dua file yang dimanfaatkan dalam program tersebut.
    satu file stopwords sebagai masukan (operasi yang dilakukan adalah read (fopen(“nama”,”r”), r = read) ), dan satu file output/keluaran yang akan digenerate sesuai dengan nama file yang dispesifikasikan saat runtime/eksekusi (fopen(“nama”, “a”), a= append, artinya append jika file sudah ada dan buat file baru jika file belum ada).

    file input (stopwords.txt) terdapat pada url yang sudah saya kasih tahu di atas (baca lagi ya :p ). sedangkan file output itu terserah, tinggal kasih nama saja (nanti digenerate oleh program)

    ps: maaf dua komentar terakhir id mu kurubah, dengan nama yang lebih baik dari idmu sebelumnya, meskipun sebenarnya aku masih tidak suka :). sapa coba yang suka dinamai wedhus, lain kali gunakan nama yang lebih baik ya, gak bayar kok :D

  4. Mau tanya tau ga fungsi/prosedur untuk menghitung is_canceled. jadi jika true maka dihitung jika false tidak hitung…adapun ADT nya:

    typedef char string[256];
    struct node
    {
    string nama_pelanggan;
    string alamat;
    int waktu_penjemputan;
    bool is_canceled;
    node *Right;
    node *Left;

    };

    Terimakasih

  5. wkakwkakwkawk….

    makasi mas saya lupa baca, abis lgsg baca source codenya, :DDD

    oo nama wedhus, maap mas, binatang favorit saya kambing(wedhus)
    kebetulan bapak saya mbeli wedhus kemaren mukanya jelek bgt(bandhot)wakwkawkakwkawk…

  6. mas hakim aku ndue soal masalah implementasi tree, mumet mas logika ku ra tekan,, boleh nanya solusi nya gak ??

    nb.ijin dulu :D:D:D:D

  7. masalahnya itu mengenai game robot mas, jadi kita disuruh buat lintasan terus si robot bisa menghancurkan penghalang, nah saya bener2 bingung wkakwkakwkakw…

  8. As, Mas. Slm kenal neh. Btw, BTS-nya ada dalam bahasa pemrograman PHP ga?? Saya buat tugas kuliah ni. Soalnya saya nyari kesana-kesini kebanyakan bahasa C, tolong dong petunjuknya mas.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s