Representasi Data dengan Pohon Biner




Representasi data dalam sebuah perangkat komputer.

Para perancang sistem operasi selalu berusaha memikirkan algoritma yang tepat, efektif dan efisien guna “menjaga” data yang ada agar tidak hilang. Seperti ketika suatu data akan disimpan di suatu media penyimpanan, bagaimana menentukan alamatnya agar dapat diraih kembali, bagaimana agar keterhubungan antara satu bagian data dengan bagian data lain tidak terputus, dan sebagainya.

Salah satu metode yang digunakan adalah binary tree. Alamat dan keterkaitan antar data dapat digambarkan sebagai pohon biner, seperti contoh berikut ini :

 


 

Gambar 10. Contoh keterkaitan antardata

 

Start menunjuk ke alamat 100, yaitu “N”. “N” sendiri menunjuk alamat kiri ke 201 (yaitu “O”), dan kanan ke 350 (yaitu “N”). Buatlah algoritma agar informasi yang akan dihasilkan adalah “NOVIANA”.

 

Dengan berbagai pertimbangan, tidak semua perancang komputer membuat algoritma untuk melakukan perhitungan data matematis seperti yang dilakukan oleh manusia pada umumnya (secara infix). Ada komputer yang mengolahnya secara prefix dan ada yang secara postfix.

 

Contoh bentuk infix     : A + B

        prefix    : + A B

        postfix    : A B +

 

Lambang yang digunakan manusia untuk melakukan penjumlahan angka 5 dan 7, adalah 5 + 7 (infix). 5 dan 7 disebut operand, dan + disebut operator. Untuk komputer yang melakukan proses matematis secara prefix, kalimatnya diubah dengan “tambahkan 5 dengan 7” atau dilambangkan dengan + 5 7, dan untuk postfix, kalimatnya adalah “5 dan 7 ditambahkan”, atau dilambangkan dengan 5 7 +.

 

Bagaimana penulisan notasi infix : A + B * C + D secara prefix dan postfix ?.

 

Prefix :

langkah 1, tentukan mana yang pertama kali yang akan diproses, diperoleh B * C. Misal B * C diganti dengan E, maka soalnya menjadi : A + E + D

A + B * C + D

E

 

langkah 2, tentukan kembali mana yang akan diproses pertama kali, diperoleh A + E. Bila A + E diganti dengan F, maka soalnya menjadi F + D

A + E + D

                     F

 

langkah 3, karena sudah menjadi 2 operand, maka notasi prefixnya menjadi + F D

 

 


 

Gambar 11a. Binary tree dari F + D

 

langkah 4, kembalikan nilai F sebenarnya. F = A + E, prefixnya = + A E, sehingga notasi keseluruhannya menjadi + + A E D

 


 

Gambar 11b. Binary tree dari (A + E) + D

 

langkah 5, kembalikan nilai E sebenarnya. E = B * C, prefixnya = * B C, sehingga notasi keseluruhannya menjadi + + A * B C D

 


 

Gambar 11c. Binary tree dari A + (B * C) + D

 

Ekspresi matematis A + ( B * C ) + D = A + B * C + D.

 

Postfix :

langkah 1, tentukan mana yang pertama kali yang akan diproses, diperoleh B * C. Misal B * C diganti dengan E, maka soalnya menjadi : A + E + D

langkah 2, tentukan kembali mana yang akan diproses pertama kali, diperoleh A + E. Bila A + E diganti dengan F, maka soalnya menjadi F + D

langkah 3, karena sudah menjadi 2 operand, maka notasi postfixnya menjadi F D +

langkah 4, kembalikan nilai F sebenarnya. F = A + E, postfixnya = A E +, sehingga notasi keseluruhannya menjadi A E + D +

langkah 5, kembalikan nilai E sebenarnya. E = B * C, postfixnya = B C *, sehingga notasi keseluruhannya menjadi A B C * + D +

 

Untuk soal : (A + B) * C + D bentuk binary treenya sebagai berikut :

 


 

