OPERASI LOGIKA PADA GENERAL TREE MENGGUNAKAN FUNGSI REKURSIF Lutfi Hakim(1), Eko Mulyanto Yuniarno(2) Mahasiswa Jurusan Teknik Elektro(1), Dosen Pembimbing(2) Institut Teknologi Sepuluh Nopember (ITS) Kampus ITS Sukolilo, Surabaya 60111 Email:
[email protected] ABSTRAK General Tree merupakan salah satu jenis tree dinamis yang memiliki struktur data tidak linier yang menggambarkan struktur hirarki antar elemen. Struktur ini membentuk seperti sebuah struktur pohon. Sedangkan fungsi rekursif merupakan fungsi yang memanggil dirinya sendiri. Implementasi rekursif pada program general tree ini adalah saat menjalankan perintah untuk apakah node tersebut sebagai operasi logika AND atau OR atau juga sebagai node yang tidak memiliki sebuah anak node. Sehingga untuk membuat perintah logika tersebut dengan implementasi sebuah fungsi rekursif tidak membutuhkan syntax yang panjang dan sukar. Hasil dari makalah ini adalah sebuah program general tree operasi logika dengan urutan nilai 010 11111 101 100110 1 (node f-g-b -- h-o-p-i-c – j-k-d – l-m-q-r-n-e -- a). Nilai root menunjukkan angka 1 atau benar, dimana anak root bernilai 0 atau salah (node b), 1 atau benar (node c), 1 atau benar (node d) dan 0 atau salah (node e). Kata kunci : Fungsi Rekursif, General Tree, Operasi Logika, Pemrograman Java I.
PENDAHULUAN Pemrograman komputer dan kehidupan manusia merupakan dua unsur yang banyak memiliki fungsi saling keterkaitan. Sebuah program komputer berasal dari logika berfikir yang diimplementasikan dalam sebuah struktur yang dinamakan algoritma. Algoritma erat kaitannya dengan logika sebuah program dari awal hingga menunjukkan sebuah hasil atau luaran. Thomas H. Cormen, dkk (2009 : 1) menjelaskan bahwa algoritma algoritma merupakan sebuah rangkaian dari langkah komputasional yang sedemikian rupa yang mengubah input ke output. Sedangkan Kenneth H. Rosen (2012:191) mendefinisikan algoritma adalah sebuah rangkaian terbatas dari instruksi yang tepat untuk menampilkan sebuah komputasi atau untuk menyelesaikan sebuah permasalahan. Sehingga dari kedua artian tersebut dapat disimpulkan bahwa Algoritma dalam pemrograman komputer merupakan suatu langkah atau urutan berfikir untuk menyelesaikan suatu permasalah (dalam hal ini pemrograman komputer) yang disusun secara sistematis dan logis. Sebuah program yang baik memiliki runtutan algoritma yang baik pula, oleh karenanya penting untuk mendesain awal runtutan algoritma jika membuat suatu program komputer. Rekursif merupakan salah satu jenis algoritma. Rekursif memiliki makna bahwa suatu hal mengalami pengulangan dan dalam pengulangannya melibatkan dirinya sendiri. Sedangkan tree atau pohon merupakan salah satu objek dari kehidupan yang memiliki struktur urutan dari atas (parent atau root) ke elemen bawahnya (anak simpul atau node). Rekursif dan tree merupakan dua hal yang tanpa disadari banyak ditemukan dalam kehidupan sehari-hari. Sebagai contoh ketika dua cermin yang diletakkan berhadapan secara paralel, maka di dalam cermin tersebut terbentuk bayangan cermin yang di dalam
cermin sekian banyaknya. Begitu juga pohon. Struktur keorganisasian sebuah perkumpulan ataupun unit merupakan salah satu contoh kasus pohon dalam kehidupan sehari-hari. General tree adalah salah satu bentuk dari tree yang memiliki jumlah anak tree tidak menentu. Hal ini menyebabkan suatu program general tree memerlukan algoritma yang berulang untuk memanggil fungsi dirinya sendiri untuk membuat suatu node. Oleh karena itu pemilihan rekursif untuk membuat logika sebuah pemrograman dinilai menjadi pilihan yang sangat tepat. Sisi lain, Operasi logika juga merupakan salah satu operasi yang tidak terlepas dari pemrograman. Pemilihan keputusan dalam logika berfikir pemrograman memerlukan sebuah operasi logika. Seperti operasi AND, OR dan lain sebagainya. Implementasi operasi logika dalam general tree untuk mencari sebuah nilai akhir dari sebuah akar dari general tree merupakan hal yang baru dalam pemrograman. Pada makalah ini akan dibahas mengenai permasalahan tersebut. Program yang dibuat dengan menggunakan bahasa pemrograman java. Luaran program yang dihasilkan merupakan implementasi dari node-node yang membentuk seperti general tree yang mengandung sebuah operasi logika pada node atau simpul yang memiliki suatu anak lebih dari dua. Operasi tersebut berupa operator AND dan OR, sedangkan node atau simpul yang tidak memiliki sebuah anak node akan bernilai 1 atau true dan bernilai 0 atau false. II. TEORI DASAR 2.1. Rekursif (Recursion) Rekursif atau recursion merupakan merupakan algoritma dalam bahasa pemrograman komputer yang memiliki fungsi di mana salah satu baris perintah pada suatu program memanggil fungsi yang sama dengan dirinya, dengan kata lain fungsi rekursif adalah fungsi yang memanggil dirinya sendiri. Sebuah algoritma dikatakan rekursif jika memecahkan masalah dengan mengurangi itu ke sebuah contoh dari masalah yang sama dengan input yang lebih kecil. Rosen (2012, 344-345) menggambarkan bahwa fungsi rekursif seperti pada gambar 1. Pertama diberikan sebuah gambar asli, kemudian proses pengambilan gambar dilakukan berturut-turut melapis gambar kecil yang berpusat di atas gambar sebelumnya.
Gambar 1: Sebuah gambar yang digambarkan secara rekursif Rosen (2012, 345) Sebuah fungsi rekursif bisa tak terbatas seperti lingkaran. Untuk menghindari hal tersebut, ada dua sifat yang harus dimiliki oleh fungsi rekursif, diantaranya: 1. Kriteria dasar (base criteria) yang maksudnya adalah harus ada setidaknya satu kriteria dasar atau kondisi, sehingga ketika kondisi ini terpenuhi maka fungsi berhenti menyebut dirinya sendiri.
2. Pendekatan progresif (Progressive approach) yang maksudnya adalah panggilan rekursif harus maju dalam sedemikian rupa sehingga setiap kali panggilan rekursif dibuat datang lebih dekat dengan kriteria dasar. Jika kedua kondisi tersebut terpenuhi, maka algoritma tersebut dikatakan rekursif. Fungsi rekursif umumnya dipakai untuk permasalahan yang memiliki langkah penyelesaian yang teprola atau langkah-langkah yang teratur. Secara umum, algoritma fungsi rekursif memiliki statement kondisional sebagai berikut : If kondisi khusus tidak terpenuhi Then panggil diri-sendiri dengan parameter yang sesuai Else lakukan instruksi yang akan dieksekusi bila kondisi khusus dipenuhi 2.2. General Tree Pohon atau tree merupakan salah satu bentuk tidak linier yang termasuk dalam kategori graph terhubung yang tidak mengandung sirkuit atau lintasan layaknya sebuah struktur pohon. Struktur pohon pada tree yang dimaksud merupakan suatu cara yang mempresentasikan hubungan data yang bersifat hirarki antar elemen-elemen secara grafis mirip dengan sebuah pohon, walaupun pohon tersebut hanya tampak sebagai sekumpulan node-node dari atas ke bawah. Elemen-elemen pada sebuah bentuk tree terdapat sebuah akar atau root dan sisa elemennya disebut sebagai simpul (Node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama lainnya, yang disebut subtree atau cabang. Untuk mengetahui lebih jelasnya, dapat digambarkan dengan ilustrasi berikut.
A
A1
A2
....
An
Gambar 2. Ilustrasi kumpulan node Gambar 2 mengilustrasikan sebuah kumpulan node dimana node A disebut sebagai simpul tunggal, sedangkan A1, A2, ... An disebut sebagai subtree atau cabang. Kumpulan node-node tersebut akan membentuk sebagai sebuah tree jika antar node dihubungkan satu sama lainnya. Untuk lebih jelasnya, dapat dilihat pada gambar berikut ini. A
A1
A2
An
Gambar 3. Ilustrasi sebuah tree Gambar 3 menunjukkan kumpulan beberapa node yang membentuk hubungan satu sama lainnya, inilah yang dinamakan dengan sebuah tree. Node A merupakan sebuah root
atau akar sedangkan A1, A2, ... An merupakan anak dari node A atau juga disebut subtree. Pada sebuah tree terdapat banyak sebutan, antara literatur satu dengan literatur lainnya disebut dengan nama yang berbeda. Berikut beberapa istilah pada sebuah tree. Tree
Level Level 1
A
B
D
E
F
C
Level 2
G
Level 3
Gambar 4. Tree Berikut istilah-istilah objek tree : Node adalah elemen tree yang berisi informasi atau data dan petunjuk percabangan. Tingkat atau level suatu node ditentukan dari akar (root) sebagai level 1. Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur dengan node tersebut, dari akar sampai node yang ditinjaunya, contohnya ancestor E adalah B dan A. Predecessor adalah node yang berada di atas node yang ditinjau, contoh predessor G adalah C. Successor adalah node yang berada di bawah node yang ditinjau, contoh successor B adalah D, E dan F. Descendant adalah seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama, contohnya descendant C adalah G. Sibling adalah node- node yang memiliki parent yang sama dengan node yang ditinjau, contohnya adalah sibling F adalah D dan E. Parent adalah node yang berada satu level di atas node yang ditinjau, contohnya parent B adalah A. Sebuah tree dibagi menjadi dua jenis bentuk yang berbeda, yakni tree static dan tree dinamis. Tree static merupakan tree yang isi node-nodenya tetap karena bentuk pohonnya sudah ditentukan, sebagai contoh binary tree. Sedangkan Tree dinamic merupakan tree yang isi node-nodenya berubah, sehingga jumlah node-nya bisa ditambahkan atau dihapuskan sesuai dengan keinginan baik itu antar hubungan one to one atau one to many. Pada gambar 4 di atas merupakan contoh ilustrasi dari general tree. General tree T adalah sebuah bentuk terbatas dari satu atau lebih node seperti yang ada salah satu node didesain sebagai R yang dinamakan akar dari T. Jika bentuk (T – {R}) adalah tidak kosong, beberapa node dibagi menjadi n > 0 memisah bentuk dari T0, T1, ... Tn-1, masing-masing dari hal ini adalah sebuah general tree dan akar dari R1, R2, ... Rn, secara respektif adalah anak dari R. Bentuk Ti (0 ≤ i < n) dikatakatan menjadi subtree dari T. Subtree tersebut diperintah pada Ti yang dikatakan datang sebelum Tj jika i < j. Dengan
ketentuan, subtree disusun dari kiri ke kanan dengan subtree T0 yang dinamakan anak paling kiri dari R. Masing-masing node dari sebuah general tree hanya mempunyai satu parent, kecuali untuk akar yang tidak mempunyai parent. Untuk hal ini, diikuti dengan seketika bahwa sebuah general tree dengan n node harus mempunyai batas n – 1 karena masing-masing node, disamping akar, mempunyai satu batas yang menghubungkan node ke parentnya. 2.3. Operasi Logika Suatu fungsi logika atau operasi logika yang dimaksud dalam aljabar Boolean adalah suatu kombinasi variabel biner yang bernilai true atau 1 dan false atau 0 seperti misalnya masukan dan keluaran suatu rangkaian digital yang dapat menunjukkan bahwa di dalam aljabar Boolean semua hubungan logika antara variabel biner dapat dijelaskan oleh tiga operasi logika dasar, yaitu : Operasi NOT (negation), operasi AND (conjunction), dan operasi OR (disconjunction). Ketiga operasi tersebut merupakan operasi dasar dari konsep aljabar Boolean. Boolean sendiri merupakan suatu tipe data yang hanya mempunyai dua nilai, yakni tru atau false (benar atau salah). Benar dikatakan juga suatu kondisi bernilai 1, dan salah jika suatu kondisi bernilai 0. Pada pokok bahasan ini tidak membahas semua operasi logika yang ada pada aljabar boolean, namun hanya membahas mengenai operasi AND dan OR. 2.3.1 Operasi AND Operasi AND merupakan suatu operasi boolean yang dikatakan memiliki nilai benar atau bernilai 1 jika suatu kondisi semua masukan bernilai 1 atau true pula. Operasi AND dilambangkan dengan dot (.) atau juga dilambangkan dengan dengan huruf V terbalik yakni “˄”. Namun pada syntax pemrograman operasi AND dilambangkan dengan simbol “&” atau “&&”. Untuk lebih jelasnya mengenai operasi logika AND, perhatikan tabel kebenaran berikut. Tabel 1. Tabel Kebenaran Operasi AND A B (A ˄ B) atau (A . B) 1 1 1 1 0 0 0 1 0 0 0 0 2.3.2 Operasi OR Berbeda dengan operasi AND, operasi OR merupakan suatu operasi pada gerbang logika atau aljabar Boolean yang memiliki nilai bahwa jika suatu output atau keluaran akan bernilai 1 atau benar jika salah satu input atau masukannya bernilai 1 atau benar, dan jika semua masukan atau input bernilai salah maka output atau luaran akan bernilai 0 atau salah pula. Operasi OR dilambangkan dengan plus (+) atau juga dilambangkan dengan dengan “˅”. Namun pada syntax pemrograman operasi OR dilambangkan dengan simbol “|” atau “| |”. Untuk lebih jelasnya mengenai operasi logika OR, perhatikan tabel kebenaran berikut. Tabel 2. Tabel Kebenaran Operasi OR A B (A ˅ B) atau (A + B) 1 1 1 1 0 1 0 1 1 0 0 0
2.4. Pemrograman Java Bahasa pemrograman adalah software bahasa komputer yang digunakan dengan cara merancang atau membuat program sesuai dengan struktur dan metode yang dimiliki oleh bahasa pemrograman itu sendiri. Dalam beberapa waktu terakhir, semakin banyak bahasa pemrograman yang diciptakan. Seperti python, matlab dan lain sebagainya. Namun pada bahasan kali ini menggunakan bahasa pemrograman java. Java merupakan bahasa pemrograman berorientasi objek dan bebas platform, yang dikembangkan oleh Microsystem saat ini merupakan bagian dari Oracle dan dirilis tahun 1995. Java merupakan salah satu bahasa pemrograman tingkat tinggi yang memiliki karakteristik simpel berorientasi objek dan memiliki performance yang tinggi. Bahasa pemrograman java merupakan pengembangan dari bahasa pemrograman C dan C++ dengan source code yang lebih simple dan mudah. Java platform memiliki dua komponen yaitu Java Virtual Machine (JVM) yang berfungsi sebagai jembatan atara bytecode dengan hardware dan Java Application Programming Interface (Java API) yang merupakan komponen-komponen dan kelas java ywang telah jadi dan memiliki kemampuan untuk menangani objek, string, angka dan sebagainya. Bahasan kali ini memakai Java SE Development Kit (JDK) 6 sebagai JVM dan Neatbens 6.5 sebagai interface pembangun program general tree ini. III. IMPLEMENTASI Operasi logika pada general tree menggunakan fungsi rekursif dibangun dengan bahasa pemrograman java. General tree yang dimaksud adalah sebuah node yang dihubungkan antara elemen satu dengan elemen lainnya secara terstruktur, logis dan sistematis. Hubungan ini membentuk sebuah struktur seperti pohon yang memiliki anak secara dinamis. Node pada sebuah general tree memiliki dua jenis, yakni sebagai parent atau orang tua dan sebagai anak atau child. Jika node sebagai parent maka node tersebut memiliki dua kedudukan yakni sebagai operator dan sebagai sebuah node yang memiliki sebuah nilai. Sedangkan node sebagai sebuah anak adalah sebuah node yang tidak memiliki anak lagi, dan hanya mempunyai satu kedudukan yakni memiliki nilai false atau 0 dan nilai true atau 1. Kedudukan node sebagai sebuah parent yang memiliki input sebuah operator. Operator logika yang digunakan adalah operator OR dan AND. Jika parent memiliki kedudukan sebagai operator OR akan memiliki nilai 1 atau benar jika salah satu anak node bernilai 1 atau benar, dan bernilai salah atau 0 jika semua anak node juga bernilai salah atau 0. Sedangkan parent yang memiliki kedudukan sebagai operaotor AND akan bernilai 1 atau bernilai true jika semua anak node bernilai 1 atau benar juga. Jika salah satu atau semuanya bernilai salah atau 0, maka node parent tersebut akan bernilai false atau 0. Sebuah node yang tidak memiliki anak node disebut sebagai node tunggal atau juga sebagai anak. Jika dalam kondisi seperti ini, maka nilai dari general tree tersebut adalah nilai dari node tersebut, yakni bernilai 0 ataupun 1 (salah ataupun benar) tanpa menggunakan operasi logika OR dan AND. Implementasi logika berfikir ini dijabarkan dalam penjelasan berikut ini. Langkah awal yang dilakukan untuk membuat sebuah program general tree yang mempunyai operasi logika adalah dengan membuat sebuah node terlebih dahulu. Untuk membuat sebuah node menggunakan deklarasi vektor. Alasan mengapa menggunakan deklarasi ini adalah agar node yang dibuat dapat bekerja secara dinamis, sehingga dapat dibuat dengan node dengan jumlah yang tidak terbatas sesuai dengan keinginan pengguna. Source code untuk hal ini adalah
Source code di atas merupakan sebuah class yang menggunakan nama ‘class node’ yang didalamnya terdapat variabel ‘tambah’ dengan tipe data public integer dan juga deklarasi vektor yang digunakan untuk membuat sebuah node secara dinamis. Fungsi tersebut akan menjalankan fungsinya sebagai perintah untuk membuat node secara dinamis jika pada bagian utama program di tuliskan source code sebagai berikut.
Sebuah node akan membentuk seperti general tree jika dihubungkan antar node tersebut. Agar antar node yang telah dibuat saling memiliki unsur keterhubungan, maka dituliskan sebuah fungsi program sebagai berikut.
Dan menuliskan source code berikut pada bagian utama program agar antar node dapat terhubung.
Syntax program tersebut membuat perintah untuk menghubungkan antara node satu dengan lain secara tersetruktur seperti general tree. Selanjutnya memberikan nilai pada masing-masing node, apakah node sebagai operator (OR atau AND) yang berposisi sebagai node parent atau anak node yang tidak anak lagi dan bernilai satu atau benar ataukah bernilai nol atau salah. Untuk membuat suatu logika seperti itu menggunakan algoritma fungsi rekursif.
Sehingga dengan source code tersebut membentuk sebuah general tree yang berposisi sebagai parent yang memiliki sebuah atau beberapa anak ataupun sebagai anak yang tidak memiliki anak lagi. Agar program dapat ditampilkan maka dituliskan syntax program
urutan penampilan program dan melihat masing-masing nilai dari setiap node. Syntax programnya sebagai berikut.
Fungsi cetak2 sebagai perintah untuk menampilkan urutan nilai node, sedangkan fungsi HubungNode berfungsi sebagai perintah untuk mengecek nilai masing-masing node apakah bernilai 1 atau 0. Agar program dapat ditampilkan pada badan program hasil, maka dituliskan source code berikut pada jendela utama program.
Sehingga dengan runtutan program di atas akan menghasilkan sebuah luaran sebagai berikut.
Jika digambarkan urutan tampilan angka di atas, maka gambar general tree-nya sebagai berikut : OR
a AND
AND
b
c
AND
OR
d
0
1
1
OR
f
g
h
i
e
1
0
1
j
k
l
0
OR
m
n
1
1
0
1
o
p
q
r
Berdasarkan urutan tampil nilai di atas menunjukkan nilai urutan berdasarkan urutan post order, yakni dari node paling kiri menuju ke node paling kanan dan terakhir merupakan nilai root (node a). Urutan nilainya adalah 010 11111 101 100110 1 (f-g-b -- h-o-p-i-c – j-k-d – l-m-q-r-n-e -- a). Hasil akhir yang menunjukkan nilai 1 menunjukkan nilai dari node a. IV. KESIMPULAN Berdasarkan hasil pengujian program dapat disimpulkan bahwa implementasi fungsi rekursif untuk membuat sebuah program general tree dengan operasi logika sangat tepat dan efektif. Terbukti bahwa hasil program menunjukkan dengan hasil yang benar, yakni dengan urutan nilai 010 11111 101 100110 1 (f-g-b -- h-o-p-i-c – j-k-d – l-m-q-rn-e -- a). Hal ini sesuai dengan yang diharapkan dimana program mencari nilai akhir pada root dari tree. Pada program di atas dituliskan bahwa root menggunakan fungsi logika OR, dimana fungsi logika OR bernilai benar jika salah satu anak node dari root bernilai satu. Pada hasil tersebut, root dari general tree menunjukkan nilai 1 atau benar. V. DAFTAR PUSTAKA 1. Rosen, Kenneth H. 2012. Discrete Mathematics and Its Application seven edition. New York : The Mc Graw Hill Companies. 2. Cormen, Thomas H, dkk. 2009. Introduction to Algorithm Third Edition. London : Massachusetts Institute of Technology. 3. Tutorial Point. 2016. Data Structure and Algorithm. Ebook download (online) 4. Tutorial Point. 2016. Java. Ebook download (online)