MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA)
PRAKTIKUM PRAKTIKUM 6 IMPLEMENTASI BINARY TREE
TUJUAN PEMBELAJARAN: 1. Mengimplementasikan struktur data Binary Tree menggunakan linked list. 2. Mampu mengimplementasikan beragam operasi pada struktur data binary tree dengan Linked List. 3. Mampu melakukan pelacakan secara preorder, inorder dan post order pada binary tree. 4. Mampu memanfaatkan struktur data Binary Tree untuk menyelesaikan permasalahan. PENGANTAR: Binary Tree Sebuah binary tree adalah sebuah pengorganisasian secara hirarki dari beberapa buah simpul, dimana masing-masing simpul tidak mempunyai anak lebih dari 2. Simpul yang berada di bawah sebuah simpul dinamakan anak (child) dari simpul tersebut. Simpul yang berada di atas sebuah simpul dinamakan induk(parent) dari simpul tersebut. Masing-masing simpul dalam binary tree terdiri dari tiga bagian : sebuah data dan dua buah pointer yang dinamakan pointer kiri(left) dan kanan(right). Dengan menggunakan tiga bagian ini, kita menampilkan sebuah binary tree dengan melakukan setting pada pointer kiri dan kanan untuk menghubungkan sebuah simpul dengan anak-anaknya. Jika sebuah simpul tidak mempunyai anak pada pointer kiri atau kanan, kita melakukan setting pada pointer tersebut pada NULL, yang menunjukkan akhir dari percabangan adalah pada simpul tersebut. Sebuah percabangan adalah kumpulan dari simpul-simpul yang dimulai dari sebuah root dan diakhiri dengan sebuah simpul terakhir. Simpul terakhir (daun) adalah simpul dari tree yang tidak mempunyai anak.
Gambar 6.1 Struktur Binary Tree Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
1
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) Tabel 6.1 Terminologi Tree
Gambar 6.2 Ilustrasi sebuah Pohon Biner dengan Kedalaman 3
Implementasi Binary Tree dengan Linked List Salah satu implementasi dari binary tree adalah Binary Search Tree (BST), dimana BST merupakan sekumpulan elemen yang bernilai unik, dan untuk setiap node X dalam struktur BST Nilai elemen pada sub pohon kiri (left subtree) pasti memiliki nilai yang lebih kecil dari X dan nilai elemen pada sub poon kanan(right sub tree) pasti memiliki nilai yang labih besar. BST dapat disajikan dengan beberapa cara. Dalam praktikum ini akan menggunakan linked list untuk implementasi Binary Search Tree. Linked list yang dipakai adalah double linked list non circular.
Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
2
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA)
Gambar 6.3 Penyajian Binary Tree dengan Double Linked List Berikut penjelasan detail mengenai implementasi Binary Search Tree dengan linked list: • •
• • •
•
Terdapat setidaknya 8 operasi yakni, insert, findMin, findMax, find, remove, preOrder, inOrder, postOrder. Proses insert dilakukan dengan mengikuti aturan sbb: o Setiap node baru akan menempati posisi sebagai daun (leaf). o Untuk insert kedalam BST dimulai dari root, jika data lebih kecil dari root, node baru harus di masukkan ke dalam left sub tree. Jika data pada node baru lebih besar dari root, node baru harus di masukkan ke dalam right sub tree. o Gunakan rekursif. Operasi findMin akan mencari nilai terkecil dari node yang ada di dalam BST dengan cara menelusuri left subtree sampai ke daun. (gunakan rekursif). Operasi findMax akan mencari nilai terbesar dari node yang ada di dalam BST dengan cara menelusuri right subtree sampai ke daun. (gunakan rekursif). Operasi find akan mencari nilai yang dicari dengan membandingkan dengan data pada root. Jika lebih kecil akan mencari di left sub tree, dan jika lebih besar cari di right sub tree. (gunakan rekursif). Operasi remove dilakukan dengan mengikuti aturan sbb: o Jika node yang dihapus berposisi sebagai daun, dengan sederhana bisa dihapus. o Jika node memiliki satu anak, maka anak tersebut akan menggantikan posisi node yang dihapus. o Jika node memiliki 2 anak [pilih salah satu]: Ganti node yang dihapus dengan node terkecil pada right sub tree. Ganti node yang dihapus dengan node terbesar pada left sub tree.
Setiap elemen/node dari BST mempunyai 3 bagian yaitu bagian data yang bernilai dengan data, bagian left untuk menunjuk ke left subtree dan bagian right untuk menunjuk ke right sub tree. Dalam hal, ini setiap data dalam node bersifat unik/beda.
Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
3
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) LANGKAH PERCOBAAN 1: Langkah 1 : Definisikan langkah-langkah yang harus dikerjakan dalam setiap operasi yang tersebut diatas. Langkah 2: Mengkonversi kedalam coding untuk setiap operasinya pada kerangka kelas di bawah ini. class BinaryNode
{ // Data private private private
member T data; //menyimpan data node bst BinaryNode left; // Reference ke left subtree BinaryNode right; // Reference ke right sub tree
// Konstruktor, LeftNode dan RightNode di set null BinaryNode(T d) {... } }
public class BinaryTree { private BinaryNode root;//akar dari bst public public public public public public
BinaryTree() {...}//konstruktor BinaryNode insert(T x, BinaryNode t) {...} BinaryNode remove(T x, BinaryNode t) {...} BinaryNode find(T x, BinaryNode t) {...} BinaryNode findMin(BinaryNode t) {...} BinaryNode findMax(BinaryNode t) {...}
public void preOrder(...) {...} public void inOrder(...) {...} public void postOrder(...) {...} }
Anda diminta untuk mengisi kode java untuk setiap konstruktor dan method yang diimplementasikan (kurung yang kosong) sesuai dengan definisi sebelumnya. Langkah 3: Simpan implementasi binary search tree yang anda buat dengan nama bst.java Langkah 4: Buat class test untuk menguji implementasi bst yang anda buat.
Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
4
MODUL PRAKTIKUM STRUKTUR DATA & ALGORITMA (SDA) TUGAS PRAKTIKUM (POST TEST): 1. Modifikasi percobaan diatas dengan menambahkan operasi berikut: a. Menghitung jumlah/size node dalam tree. b. Menghitung height(kedalaman) tree. c. Mencari semua data pada node yang berposisi sebagai leaf(daun). Cat: Tugas praktikum sebisa mungkin dikerjakan di kelas. Asisten dimohon bisa memberikan arahan.
LAPORAN PRAKTIKUM BERISI PEMBAHASAN LATIHAN PERCOBAAN DAN SOAL. DIKUMPULKAN MINGGU DEPAN.
Abdul Aziz, Jurusan Informatika FMIPA UNS 2012
5
