Atthohir AB

TUGAS MANDIRI

“Binary Tree”

Mata Kuliah: Struktur Data

NAMA MAHASISWA : MUHAMAD FAJRI MAULANA M I

NIM : 113410027

KODE KELAS : 112-IF211-M4

DOSEN : PASTIMA SIMANJUNTAK, S.KOM.

STMIK PUTERA BATAM

TAHUN 2012

KATA PENGANTAR

Puji syukur kita panjatkan kehadirat Allah SWT, Tuhan Yang Maha Esa yang telah memberikan rahmat serta hidayah-Nya sehingga penyusunan tugas ini dapat diselesaikan. Tugas ini disusun untuk diajukan sebagai tugas mandiri mata kuliah Struktur Data dengan judul “Binary Tree” dalam menempuh pendidikan perkuliahan di STMIK Putera Batam.

Terima kasih disampaikan kepada Ibu Pastima Simanjuntak, S.Kom. selaku dosen mata kuliah Struktur Data yang telah membimbing dan memberikan kuliah demi lancarnya tugas mandiri ini.

Penulis menyadari bahwa masih banyak kekurangan dan keterbatasan dalam penyajian data dalam tugas mandiri ini. Oleh karena itu, penulis mengharapkan kritik dan saran yang membangun dari semua pembaca demi kesempurnaan tugas ini. Demikian tugas ini penulis susun, apabila ada kata-kata yang kurang berkenan dan banyak terdapat kekurangan, penulis mohon maaf yang sebesar-besarnya.

Batam, 30 May 2012

Penyusun

Muhamad Fajri Maulana M I

NIM. 113410027

DAFTAR ISI

Kata Pengantar ------------------------------------------------------------------ 1

Daftar Isi------------------------------------------------------------------------- 2

BAB I. PENDAHULUAN---------------------------------------------------------------- 3

1.1.Latar Belakang--------------------------------------------------------- 3

1.2.Rumusan Masalah------------------------------------------------------ 4

1.3.Tujuan------------------------------------------------------------------ 4

1.4.Manfaat----------------------------------------------------------------- 4

BAB II. LANDASAN TEORI---------------------------------------------------------- 6

2.1. Teori Pohon------------------------------------------------------------ 6

2.2. Binary Tree------------------------------------------------------------- 6

BAB III. PEMBAHASAN --------------------------------------------------------------- 8

3.1. Struktur Data Tree----------------------------------------------------- 8

3.2. Implementasi Binary Tree dengan Linked List ---------------------- 11

3.3. Inisialisasi Tree ------------------------------------------------------- 13

3.4. Menambahkan Node Pada Tree ------------------------------------- 13

3.5. Membaca dan Menampilkan Node pada Tree ----------------------- 14

3.6. Membuat Pohon Biner ----------------------------------------------- 16

3.7. Metode Traversal ---------------------------------------------------- 17

BAB IV KESIMPULAN---------------------------------------------------------------- 18

BAB V DAFTAR PUSTAKA--------------------------------------------------------- 19

BAB I

PENDAHULUAN

1.1. Latar Belakang

Salah satu penerapan teori pohon yang paling berguna dan dipakai yaitu konsep binary search tree dimana konsep ini memberikan struktur data yang memudahkan operasi pencarian, penambahan, dan penghapusan terhadap data. Operasi tersebut lebih efisien dan jauh lebih baik pada konsep ini dibanding sequential search pada senarai berkait dalam waktu eksekusi / run-time.

Dari konsep binary search tree ini dikembangkan lagi suatu struktur penyimpanan data yang merupakan modifikasi dari binary search tree tersebut yaitu AVL-Tree dan Splay Tree yang masing-masing mempunyai keunggulan pada kasus tertentu yang sekarang ini sering dijumpai.

AVL-Tree merupakan modifikasi binary search tree yang tinggi setiap upapohon kiri dan upapohon kanan sama atau setidaknya selisih antara keduanya tidak lebih dari 1. Keunggulan dari AVL-Tree antara lain untuk mengoptimasi pencarian data terutama untuk kasus pohon yang condong ke kiri atau ke kanan sehingga pencarian akan jauh lebih mudah apabila pohon tersebut seimbang. Kasus pohon yang condong ke kiri atau kanan itu mungkin saja terjadi terutama apabila penambahan elemen dan penghapusan elemen dilakukan terus-menerus dan tidak dapat diketahui urutannya.

