MAKALAH DESAIN DAN ANALISIS ALGORITMA
“BINARY TREE”
DISUSUN OLEH : 1. Nadim Achmad
(105060 807111009)
2. Dzurratul Ulya
(105060807111120)
3. Safer Yusuf
(105060803111004 )
PROGRAM TEKNOLOGI INFORMASI DAN ILMU KOMPUTER
UNIVERSITAS BRAWIJAYA
KATA PENGANTAR
Puji Syukur kami panjatkan kehadirat Allah SWT karena berkat limpahan rahmat dari-NYA kami selaku kelompok I dapat menyelesaikan makalah ini tepat pada waktunya,walaupun dalam keadaan yang sangat sederhana. Makalah ini berisikan tidak lanjut dari materi pembelajaran kita yang berjudul “Binary Tree” . Dengan segala keterbatasan yang kami miliki kami sajikan makalah ini dalam bentuk yang sangat sederhana maka dari itu kami selaku panyaji minta maaf yang sebesar-besarnya jika makalah ini masih begitu banyak kekurangan, baik itu yang kami sengaja ataupun tidak karena ini senua masih dalam proses pembelajaran kami yang tentunya tak lepas dari kodrad kami sebagai manusia biasa yang tak akan pernah luput dari kesalahan.
Malang, 20 Mei 2012
Kelompok I
BAB 1 PENDAHULUAN 1.1. Latar Belakang Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpeunan yang saling tak berhubungan satu sama lainnya (disebut subtree).Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop. 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. 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.
1.2 Permasalahan Pengertian Binary Tree
Binary tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunanhimpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree. Binary Tree adalah Suatu tree dengan syarat bahwa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child (anak simpul), Secara khusus anaknya dinamakan kiri dan kanan.
Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max = 2. Contoh : (1)
(2)
A
B
(3) A
A
C
B
B
D
Derajat keluar = 2
A adalah subtree kanan
A adalah subtree kiri
(4)
(5)
A
A
B
B
C
E
Bukan Binary Tree tapi General Tree karena bukan
D
F
Bukan Binary Tree tapi General Tree karena mempunyai derajat keluar > 2.
Sebuah pohon biner adalah grafik asiklis yang terhubung dimana setiap tingkatan dari sudut tidak lebih dari 3. Ini dapat ditunjukan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar. Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak; bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yg tak terkoneksi, membolehkan bermacam koneksi dalam komponen di gafik, kita memanggil struktur sebuah hutan.
Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada grafik langsung. Sebuah pohon biner dapat berarti:
Sebuah sudut tunggal. Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar daris setiap pohon biner.
Pohon biner dapat dikonstruksi dari bahasa pemrograman primitif dalam berbagai cara. Dalam bahasa yang menggunakan records dan referensi, pohon biner secara khas dikonstruksi dengan mengambil sebuah struktur simpul pohon yang memuat beberapa data dan referensi ke anak kiri dan anak kanan. Kadang-kadang itu juga memuat sebuah referensi ke ayahnya yang khas. JikA sebuah simpul mempunyai kurang dari dua anak, beberapa penunjuk anak dapat diatur kedalam nilai nol khusus, atau ke sebuah simpul sentinel. Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai((i-1)/2) (asumsikan akarnya memiliki indeks kosong). Metode ini menguntungkan dari banyak penyimpanan yang rapat dan memiliki referensi lokal yang lebih baik, tersitimewa selama sebuah preorder traversal. Bagaimanapun juga, ini terlalu mahal untuk perkembangannya dan boros tempat sebanding dengan 2h - n untuk sebuah pohon dengan tinggi h dengan nsimpul. Ini juga tidak menentukan susunan anak, tetapi memperbaiki akar tertentu.
Pada Binary Tree terdapat yang namanya simpul (node). Node pada binary tree maksimum berjumlah 2n-1 dan jumlah maksimum pada setiap tingkat adalah 2n
A
Tingkat ke-0, jumlah max=2’ Tingkat ke-1, jumlah max=2’
C
B
Tingkat ke-2, jumlah max=2’ D
E
F
G
Penghitungan jumlah node dalam tree dilakukan dengan cara mengunjungi setiap node, dimulai dari root ke subtree kiri, kemudian ke subtree kanan dan masing-masing node dicatat jumlahnya, dan terakhir jumlah node yang ada di subtree kiri dijumlahkan dengan jumlah node yang ada di subtree kanan ditambah 1 yaitu node root. Node root dalam sebuah tree adalah suatu node yang memiliki hiarki tertinggi dan dapat juga memiliki node-node anak. Semua node dapat ditelusuri dari node root tersebut. Node root adalah node khusus yang tercipta pertama kalinya. Node-node lain di bawah node root saling terhubung satu sama lain dan disebut subtree. Contoh penggunaan struktur pohon adalah pada silsilah keluarga, hasil pertandingan yang berbentuk turnamen, struktur organisasi dari sebuah perusahaan Jenis-Jenis Binary Tree Pada binary tree terdapat tiga jenis atau bentuk binary tree, diantaranya yaitu: 1. Full Binary Tree yaitu semua node atau simpul (kecuali leaf) pasti memiliki 2 anak dan tiap subtree memiliki panjang path yag sama. A
B
D
C
E
F
G
2. Complete Binary Tree yaitu pada dasarnya mirip dengan full binary tree, tapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node ((kecuali left ) memiliki 2 anak.
A
B
C
D
E
3. Skewed Binary Tree yaitu binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak. D
A
E
B
C
F
Operasi-Operasi pada Binary Tree Pada binary terdapat beberapa operator yang digunakan di dalamnya, diantaranya adalah: 1. Create, berguna untuk membentuk sebuah tree baru yang kosong. pohon = NULL; 2. Search adalah tree yang terurut dimana aturannya Semua data dibagian kiri subtree dari node t selalu lebih kecil dari data dalam node t itu sendiri dan semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t. 3. Clear, berguna untuk menghapus semua elemen tree. pohon = NULL; 4. Empty, berguna untuk mengetahui apakah tree kosong atau tidak int isEmpty(Tree *pohon){ if(pohon == NULL) return 1; else return 0;} 5. Insert, digunakan untuk menambah node ke dalam Tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.
6. Find, digunakan untuk mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya adalah tree tidak boleh kosong. 7. Traverse yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali. 8. Count, digunakan untuk menghitung jumlah node dalam Tree 9. Height, digunakan untuk mengetahui kedalaman sebuah Tree 10. Find Min dan Find Max, digunakan untuk mencari nilai terkecil dan terbesar pada Tree 11. Child, digunakan untuk mengetahui anak dari sebuah node (jika punya) Pada operator-operator yang bekerja pada binary tree terdapat beberapa operator yang memilki pendefenisian secara khusus, diataranya yaitu search, create, insert, transverse dan delete yang akan dibahas dalm makalah ini.
Binary Search Tree Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Aturan yang harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut: 1. Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri. 2. Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.
Suatu binary search tree dari himpunan N record (N1, N2, N3 . . . Nn) adalah suatu Binary Tree yang setiap vertex-nya (sebut Ri) ditempati oleh Ni untuk i=1,2,3 ... N. Vertex-vertex dari Binary Tree tsb. diatur sedemikian rupa sehingga untuk setiap Ri harus memenuhi syarat sbb : 1. Jika Rj = left (Ri) maka Nj < Ni 2. Jika Rj = right (Ri) maka Nj > Ni
Contoh : Diketahui key dari 7 record (K, M, L, N, P, O, Q) Binary Search Tree dari 7 key diatas dapat dibentuk : K
N
M
L
K
M
Trnsversal dalam binary tree Transversal dakam binary tree adalah proses menelusuri suatu Binary Tree sehingga sedemikian rupa setiap vertex dikunjungi hanya 1 kali. 3 aktivitas dalam Binary tree Transversal : 1. Visit the Root 2. Transverse the left subtree 3. Transverse the right subtree Beberapa macam pola penelusuran dalam Binary Tree Transversal : 1. Pre – Order-Transversal Pre order Transversal adalah penelusuran yang dimulai dari semua simpul induk kemudian melajutkan penelusuran pada anak simpul yang dimulai dari anak simpul kiri kemudian anak simpul kanan. 1
2
3
7 6
4
8
9
5
2. In-Order-Transversal In order transversal adalah penelusuran dimulai dari simpul anak disebelah kiri kemudian penelusuran dilanjutkan pada simpul induk dan yang terakhir pada simpul anak yang beradad di bagian kanan.
6
4
2
1
7
5
3
8
9
3. Post-Order-Transversal Post Order Transversal adalah penelusuran dimulai dari simpul anak kiri kemudian simpul anak kanan dan penelusuran terakhir ditujukan pada simpul induk. 9 5
3
8 4
1
6
7
2
4. Level-Order-Transversal Level Order Transversal adalah penelusuran dimulai dari tingkat ke i dan dilanjutka pada tingkat ke ( i+1). 1
2
5 5
4
8
3
6
7
9
1.3 Tujuan Adapun tujuan dari pembuatan makalah ini yaitu: 1. Untuk mengetahui defenisi dari Binary Tree 2. Untuk mengetahui bagaimana pembagian atau jenis-jenis Binary Tree 3. Untuk mengetahui Operator-operator apa saja yang bekerja di dalam Binary Tree.
BAB 2 TINJAUAN PUSTAKA
2.1 Konsep Algoritma Konsep algoritma yang dipakai yaitu, •
Decrease and conquer: metode desain algoritma dengan mereduksi persoalan menjadi beberapa sub-persoalan yang lebih kecil, tetapi selanjutnya hanya memproses satu sub-persoalan saja.Berbeda dengan divide and conquer yang memproses semua subpersoalan dan menggabung semua solusi setiap sub-persoalan.
•
Decrease and conquer terdiri dari dua tahapan:
1. Decrease: mereduksi persoalan menjadi beberapa persoalan yang lebih kecil (biasanya dua sub-persoalan). 2. Conquer: memproses satu sub-persoalan secara rekursif. Tidak ada tahap combine dalam decrease and conquer. •
Tiga varian decrease and conquer:
1. Decrease by a constant: ukuran instans persoalan direduksi sebesar konstanta yang sama setiap iterasi algoritma. Biasanya konstanta = 1. 2. Decrease by a constant factor: ukuran instans persoalan direduksi sebesar faktor konstanta yang sama setiap iterasi algoritma. Biasanya faktor konstanta = 2. 3. Decrease by a variable size: ukuran instans persoalan direduksi bervariasi pada setiap iterasi algoritma. Algoritma decrease and conquer: 1. Bagi himpunan koin menjadi dua sub-himpunan, masing-masing [n/2] koin. Jika n ganjil, maka satu buah koin tidak dimasukkan ke dalam kedua sub-himpunan. 2. Timbang kedua sub-himpunan dengan neraca. 3. Jika beratnya sama, berarti satu koin yang tersisa adalah palsu. 4. Jika beratnya tidak sama, maka ulangi proses untuk sub-himpunan yang beratnya lebih ringan (salah satu koin di dalamnya palsu).
Ukuran persoalan selalu berkurang dengan faktor setengah dari ukuran semula. Hanyasetengah bagian yang diproses, setengah bagian yang lain tidak diproses.
Jumlah penimbangan yang dilakukan adalah:
0
,n=1
1+T(n/2)
,n>1
T(n) =
Penyelesaian relasi rekurens T(n) mirip seperti binary search: T(n) = 1 + T(n/2) = …. + O(2log n)
BAB 3 IMPLEMENTASI PROGAM 3.1 Implementasi Program Pada Binary Tree Binary Tree dapat dibuat dengan menggunakan linked list secara rekursif dan linked list yang digunakan adalah double linked list non circular. Dimana, data yang pertama kali masuk akan menjadi node root. Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.
Contoh program seederhana dalam binary tree : #include
#include #include<stdio.h> #include<stdlib.h> struct node { int data; node *left; node *right; }; node *tree=NULL; node *insert(node *tree,int ele); void preorder(node *tree); void inorder(node *tree); void postorder(node *tree); int count=1; void main() { clrscr(); int ch,ele; do { clrscr(); cout<<"\n\t\a\a1----INSERT A NODE IN A BINARY TREE.\a\a"; cout<<"\n\t\a\a2----PRE-ORDER TRAVERSAL.\a\a"; cout<<"\n\t\a\a3----IN-ORDER TRAVERSAL.\a\a"; cout<<"\n\t\a\a4----POST-ORDER TRAVERSAL.\a\a"; cout<<"\n\t\a\a5----EXIT.\a\a"; cout<<"\n\t\a\aENTER CHOICE::\a\a"; cin>>ch; switch(ch) { case 1: cout<<"\n\t\a\aENTER THE ELEMENT::\a\a"; cin>>ele; tree=insert(tree,ele); break; case 2: cout<<"\n\t\a\a****PRE-ORDER TRAVERSAL OF A TREE****\a\a"; preorder(tree); break; case 3: cout<<"\n\t\a\a****IN-ORDER TRAVERSAL OF A TREE****\a\a"; inorder(tree); break;
case 4: cout<<"\n\t\a\a****POST-ORDER TRAVERSAL OF A TREE****\a\a"; postorder(tree); break; case 5: exit(0); } }while(ch!=5); } node *insert(node *tree,int ele) { if(tree==NULL) { tree=new node; tree->left=tree->right=NULL; tree->data=ele; count++; } else if(count%2==0) tree->left=insert(tree->left,ele); else tree->right=insert(tree->right,ele); return(tree); } void preorder(node *tree) { if(tree!=NULL) { cout<data; preorder(tree->left); preorder(tree->right); getch(); } } void inorder(node *tree) { if(tree!=NULL) { inorder(tree->left); cout<data; inorder(tree->right); getch(); } }
void postorder(node *tree) { if(tree!=NULL) { postorder(tree->left); postorder(tree->right); cout<data; getch(); } }
BAB 4 PENUTUP 4.1 Kesimpulan Dari uraian pada pembahasan yang disajikan, maka dapat ditarik sebuah kesimpulan bahwa : 1. Binary Tree adalah Suatu tree dengan syarat bahwa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary tree hanya boleh memiliki paling banyak dua child (anak simpul), Secara khusus anaknya dinamakan kiri dan kanan. 2. Terdapat tiga jenis binary tree diantaranya pertama adalah Full Binary Tree yaitu semua node atau simpul (kecuali leaf) pasti memiliki 2 anak dan tiap subtree memiliki panjang path yag sama,kedua adalah Complete Binary Tree yaitu pada dasarnya mirip dengan full binary tree, tapi tiap subtree boleh memiliki panjang path yang berbeda dan tiap node ((kecuali left ) memiliki 2 anak. Dan yang ketiga adalah Skewed Binary Tree yaitu binary tree yang semua nodenya (kecuali leaf) hanya memiliki satu anak. 3. Terdapat beberapa operator-operator yang bekerja dalam binary tree yaitu search,delete,insert,transverse,create,clear dan masih banyak yang lainnya. 4. Implementasi program yaitu dapat dibuat dengan menggunakan linked list secara rekursif dan linked list yang digunakan adalah double linked list non circular.