Gambar 12. Skema binary tree untuk (A+B)*C+D

 

Prefixnya     : + * + A B C D

Postfixnya    : A B + C * D +

 

Dari gambar binary tree, kita dapat secara langsung menentukan bentuk notasi infix,
prefix, maupun postfixnya. Perhatikan gambar berikut ini.

 


 

Gambar 13. Tentukan infix,
prefix, dan postfixnya

 

Infix : Ingat, konsep binary tree adalah “pembelahan dua.” Jika gambar 13 itu dibelah menjadi dua, maka belahan kiri (left substree) terdiri dari A / B, dan belahan kanan (right substree) adalah C * – E F, sementara yang di tengah (root) adalah +. Di belahan kiri kita sudah mendapatkan notasi (A / B). Di belahan kanan, kita belah lagi menjadi belahan kiri2 C, dan belahan kanan2 E – F, sedangkan yang di tengah (root) adalah *.

 

Hasil pembelahan itu kini kita gabungkan (setiap operator atau root), kita letakkan di tengah.

Notasinya menjadi : (A + B) + ( C * (E – F))

         kiri kanan

Hilangkan tanda kurung pemisah yang tidak penting (bila dibuang, hasil pemrosesan tidak berubah). Notasinya menjadi : A + B + C * (E – F)

 

Prefix : Karena operand berada di depan, sehingga untuk notasi A + B dituliskan dengan + A B, maka bila bila kita sebut A adalah kiri, + adalah tengah, dan B adalah kanan, maka rumusnya adalah tengah-kiri-kanan secara rekursif (lakukan berulang di setiap node mana yang sedang dikunjungi)

 

Lakukan rumus itu dari atas, kita dapat tengah + (sementara hasilnya adalah +).

Setelah tengah, kita menuju ke kiri, yaitu /. Stop di situ, kita ulangi lagi rumus semula, tengah-kiri-kanan. Tengah = /, kiri = A dan kanan = B. Hasil berikutnya menjadi + /.

 

Dari / kita menuju ke kiri lagi, kita dapat A. Stop di situ, ulangi lagi rumus tengah-kiri-kanan. Karena tidak ada lagi yang lebih kiri dari A, maka A dijadikan hasil, sehingga hasilnya menjadi + / A. Setelah tidak ada yang di kiri lagi, maka lanjutkan rumus, setelah kiri adalah kanan, yaitu B. Ulangi lagi rumus tengah-kiri-kanan, karena tidak ada lagi yang berada di kiri maupun di kanan B, maka jadikan B sebagai hasil, sehingga hasilnya menjadi + / A B.

 

Substree kiri sudah selesai, maka lanjutkan ke substree kanan, lakukan sama dengan rumus tengah-kiri-kanan. Maka hasil akhirnya akan diperoleh : + / A B * C – E F.

 

Postfix : Karena operator di belakang operand, maka rumusnya : kiri-kanan-tengah.

(Ulangi seperti yang telah diuraikan di penyelesaian notasi prefix dengan rumus yang berbeda).

 

Dimulai dengan substree kiri, kita peroleh : A B /.

Dilanjutkan dengan substree kanan, kita peroleh : C E F – * +.

Hasil akhirnya : A B / C E F – * +

 

Prefix menempatkan puncak (akar/ root) di awal notasi, sedangkan postfix menempatkan puncak (root) di akhir notasi. Dengan sering melakukan latihan, dengan hanya melihat gambar binary treenya, kita akan mudah menemukan pola pergerakan untuk menentukan notasi prefix dan postfixnya.

 

Bisakah anda mencari jalannya bila diketahui postfix = A B C – + D E F / + *, maka prefixnya = * + A – B C + D / E F, dan infixnya = (A + B – C ) * ( D + E / F) ?. Gambarlah binary treenya.

Iklan

tulis comment nya...

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

Logo WordPress.com

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

Gambar Twitter

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

Foto Facebook

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

Foto Google+

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

Connecting to %s