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.

HAIKU: next generation OS

he.he.he, just kidding, HAIKU merupakan sebuah sistem operasi yang masih baru dalam tahap pengembangan. HAIKU merupakan open source OS yang diinspirasi oleh BeOS, tujuan pengembangannya sih katanya buat ngasih user personal computing experience yang simple tapi powerfull serta terbebas dari kompleksitas yang memang gak perlu bagi user.

karena masih dalam tahap pengembangan maka HAIKU belum ada .iso nya ataupun cd bajakannya, meskipun anda nyari sampe Blok M :D, kalau mau nyoba ya pake image-nya dulu, terus buka pake VMWare atau VirtualBox, nih aku kasih screenshot nya:

 

 

nah karena itu OS adalah open source dan masih benar – benar baru maka anda sebagai user punya kesempatan untuk melakukan pengujian dan ngasih kontribusi lainnya yang masih banyak lagi (misal: disain icon, GUI, etc.)

bagi anda seorang programmer/developer anda punya kesempatan untuk membesarkan anak balita ini :) dan tentunya jadi salah seorang pioneer tentu akan sangat membanggakan bagi anda ha..ha..ha.

nah, dan karena OS ini masih baru di kembangkan, jadi saya menyebutnya OS masa depan, soalnya bukan jaman sekarang, sekarang mah masih di kembangkan atuh

check it out: http://www.haiku-os.org/

kalau mu unduh image-nya cuman kecil 28 MB :D

kalau mau diskusi tentang OS ini dengan saya, dengan senang hati saya akan menjadi partner diskusi anda.

Jawaban Programmer untuk Shakespeare

Shakespeare seorang sastrawan yang sangat terkenal dalam salah satu karyanya Hamlet, Prince of Denmark, pernah bertanya (melalui tokoh Hamlet yang pada waktu itu mau bunuh diri) “to be or not tobe ?”, oke, begini petikan skripnya selengkapnya

To be or not to be, that is the question;
Whether ’tis nobler in the mind to suffer
The Slings and Arrows of outrageous Fortune
Or to take arms against a sea of troubles,
And by opposing, end them. To die, to sleep;
No more; and by a sleep to say we end
The heart-ache and the thousand natural shocks
That flesh is heir to — ’tis a consummation
Devoutly to be wish’d. To die, to sleep;
To sleep, perchance to dream. Ay, there’s the rub,
For in that sleep of death what dreams may come,
When we have shuffled off this mortal coil,
Must give us pause. There’s the respect
That makes calamity of so long life,
For who would bear the whips and scorns of time,
Th’oppressor’s wrong, the proud man’s contumely,
The pangs of despised love, the law’s delay,
The insolence of office, and the spurns
That patient merit of th’unworthy takes,
When he himself might his quietus make
With a bare bodkin? who would fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscovered country from whose bourn
No traveller returns, puzzles the will,
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all,
And thus the native hue of resolution
Is sicklied o’er with the pale cast of thought,
And enterprises of great pitch and moment
With this regard their currents turn awry,
And lose the name of action.^[2]

sebagai seorang programmer, saya forward pertanyaan ini kepada mas compiler (c++ compiler dari VS 2008 :)). gini pertanyaan saya

#include
int main(){
   int tobe = 0x2B;
   int tobeORNOTtobe;
   tobeORNOTtobe = (0x2B | ~0x2B);
   printf("0x2B | ~0x2B == %x",tobeORNOTtobe);
   return 0;
}

apa jawabannya si Mas coba, nih lihat

jadi ternyata jawaban untuk pertanyaannya shakespeare adalah “FFFF” :D

XOR SWAP, algoritma swapping yang unik

jika anda di suruh buat sebuah algoritma untuk mempertukarkan nilai dari dua buah variabel yang setipe, gimana caranya? ini mungkin pertanyaan yang sangat sederhana, bahkan bagi seorang pemula dalam dunia pemrograman, mungkin jawaban anda dapat tergambar dalam algoritma seperti ini:

1. misalnya variabel – variable yang akan di pertukarkan nilainya adalah A dan B
2. buat sebuah variabel penampung, misal C
3. beri nilai C dengan nilai A
4. beri nila A dengan nilai B
5. beri nilai B dengan nilai C

atau dalam bahasa c/c++ sebagai berikut:

void swap(int *A, int *B){
	int C;
	if (A != B){
	   C = *A;
	   *A = *B;
	   *B = C:
	}
}

tapi taukah anda, bahwa anda juga dapat membuat kode program berikut untuk operasi swap

void xorswap(int *A, int *B){
	if (A != B){
	   *A ^= *B;
	   *B ^= *A;
	   *A ^= *B;
	}
}

inilah yang disebut dengan algoritma xor swap, dengan memanfaatkan aturan closure pada operasi binary, muncullah algoritma xor swap ini. gak percaya bahwa algoritma bisa jalan? ok, saya gak bisa maksa anda percaya, jadi saya persilahkan anda untuk menanyakannya ke mesin, ambil compiler anda, tulis kode program seperti di atas, compile, terus jalankan……nah, percaya kan :)

Hello World Win32

Anda kenal dengan kode program berikut:

#include <stdio.h>

int main(){

        printf (“hello world”);

        return 0;

      }

itu merupakan “hello world” yang di populerkan oleh Ritchie&Kernighan pada waktu ngenalin c di The C Programming Language. Nah, sekarang disini sekarang saya coba membuat sebuah “hello world” dalam basis windows dengan win32 api, here we go:

#include <windows.h>

      int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance,PSTR szCmdLine, int iCmdShow)

{

            // kode untuk hello world,

MessageBox (NULL, TEXT (“Hello world”), TEXT (“HelloMsg”), 0) ;

            return 0;

}

Ah, gak menarik, ok mari kita coba buat hello world dengan versi lain. Kita tulis langsung di layar full screen. Tapi sebelumnya mari kita lihat dulu makhluk apa saja yang ada di hello world yang barusan saya buat itu. Perhatikan para meter pertama dari WinMain , hInstance merupakan handle pada instance (“program”) ini. hPrevInstance merupakan handle untuk instance yang sama yang sebelumnya telah ada jika memang ada, biasanya/selalu bernilai NULL (0). szCmdLine merupakan pointer ke sebuah string yang menunjukkan command line ke aplikasi. Sedangkan parameter terakhir mengatur bagaimana aplikasi ditampilkan yaitu hides (SW_HIDES), minimize (SW_MINIMIZE), maximize (SW_MAXIMIZE) dan nilai lainnya.

Sedangkan method MessageBox , ya seperti method messagebox di Vb maupun C# ya untuk itulah. Coba run saja entar tau J