Sedangkan Splay-Tree justru kebalikan dari AVL-Tree yang tidak mempermasalahkan kecondongan upapohonnya namun setiap kali data diakses maka simpul dari data yang diakses tersebut akan dinaikkan keatas mendekati akar pohon. Data yang sering diakses / aktif akan berada dekat pada akar pohon sehingga data tersebut mudah Dengan demikian dapat disimpulkan bahwa penerapan teori pohon sangatlah bermanfaat dalam kajian struktur data.

1.2. Rumusan Masalah

Bayangkan apabila kita ingin mencari sebuah data pada sebuah senarai berkait, tentunya tidak ada cara selain mencarinya secara sekuensial dari pointer elemen pertama senarai. Bandingkan jika kita melakukan pencarian di tabel kontigu dan dengan pencarian biner (binary search), tentunya pencarian akan lebih cepat. Dan sekarang bayangkan jika kita ingin melakukan operasi penambahan dan penghapusan elemen senarai. Operasi tersebut akan lebih lambat pada table kontigu daripada senarai berkait. Hal ini disebabkan karena operasi penambahan dan penghapusan pada tabel kontigu memerlukan pemindahan banyak entri data setiap saat, dibandingkan dengan senarai berkait yang hanya membutuhkan sedikit permainan pointer. 3

Dari permasalahan diatas tentunya dapat kita simpulkan bahwa alangkah baiknya jika kita dapat melakukan operasi pencarian dengan kecepatan eksekusi tinggi (seperti pada table kontigu dan pencarian biner) dan operasi penambahan dan penghapusan dengan kecepatan eksekusi tinggi (seperti pada senarai berkait).

1.3. Tujuan

Mempelajari variasi bagian-bagian dari tree sebagai suatu bentuk struktur tak linier
Mempelajari beberapa hubungan fakta yang direpresentasikan dalam sebuah tree, sehingga mampu merepresentasikan tree dalam permasalahan aslinya
Memahami bagaimana menulis program untuk tree, dan bagaimana mengartikannya kembali dalam bentuk permasalahan aslinya.
Mengimplementasikan struktur data Binary Tree menggunakan linked list.

1.4. Manfaat

Keunggulan Binary Search Tree akan sangat berguna, dimana Binary Search Tree dapat menjadi solusi permasalahan tersebut karena pencarian serta penambahan dan penghapusan elemennya memiliki kecepatan eksekusi yang tinggi. Operasi pencarian, penambahan, dan penghapusan pada Binary Search Tree memiliki run-time O (log n). serta manfaat lain diantaranya adalah:

Mampu mengimplementasikan beragam operasi pada struktur data binary tree

dengan Linked List.

Mampu melakukan pelacakan secara preorder, inorder dan post order pada binary tree.
Mampu memanfaatkan struktur data Binary Tree untuk menyelesaikan permasalahan.

BAB II

LANDASAN TEORI

2.1. Teori Pohon

Teori pohon merupakan salah satu teori yang cukup tua karena sudah dikenal sejak tahun 1857, dimana ketika itu matematikawan Inggris Arthur Cayley menggunakan teori pohon ini untuk menghitung jumlah senyawa kimia. Teori pohon ini sebenarnya adalah suatu mekanisme penyelesaian suatu masalah dengan menganalogikan permasalahan tersebut kedalam struktur pohon untuk memudahkan pencarian solusi masalah tersebut. Teori pohon ini juga merupakan salah satu penerapan konsep graf. Dimana pohon itu dapat didefinisikan sebagai graf tak-berarah terhubung yang tidak mengandung sirkuit. Kajian struktur data merupakan kajian yang sangat penting dalam bidang informatika. Dan di zaman sekarang ini yang teknologinya semakin berkembang, dibutuhkan struktur data yang efisien yang dapat meningkatkan kinerja program.

Teori pohon ini merupakan teori yang sangat berguna dalam struktur data dimana aplikasiaplikasi dari teori pohon ini dapat dijadikan struktur penyimpanan data yang sangat baik dalam kasus tertentu yang mana kasus tersebut sudah umum ditemui sekarang ini. Oleh karena itu dalam makalah ini akan dijelaskan beberapa aplikasi teori pohon yang dipakai untuk membentuk suatu struktur penyimpanan data yang efisien.

2.2. 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 Struktur Binary Tree.

Gambar Terminologi Tree.
BAB III

PEMBAHASAN

3.1. Struktur Data Tree

Dalam bab ini kita akan mempelajari satu bentuk struktur data tak linier yang mempunyai sifat-sifat khusus, yang dinamakan pohon (tree). Struktur ini biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen yang ada. Silsilah keluarga, hasil pertandingan yang berbentuk turnamen, atau struktur organisasi dari sebuah perusahaan adalah contoh dalam organisasi tree. Dalam pemrograman, sebuah pohon terdiri dari elemen-elemen yang dinamakan node(simpul) yang mana hubungan antar simpul bersifat hirarki. Simpul yang paling atas dari hirarki dinamakan root. Simpul yang berada di bawah root secara langsung, dinamakan anak dari root, yang mana biasanya juga mempunyai anak di bawahnya. Sehingga biasa disimpulkan, kecuali root, masing-masing simpul dalam hirarki mempunyai satu induk (parent).

Jumlah anak sebuah simpul induk sangat bergantung pada jenis dari pohon. Jumlah anak dari simpul induk ini dinamakan faktor percabangan. Pada bab ini pembahasan difokuskan pada binary tree, yaitu pohon yang mempunyai factor percabangan 2.

1. Deskripsi dari 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 dari simpul tersebut. Simpul yang berada di atas sebuah simpul dinamakan induk dari simpul tersebut.

Masing-masing simpul dalam binary tree terdiri dari tiga bagian : sebuah data dan dua buah pointer yang dinamakan pointer kiri dan kanan. 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 adalah simpul dari tree yang tidak mempunyai anak. Kadang-kadang ketika kita bekerja dengan beberapa pohon dalam satu waktu, maka pohon-pohon tersebut dinamakan sebua hutan.

2. Istilah-Istilah Dasar

Simpul juga mempunyai sibling, descendants, dan ancestors. Sibling dari sebuah simpul adalah anak lain dari induk simpul tersebut. Descendants dari sebuah simpul adalah semua simpul-simpul merupakan cabang (berada di bawah) simpul tersebut.

Anchestors dari sebuah simpul adalah semua simpul yang berada di atas antara simpul tersebut dengan root. Penampilan dari sebuah tree akan ditampilkan dengan berat dari tree tersebut, angka yang menunjukkan jumlah level yang ada di dalamnya.

Tingkat suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 1. Jika suatu simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya akan berada pada tingkatan N + 1.

Tinggi atau kedalaman dari suatu pohon adalah tingkat maksimum dari simpul dalam pohon dikurangi dengan 1. Selain tingkat, juga dikenal istilah derajad (degree) dari suatu simpul. Derajad suatu simpul dinyatakan sebagai banyaknya anak atau turunan dari simpul tersebut.

Gambar: Ilustrasi Sebuah Pohon Biner dengan Kedalaman 3

3. Penyajian Pohon Biner

Implementasi pohon biner dalam pemrograman dapat dilakukan dengan beberapa cara. Cara pertama adalah dengan menggunakan link list dan cara lain adalah dengan menggunakan cara berurutan. Dalam bab ini kita lebih banyak mempelajari cara implementasi biner menggunakan link list.

4. Deklarasi Pohon

Jika kita memperhatikan setiap simpul dalam pohon biner, kita bisa menyusun struktur data yang tepat dari simpul-simpul tersebut. Kita dapat melihat bahwa dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang kanan, dan informasi yang akan disimpan dalam simpul tersebut. Dengan memperhatikan hal ini, simpul dalam pohon biner disajikan sebagai berikut:

Gambar Simpul Pada Pohon Biner

Sesuai dengan gambar tersebut, maka deklarasi list yang sesuai adalah:

typedef char TypeInfo;

typedef struct Simpul *Tree;

struct Simpul {

TypeInfo Info;

tree Kiri, /* cabang kiri */

Kanan; /* cabang kanan */

};

Program Deklarasi dari Tree

3.2. 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.

Gambar 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:

Setiap node baru akan menempati posisi sebagai daun (leaf).
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.
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:

Jika node yang dihapus berposisi sebagai daun, dengan sederhana bisa dihapus.
Jika node memiliki satu anak, maka anak tersebut akan menggantikan posisi node yang dihapus.
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.

3.3. Inisialisasi Tree

Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum memiliki node sama sekali, sehingga masih kosong. Oleh karena itu perlu kita tambahkan kode berikut pada baris awal fungsi Main:

Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita buat, dengan nama *pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka pointer *pohon ditunjukkan ke NULL.

3.4. Menambahkan Node Pada Tree

Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner:

1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.

2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

a. Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

3.5. Membaca dan Menampilkan Node Pada Tree

Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif.

a. Kunjungan Pre-Order.

Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

1. Cetak isi (data) node yang sedang dikunjungi

2. Kunjungi kiri node tersebut,

- Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

- Jika kiri kosong (NULL), lanjut ke langkah ketiga.

3. Kunjungi kanan node tersebut,

- Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

b. Kunjungan In-Order.

1. Kunjungi kiri node tersebut,

- Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

- Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi

3. Kunjungi kanan node tersebut,

- Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

- Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

c. Kunjungan Post-Order.

1. Kunjungi kiri node tersebut,

- Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

- Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Kunjungi kanan node tersebut,

- Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

- Jika kanan kosong (NULL), lanjut ke langkah ketiga.

3.6. Membuat Pohon Biner

Tabel Program Deklarasi dan Tree memperlihatkan bagaimana proses pembentukan pohon biner dari sebuah persamaan.

Tabel Pembentukan Pohon Biner dari persamaan: (A+B)*((B-C)+D)

3.7. Metode Traversal

Proses traversing dari sebuah binary tree artinya melakukan kunjungan pada setiap simpul pada suatu pohon biner tepat satu kali. Dengan melakukan kunjungan secara lengkap, kita akan memperoleh informasi secara linear yang tersimpan dalam pohon biner. Dalam melakukan kunjungan pada sebuah pohon biner, kita akan memperlakukan hal yang sama pada setiap simpul pada cabang-cabangnya.

Urutan informasi yang tersimpan dalam pohon biner akan berbeda jika letak simpulnya ditukar. Dalam melakukan kunjungan kita perlu memperhatikan hal ini. Dengan alasan inilah kita bisa melakukan kunjungan dengan tiga cara, yaitu kunjungan secara preorder, inorder, dan secara postorder. Selain itu, berdasarkan kedudukan setiap simpul dalam pohon, juga bisa dilakukan kunjungan secara levelorder. Ketiga macam kunjungan yang pertama bisa dilaksanakan secara rekursif. Kunjungan preorder, juga disebut dengan depth first order, menggunakan urutan:

- Cetak isi simpul yang dikunjungi

- Kunjungi cabang kiri

- Kunjungi cabang kanan

Kunjungan secara inorder, juga sering disebut dengan symmetric order, menggunakan urutan:

- Kunjungi cabang kiri

- Cetak isi simpul yang dikunjungi

- Kunjungi cabang kanan

Kunjungan secara postorder menggunakan urutan:

- Kunjungi cabang kiri

- Kunjungi cabang kanan

- Cetak isi simpul yang dikunjungi

BAB IV

KESIMPULAN

Tree adalah sebuah struktur linier, biasanya digunakan untuk menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen yang ada. Ada beberapa istilah dalam tree ini, yang mana masing-masing istilah mempunyai arti dalam kaitannya dengan hirarki antar elemen dalam tree tersebut, seperti sibling, descendant dsb.

Dalam ilmu komputer, tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan. Node-node tersebut dihubungkan oleh sebuah vektor. Setiap node dapat memiliki 0 atau lebih node anak (child). Sebuah node yang memiliki node anak disebut node induk (parent). Sebuah node anak hanya memiliki satu node induk. Sesuai konvensi ilmu komputer, tree bertumbuh ke bawah, tidak seperti pohon di dunia nyata yang tumbuh ke atas. Dengan demikian node anak akan digambarkan berada di bawah node induknya.

BAB V

DAFTAR PUSTAKA