際際滷

際際滷Share a Scribd company logo

Sd10

?
?
Arief Hertadi
Arief Hertadi
1 of 15
Download to read offline
www.hansmichael.com - Bab X. Konsep Dasar Tree BAB X Konsep Dasar Tree 10.1 Definisi Tree 10.2 Representasi dari Tree 10.3 Istilah-istilah dalam Tree 10.4 Binary Tree 10.5 Representasi Binary Tree 10.6 Traversal pada Binary Tree 10.7 Latihan Soal Setelah mempelajari struktur data linier pada bab-bab sebelumnya (stack, queue, dan linked list), maka pada bab ini akan dipelajari mengenai struktur data non linier, yaitu TREE. Contoh dari sebuah struktur tree dapat dilihat dalam kehidupan sehari-hari seperti silsilah keluarga atau struktur organisasi dari suatu perusahaan. 10.1 Definisi Tree Secara sederhana tree dapat didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut root, dan sisa elemen yang lain (yang disebut node) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama lain (disjoint), yang disebut dengan subtree. Node yang tidak mempunyai cabang disebut terminal node atau leaf, sedangkan node yang mempunyai cabang disebut branch node. Jumlah node pada sebuah tree merupakan bilangan terbatas (finite number). Apabila diamati pada setiap subtree, akan terlihat bahwa subtree pun mempunyai root dan subtree-subtree, dengan kata lain juga merupakan sebuah tree. Dengan pengertian tersebut, maka tree dapat didefinisikan secara rekursif sebagai berikut: ? Sebuah node tunggal adalah tree. ? Jika terdapat sebuah node N dan beberapa subtree T1, T2, T3, ..., Tk yang tidak saling berhubungan, dan berakar pada node-node N1, N2, N3, ..., Nk, maka dari 84
www.hansmichael.com - Bab X. Konsep Dasar Tree 85 node N dan subtree-subtree ini dapat dibentuk sebuah tree yang berakar pada node N.Contoh: ? Tree dengan 12 node dan root N0 T1 = {N1, N2, N3, N4, N5, N6} T2 = {N7} T3 = {N8, N9, N10} ? T1 merupakan tree dengan root N1 T11 = {N2} T12 = {N3} T13 = {N4, N5, N6} ? T2 merupakan tree dengan root N2 ? T3 merupakan tree dengan root N3 T31 = {N9} T32 = {N10, N11} ? T13 merupakan tree dengan root N4 T131 = {N5} T132 = {N6} ? T32 merupakan tree dengan root N10 T321 = {N11} N0 N1 N7 N8 N2 N3 N4 N9 N10 N5 N6 N11 Gambar 10.1 Representasi Tree
www.hansmichael.com - Bab X. Konsep Dasar Tree 86 10.2 Representasi dari Tree Ada beberapa cara untuk menggambarkan sebuah tree, yaitu: 1. Pedigree chart N0 N1 N5 N6 N2 N3 N4 N7 N8 2. Lineal chart N2 N1 N3 N4 N0 N5 N7 N6 N8 3. Diagram Venn atau Nested Sets N0 N5 N2 N3 N6 N7 N8 N1 N4 4. Nested parentheses (N0 (N1 (N2) (N3) (N4)) (N5) (N6 (N7) (N8)))
www.hansmichael.com - Bab X. Konsep Dasar Tree 87 5. Bar chart N0 N1 N2 N3 N4 N5 N6 N7 N8 6. Level-number notation 1 N0 2 N1 3 N2 3 N3 3 N4 2 N5 2 N6 3 N7 3 N8 10.3 Istilah-Istilah dalam Tree Dalam mempelajari struktur data non linier ini, akan ditemui banyak istilah- istilah yang dipergunakan untuk menyajikan sebuah tree. Berikut ini akan dibahas istilah-istilah yang sering digunakan dalam tree. 10.3.1 Level (Tingkat) Level sebuah node adalah satu ditambah panjang path dari root ke node tersebut, sehingga level root selalu satu. Jika suatu node terletak pada level N, maka node-node yang merupakan child-nya terletak pada level N +1. Sebagai contoh, berikut ini diperlihatkan sebuah tree (12 node) lengkap dengan nomor level untuk setiap nodenya.
www.hansmichael.com - Bab X. Konsep Dasar Tree 88 Level/Tingkat N0 1 N1 N7 N8 2 N2 N3 N4 N9 N10 3 N5 N6 N11 4 Gambar 10.2 Level pada Tree Selain definisi di atas, ada juga beberapa buku yang menyatakan bahwa root dinyatakan sebagai level 0, dan node-node lainnya dinyatakan sebagai level 1 lebih tinggi dari parent-nya. Buku ini menggunakan definisi yang pertama, yaitu bahwa root dikatakan berlevel 1. 10.3.2 Degree (Derajat) Dikenal dua macam degree/derajat dari sebuah node yaitu: 1. Out-degree (atau sering disebut degree) yaitu jumlah subtree dalam node tersebut. Degree dari leaf atau terminal node selalu nol. 2. In-degree yaitu jumlah path yang masuk ke dalam node tersebut. In-degree dari root selalu nol dan untuk node-node lainnya selalu satu. Contoh: Dari gambar tree di atas: ? Node N0 mempunyai out-degree = 3 dan in-degree = 0. ? Node N1 mempunyai out-degree = 3 dan in-degree = 1. ? Node N2 mempunyai out-degree = 1 dan in-degree = 1. ? Node N3 mempunyai out-degree = 1 dan in-degree = 1. ? Node N4 mempunyai out-degree = 2 dan in-degree = 1. ? dan seterusnya.
www.hansmichael.com - Bab X. Konsep Dasar Tree 89 Leaf sering disebut sebagai external node (node luar), sedangkan node-node selain leaf dan root disebut internal node (node dalam). 10.3.3 Height (Tinggi) atau Depth (Kedalaman) Tinggi atau kedalaman dari suatu tree adalah level maksimum dari node dalam tree tersebut dikurangi satu. Untuk contoh tree di atas, tinggi tree tersebut adalah 4 - 1 = 3, karena level maksimumnya adalah 4. 10.3.4 Ancestor dan Descendant Ancestor suatu node yaitu semua node yang terletak dalam satu jalur dengan node tersebut dari root sampai node yang ditinjau. Sebagai contoh, ancestor dari node N6 adalah N0, N1, dan N4. Descendant suatu node yaitu semua node yang dapat dicapai dari node tersebut. Sebagai contoh, descendant dari node N1 adalah N2, N3, N4, N5, dan N6. 10.3.5 Parent (Father) dan Child (Son) Parent suatu node adalah sebuah node yang dapat mencapai node tersebut dengan path tunggal. Sebagai contoh, parent dari N2 adalah N1, parent dari N5 adalah N4, parent dari N10 adalah N8, dan sebagainya. Child suatu node adalah semua node yang dapat dicapai oleh node tersebut dengan sebuah path saja. Sebagai contoh, child dari N1 adalah N2, N3, dan N4; child dari N4 adalah N5 dan N6; dan sebagainya. 10.3.6 Forest Forest adalah kumpulan tree yang tidak saling berhubungan (disjoint). Jika pada tree di atas, node N0 dihapus menyebabkan terjadi sebuah forest dengan tiga tree (dapat dilihat pada gambar berikut ini). N1 N7 N8 N2 N3 N4 N9 N10 N5 N6 N11 Gambar 10.3 Forest
www.hansmichael.com - Bab X. Konsep Dasar Tree 90 10.3.7 Ordered Tree Definisi ordered tree yaitu: ? Sebuah tree yang di dalamnya terdapat aturan untuk menyusun node-node dalam level yang sama, atau ? Sebuah tree dimana setiap subtree pada semua node di dalamnya membentuk himpunan yang berurutan (ordered set). Urutan node-node dapat bersifat ascending (urut naik) dan dapat pula bersifat descending (urut turun). Gambar 10.4 merupakan contoh dari non-ordered tree dan ordered tree. B tidak urut Y A Z C I H J P O N X (a) B urut A Y Z C H I J P N O X (b) Gambar 10.4 Non-Ordered Tree (a) dan Ordered Tree (b) 10.3.8 m-ary Tree m-ary tree adalah tree yang out-degree setiap node di dalamnya lebih kecil atau sama dengan m. Apabila m = 2, maka disebut dengan binary tree. Untuk contoh ordered tree di atas, juga dapat dikatakan sebagai 3-ary tree.
www.hansmichael.com - Bab X. Konsep Dasar Tree 91 10.3.9 Balance Tree Balance tree yaitu tree dimana leaf-leafnya terletak pada level h dan h-1, sehingga jarak antara sebuah leaf dan leaf terbawah paling banyak 1. Contoh balance tree adalah AVL-tree dan B-tree yang akan dibahas pada bab XIII dan bab XV. Gambar 10.5 merupakan contoh balance tree dan non-balance tree. D D B F F A C G E G (a) (b) Gambar 10.5 Balance Tree (a) dan Non-Balance Tree (b) 10.3.10 Complete m-ary Tree dan Full m-ary Tree Complete m-ary tree yaitu suatu m-ary tree yang out-degree setiap node di dalamnya sama dengan nol (merupakan leaf) atau sama dengan m. Sedangkan full m-ary tree adalah complete m-ary tree dimana leaf-leafnya terletak pada level yang sama. 10.4 Binary Tree Setelah mengetahui tree secara umum, maka untuk selanjutnya fokus pembahasan akan diarahkan pada tree yang hanya mempunyai dua buah subtree saja (subtree kiri dan subtree kanan) yang disebut sebagai binary tree. 10.4.1 Konsep Dasar Binary Tree Binary tree adalah himpunan dengan jumlah terbatas yaitu m buah node (m − 0), yang selain kosong (m = 0) hanya dapat berisi sebuah node root yang memiliki dua buah subtree yang masing-masing disebut SUB BINARY TREE KIRI dan SUB BINARY TREE KANAN. Jika m = 0 maka disebut EMPTY BINARY TREE. 10.4.2 Konversi dari General Tree ke Binary Tree Apabila suatu general tree dapat dinyatakan sebagai binary tree, maka perlu dilakukan proses konversi dari general tree ke binary tree. Gambar di bawah ini
www.hansmichael.com - Bab X. Konsep Dasar Tree 92 memperlihatkan urutan proses konversi struktur general tree menjadi struktur binary tree. B B A A Y Z C Y C H I J P H Z N O X I J I II N P O X B A Z Y H J P C I X N O Gambar 10.6 Konversi General Tree ke Binary Tree Dari gambar 10.6 terlihat bahwa terdapat dua tahap konversi yaitu: ? Tahap pertama yaitu menghapus semua cabang (branch) yang terhubung pada setiap node kecuali cabang yang paling kiri. Selanjutnya menghubungkan semua node pada level yang sama dengan branch. ? Tahap kedua yaitu mengubah menjadi binary tree dimana branch kiri adalah branch yang vertikal dan branch kanan adalah branch yang horisontal. Proses konversi ini dapat pula diterapkan untuk mengkonversi sebuah forest menjadi binary tree, dan dapat dilihat pada contoh gambar 10.7.
www.hansmichael.com - Bab X. Konsep Dasar Tree 93 A G B E H I J C D F C D I A G B E H I J C D F C D II A B G C E H D F I J C Gambar 10.7 D Konversi Forest ke Binary Tree 10.5 Representasi Binary Tree Apabila diperhatikan node-node dalam binary tree, maka akan terlihat bahwa dalam setiap node secara umum selalu terdiri dari dua buah pointer untuk menunjukkan subtree kiri dan subtree kanan, serta informasi yang akan disimpan dalam node tersebut. Struktur penyimpanan informasi ini terbagai menjadi:
www.hansmichael.com - Bab X. Konsep Dasar Tree 94 10.5.1 Representasi Penyimpanan Linked Cara pertama adalah penyimpanan node secara linked, dalam arti menggunakan tipe data pointer. Pada cara ini, struktur node akan disajikan sebagai berikut: LPtr Info RPtr Jika struktur node tersebut diimplementasikan ke dalam Pascal, maka deklarasi node yang sesuai adalah: 1: TYPE 2: BinTreeType = ^BinNodeType; 3: BinNodeType = RECORD 4: LPtr : BinTreeType; 5: Info : BinInfoType; 6: RPtr : BinTreeType; 7: END; Gambar 10.8 adalah binary tree dan representasinya dalam penyimpanan secara linked. Pointer T menunjukkan alamat dari node root, sedang subtree yang kosong diwakili dengan pointer yang bernilai NIL. A T B F A C E G H B F D C E G H F Gambar 10.8 Binary Tree dan Representasi dalam Linked List 10.5.2 Representasi Penyimpanan Threaded Pada representasi secara linked dapat disimpulkan bahwa apabila pada sebuah binary tree terdapat n buah node, maka jumlah pointer nil adalah n + 1 buah dari total pointer adalah 2n buah. Hal ini merupakan pemborosan tempat,
www.hansmichael.com - Bab X. Konsep Dasar Tree 95 dan pada representasi penyimpanan threaded, pointer nil diganti dengan thread link. Pembahasan lebih lanjut mengenai threaded terdapat pada bab XII. 10.5.3 Representasi Penyimpanan Sekuensial Telah diketahui bahwa tidak semua bahasa pemrograman mempunyai tipe data pointer (linked allocation), sehingga perlu diketahui pula representasi binary tree dengan menggunakan sequential allocation (array). Dalam representasi ini, perlu dipersiapkan dahulu sebuah array satu dimensi (vektor). Jumlah elemen maksimum array ditentukan berdasarkan jumlah node dari sebuah full binary tree dengan suatu ketinggian tertentu. Apabila tinggi sebuah full binary tree adalah h, maka jumlah node pada binary tree tersebut adalah 2h + 1 - 1. Misalkan terdapat sebuah full binary tree dengan tinggi = 5, maka jumlah nodenya = 26 - 1 = 64 - 1 = 63 buah. Setelah mempersiapkan vektor sebagai media penyimpan binary tree, selanjutnya perlu diperhatikan aturan-aturan penempatan node pada vektor yaitu sebagai berikut: 1. Elemen pertama vektor adalah root. 2. Child kiri dari elemen vektor ke-i adalah elemen vektor ke-2i dan child kanan dari elemen vektor ke-i adalah elemen vektor ke-(2i + 1). Dengan memperhatikan aturan tersebut, maka binary tree seperti contoh pada representasi linked, apabila disajikan dalam bentuk array maka menjadi seperti gambar berikut ini: Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Info A B F C E G H - D - - - - - - 10.6 Traversal pada Binary Tree Proses traversal adalah proses melakukan kunjungan pada setiap node pada suatu binary tree tepat satu kali. Dengan melakukan kunjungan secara lengkap, maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree. Terdapat tiga cara untuk melakukan kunjungan itu, yaitu: 1. Traversal preorder (depth first order) Dilaksanakan dengan jalan mencetak isi node yang dikunjungi lalu melakukan kunjungan ke subtree kiri dan selanjutnya ke subtree kanan. Algoritma umum traversal preorder adalah sebagai berikut:
www.hansmichael.com - Bab X. Konsep Dasar Tree 96 ? Jika tree kosong, maka keluar. ? Proses node root. ? Traverse subtree kiri secara preorder. ? Traverse subtree kanan secara preorder. 2. Traversal inorder (symmetric order) Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, mencetak isi node yang dikunjungi, lalu melakukan kunjungan ke subtree kanan. Algoritma umum traversal inorder adalah sebagai berikut: ? Jika tree kosong, maka keluar. ? Traverse subtree kiri secara inorder. ? Proses node root. ? Traverse subtree kanan secara inorder. 3. Traversal postorder Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, lalu ke subtree kanan, dan selanjutnya mencetak isi node yang dikunjungi. Algoritma umum traversal inorder adalah sebagai berikut: ? Jika tree kosong, maka keluar. ? Traverse subtree kiri secara postorder. ? Traverse subtree kanan secara postorder. ? Proses node root. Semua algoritma traversal (preorder, inorder, postorder) yang diberikan di atas berupa algoritma rekursif, dan sebenarnya dapat dikerjakan secara iteratif dengan bantuan stack. Contoh: diberikan ekspresi matematika ((A * B) - (C ^ D)) + (E / F), apabila digambarkan dalam bentuk binary tree menjadi seperti gambar 10.9.
www.hansmichael.com - Bab X. Konsep Dasar Tree 97 + - / * ^ E F A B C D Gambar 10.9 Representasi Ekspresi Matematika dalam Binary Tree Apabila binary tree di atas dikunjungi: ? secara preorder akan menghasilkan: +-*AB^CD/EF ? secara inorder akan menghasilkan: A*C-C^D+E/F ? secara postorder akan menghasilkan: AB+CD^-EF/+ 10.7 Latihan Soal 1. Tentukan level dan degree dari masing-masing node dalam tree yang ada pada gambar 10.10. A B K C F G D E H J I L M Gambar 10.10 Non Binary tree 2. Gambarkan bentuk tree pada soal no.1 dengan diagram Venn, nested parentheses, bar chart dan level-number notation. 3. Ubahlah ordered tree pada soal no. 1 menjadi sebuah binary tree.
www.hansmichael.com - Bab X. Konsep Dasar Tree 98 4. Bagaimanakah representasi sekuensial dari binary tree jawaban soal no. 3? Sebelumnya tentukan dahulu tinggi maksimum dari binary tree yang dapat direpresentasikan dalam array tersebut. 5. Lakukanlah proses traversal preorder, inorder dan postorder pada binary tree jawaban soal no. 3. 6. Buatlah tiga buah procedure iteratif untuk melakukan traversal inorder, preorder dan postorder pada sebuah binary tree. 7. Buatlah sebuah procedure untuk melakukan traversal level order (berdasarkan level dari tree tersebut) pada sebuah binary tree dengan bantuan stack atau queue. 8. Buatlah sebuah function untuk mengembalikan jumlah node pada sebuah binary tree. 9. Buatlah sebuah function untuk mengembalikan ketinggian dari sebuah binary tree. 10. Buatlah tiga buah function untuk mengembalikan status (benar atau salah) apakah suatu binary tree merupakan balance tree, complete binary tree, full binary tree. 11. Gambarkan binary tree yang dimaksud: a) Traversal preorder pada sebuah binary tree menghasilkan urutan ｀A B C D E F G H I¨, sedangkan traversal inorder-nya menghasilkan urutan ｀C D E B F A I H G¨. b) Traversal postorder pada sebuah binary tree menghasilkan urutan ｀E D A C G F B H¨, sedangkan jumlah child untuk masing-masing node adalah sebagai berikut: A = 1, B = 2, C = 0, D = 1, E = 0, F = 1, G = 0 dan H = 2. 12. Buatlah sebuah program untuk mengkonversi antar ketiga notasi ekspresi matematika (prefix, infix dan suffix) dengan menggunakan binary tree.

More Related Content

Sd10

  • 1. www.hansmichael.com - Bab X. Konsep Dasar Tree BAB X Konsep Dasar Tree 10.1 Definisi Tree 10.2 Representasi dari Tree 10.3 Istilah-istilah dalam Tree 10.4 Binary Tree 10.5 Representasi Binary Tree 10.6 Traversal pada Binary Tree 10.7 Latihan Soal Setelah mempelajari struktur data linier pada bab-bab sebelumnya (stack, queue, dan linked list), maka pada bab ini akan dipelajari mengenai struktur data non linier, yaitu TREE. Contoh dari sebuah struktur tree dapat dilihat dalam kehidupan sehari-hari seperti silsilah keluarga atau struktur organisasi dari suatu perusahaan. 10.1 Definisi Tree Secara sederhana tree dapat didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut root, dan sisa elemen yang lain (yang disebut node) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama lain (disjoint), yang disebut dengan subtree. Node yang tidak mempunyai cabang disebut terminal node atau leaf, sedangkan node yang mempunyai cabang disebut branch node. Jumlah node pada sebuah tree merupakan bilangan terbatas (finite number). Apabila diamati pada setiap subtree, akan terlihat bahwa subtree pun mempunyai root dan subtree-subtree, dengan kata lain juga merupakan sebuah tree. Dengan pengertian tersebut, maka tree dapat didefinisikan secara rekursif sebagai berikut: ? Sebuah node tunggal adalah tree. ? Jika terdapat sebuah node N dan beberapa subtree T1, T2, T3, ..., Tk yang tidak saling berhubungan, dan berakar pada node-node N1, N2, N3, ..., Nk, maka dari 84
  • 2. www.hansmichael.com - Bab X. Konsep Dasar Tree 85 node N dan subtree-subtree ini dapat dibentuk sebuah tree yang berakar pada node N.Contoh: ? Tree dengan 12 node dan root N0 T1 = {N1, N2, N3, N4, N5, N6} T2 = {N7} T3 = {N8, N9, N10} ? T1 merupakan tree dengan root N1 T11 = {N2} T12 = {N3} T13 = {N4, N5, N6} ? T2 merupakan tree dengan root N2 ? T3 merupakan tree dengan root N3 T31 = {N9} T32 = {N10, N11} ? T13 merupakan tree dengan root N4 T131 = {N5} T132 = {N6} ? T32 merupakan tree dengan root N10 T321 = {N11} N0 N1 N7 N8 N2 N3 N4 N9 N10 N5 N6 N11 Gambar 10.1 Representasi Tree
  • 3. www.hansmichael.com - Bab X. Konsep Dasar Tree 86 10.2 Representasi dari Tree Ada beberapa cara untuk menggambarkan sebuah tree, yaitu: 1. Pedigree chart N0 N1 N5 N6 N2 N3 N4 N7 N8 2. Lineal chart N2 N1 N3 N4 N0 N5 N7 N6 N8 3. Diagram Venn atau Nested Sets N0 N5 N2 N3 N6 N7 N8 N1 N4 4. Nested parentheses (N0 (N1 (N2) (N3) (N4)) (N5) (N6 (N7) (N8)))
  • 4. www.hansmichael.com - Bab X. Konsep Dasar Tree 87 5. Bar chart N0 N1 N2 N3 N4 N5 N6 N7 N8 6. Level-number notation 1 N0 2 N1 3 N2 3 N3 3 N4 2 N5 2 N6 3 N7 3 N8 10.3 Istilah-Istilah dalam Tree Dalam mempelajari struktur data non linier ini, akan ditemui banyak istilah- istilah yang dipergunakan untuk menyajikan sebuah tree. Berikut ini akan dibahas istilah-istilah yang sering digunakan dalam tree. 10.3.1 Level (Tingkat) Level sebuah node adalah satu ditambah panjang path dari root ke node tersebut, sehingga level root selalu satu. Jika suatu node terletak pada level N, maka node-node yang merupakan child-nya terletak pada level N +1. Sebagai contoh, berikut ini diperlihatkan sebuah tree (12 node) lengkap dengan nomor level untuk setiap nodenya.
  • 5. www.hansmichael.com - Bab X. Konsep Dasar Tree 88 Level/Tingkat N0 1 N1 N7 N8 2 N2 N3 N4 N9 N10 3 N5 N6 N11 4 Gambar 10.2 Level pada Tree Selain definisi di atas, ada juga beberapa buku yang menyatakan bahwa root dinyatakan sebagai level 0, dan node-node lainnya dinyatakan sebagai level 1 lebih tinggi dari parent-nya. Buku ini menggunakan definisi yang pertama, yaitu bahwa root dikatakan berlevel 1. 10.3.2 Degree (Derajat) Dikenal dua macam degree/derajat dari sebuah node yaitu: 1. Out-degree (atau sering disebut degree) yaitu jumlah subtree dalam node tersebut. Degree dari leaf atau terminal node selalu nol. 2. In-degree yaitu jumlah path yang masuk ke dalam node tersebut. In-degree dari root selalu nol dan untuk node-node lainnya selalu satu. Contoh: Dari gambar tree di atas: ? Node N0 mempunyai out-degree = 3 dan in-degree = 0. ? Node N1 mempunyai out-degree = 3 dan in-degree = 1. ? Node N2 mempunyai out-degree = 1 dan in-degree = 1. ? Node N3 mempunyai out-degree = 1 dan in-degree = 1. ? Node N4 mempunyai out-degree = 2 dan in-degree = 1. ? dan seterusnya.
  • 6. www.hansmichael.com - Bab X. Konsep Dasar Tree 89 Leaf sering disebut sebagai external node (node luar), sedangkan node-node selain leaf dan root disebut internal node (node dalam). 10.3.3 Height (Tinggi) atau Depth (Kedalaman) Tinggi atau kedalaman dari suatu tree adalah level maksimum dari node dalam tree tersebut dikurangi satu. Untuk contoh tree di atas, tinggi tree tersebut adalah 4 - 1 = 3, karena level maksimumnya adalah 4. 10.3.4 Ancestor dan Descendant Ancestor suatu node yaitu semua node yang terletak dalam satu jalur dengan node tersebut dari root sampai node yang ditinjau. Sebagai contoh, ancestor dari node N6 adalah N0, N1, dan N4. Descendant suatu node yaitu semua node yang dapat dicapai dari node tersebut. Sebagai contoh, descendant dari node N1 adalah N2, N3, N4, N5, dan N6. 10.3.5 Parent (Father) dan Child (Son) Parent suatu node adalah sebuah node yang dapat mencapai node tersebut dengan path tunggal. Sebagai contoh, parent dari N2 adalah N1, parent dari N5 adalah N4, parent dari N10 adalah N8, dan sebagainya. Child suatu node adalah semua node yang dapat dicapai oleh node tersebut dengan sebuah path saja. Sebagai contoh, child dari N1 adalah N2, N3, dan N4; child dari N4 adalah N5 dan N6; dan sebagainya. 10.3.6 Forest Forest adalah kumpulan tree yang tidak saling berhubungan (disjoint). Jika pada tree di atas, node N0 dihapus menyebabkan terjadi sebuah forest dengan tiga tree (dapat dilihat pada gambar berikut ini). N1 N7 N8 N2 N3 N4 N9 N10 N5 N6 N11 Gambar 10.3 Forest
  • 7. www.hansmichael.com - Bab X. Konsep Dasar Tree 90 10.3.7 Ordered Tree Definisi ordered tree yaitu: ? Sebuah tree yang di dalamnya terdapat aturan untuk menyusun node-node dalam level yang sama, atau ? Sebuah tree dimana setiap subtree pada semua node di dalamnya membentuk himpunan yang berurutan (ordered set). Urutan node-node dapat bersifat ascending (urut naik) dan dapat pula bersifat descending (urut turun). Gambar 10.4 merupakan contoh dari non-ordered tree dan ordered tree. B tidak urut Y A Z C I H J P O N X (a) B urut A Y Z C H I J P N O X (b) Gambar 10.4 Non-Ordered Tree (a) dan Ordered Tree (b) 10.3.8 m-ary Tree m-ary tree adalah tree yang out-degree setiap node di dalamnya lebih kecil atau sama dengan m. Apabila m = 2, maka disebut dengan binary tree. Untuk contoh ordered tree di atas, juga dapat dikatakan sebagai 3-ary tree.
  • 8. www.hansmichael.com - Bab X. Konsep Dasar Tree 91 10.3.9 Balance Tree Balance tree yaitu tree dimana leaf-leafnya terletak pada level h dan h-1, sehingga jarak antara sebuah leaf dan leaf terbawah paling banyak 1. Contoh balance tree adalah AVL-tree dan B-tree yang akan dibahas pada bab XIII dan bab XV. Gambar 10.5 merupakan contoh balance tree dan non-balance tree. D D B F F A C G E G (a) (b) Gambar 10.5 Balance Tree (a) dan Non-Balance Tree (b) 10.3.10 Complete m-ary Tree dan Full m-ary Tree Complete m-ary tree yaitu suatu m-ary tree yang out-degree setiap node di dalamnya sama dengan nol (merupakan leaf) atau sama dengan m. Sedangkan full m-ary tree adalah complete m-ary tree dimana leaf-leafnya terletak pada level yang sama. 10.4 Binary Tree Setelah mengetahui tree secara umum, maka untuk selanjutnya fokus pembahasan akan diarahkan pada tree yang hanya mempunyai dua buah subtree saja (subtree kiri dan subtree kanan) yang disebut sebagai binary tree. 10.4.1 Konsep Dasar Binary Tree Binary tree adalah himpunan dengan jumlah terbatas yaitu m buah node (m − 0), yang selain kosong (m = 0) hanya dapat berisi sebuah node root yang memiliki dua buah subtree yang masing-masing disebut SUB BINARY TREE KIRI dan SUB BINARY TREE KANAN. Jika m = 0 maka disebut EMPTY BINARY TREE. 10.4.2 Konversi dari General Tree ke Binary Tree Apabila suatu general tree dapat dinyatakan sebagai binary tree, maka perlu dilakukan proses konversi dari general tree ke binary tree. Gambar di bawah ini
  • 9. www.hansmichael.com - Bab X. Konsep Dasar Tree 92 memperlihatkan urutan proses konversi struktur general tree menjadi struktur binary tree. B B A A Y Z C Y C H I J P H Z N O X I J I II N P O X B A Z Y H J P C I X N O Gambar 10.6 Konversi General Tree ke Binary Tree Dari gambar 10.6 terlihat bahwa terdapat dua tahap konversi yaitu: ? Tahap pertama yaitu menghapus semua cabang (branch) yang terhubung pada setiap node kecuali cabang yang paling kiri. Selanjutnya menghubungkan semua node pada level yang sama dengan branch. ? Tahap kedua yaitu mengubah menjadi binary tree dimana branch kiri adalah branch yang vertikal dan branch kanan adalah branch yang horisontal. Proses konversi ini dapat pula diterapkan untuk mengkonversi sebuah forest menjadi binary tree, dan dapat dilihat pada contoh gambar 10.7.
  • 10. www.hansmichael.com - Bab X. Konsep Dasar Tree 93 A G B E H I J C D F C D I A G B E H I J C D F C D II A B G C E H D F I J C Gambar 10.7 D Konversi Forest ke Binary Tree 10.5 Representasi Binary Tree Apabila diperhatikan node-node dalam binary tree, maka akan terlihat bahwa dalam setiap node secara umum selalu terdiri dari dua buah pointer untuk menunjukkan subtree kiri dan subtree kanan, serta informasi yang akan disimpan dalam node tersebut. Struktur penyimpanan informasi ini terbagai menjadi:
  • 11. www.hansmichael.com - Bab X. Konsep Dasar Tree 94 10.5.1 Representasi Penyimpanan Linked Cara pertama adalah penyimpanan node secara linked, dalam arti menggunakan tipe data pointer. Pada cara ini, struktur node akan disajikan sebagai berikut: LPtr Info RPtr Jika struktur node tersebut diimplementasikan ke dalam Pascal, maka deklarasi node yang sesuai adalah: 1: TYPE 2: BinTreeType = ^BinNodeType; 3: BinNodeType = RECORD 4: LPtr : BinTreeType; 5: Info : BinInfoType; 6: RPtr : BinTreeType; 7: END; Gambar 10.8 adalah binary tree dan representasinya dalam penyimpanan secara linked. Pointer T menunjukkan alamat dari node root, sedang subtree yang kosong diwakili dengan pointer yang bernilai NIL. A T B F A C E G H B F D C E G H F Gambar 10.8 Binary Tree dan Representasi dalam Linked List 10.5.2 Representasi Penyimpanan Threaded Pada representasi secara linked dapat disimpulkan bahwa apabila pada sebuah binary tree terdapat n buah node, maka jumlah pointer nil adalah n + 1 buah dari total pointer adalah 2n buah. Hal ini merupakan pemborosan tempat,
  • 12. www.hansmichael.com - Bab X. Konsep Dasar Tree 95 dan pada representasi penyimpanan threaded, pointer nil diganti dengan thread link. Pembahasan lebih lanjut mengenai threaded terdapat pada bab XII. 10.5.3 Representasi Penyimpanan Sekuensial Telah diketahui bahwa tidak semua bahasa pemrograman mempunyai tipe data pointer (linked allocation), sehingga perlu diketahui pula representasi binary tree dengan menggunakan sequential allocation (array). Dalam representasi ini, perlu dipersiapkan dahulu sebuah array satu dimensi (vektor). Jumlah elemen maksimum array ditentukan berdasarkan jumlah node dari sebuah full binary tree dengan suatu ketinggian tertentu. Apabila tinggi sebuah full binary tree adalah h, maka jumlah node pada binary tree tersebut adalah 2h + 1 - 1. Misalkan terdapat sebuah full binary tree dengan tinggi = 5, maka jumlah nodenya = 26 - 1 = 64 - 1 = 63 buah. Setelah mempersiapkan vektor sebagai media penyimpan binary tree, selanjutnya perlu diperhatikan aturan-aturan penempatan node pada vektor yaitu sebagai berikut: 1. Elemen pertama vektor adalah root. 2. Child kiri dari elemen vektor ke-i adalah elemen vektor ke-2i dan child kanan dari elemen vektor ke-i adalah elemen vektor ke-(2i + 1). Dengan memperhatikan aturan tersebut, maka binary tree seperti contoh pada representasi linked, apabila disajikan dalam bentuk array maka menjadi seperti gambar berikut ini: Posisi 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Info A B F C E G H - D - - - - - - 10.6 Traversal pada Binary Tree Proses traversal adalah proses melakukan kunjungan pada setiap node pada suatu binary tree tepat satu kali. Dengan melakukan kunjungan secara lengkap, maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree. Terdapat tiga cara untuk melakukan kunjungan itu, yaitu: 1. Traversal preorder (depth first order) Dilaksanakan dengan jalan mencetak isi node yang dikunjungi lalu melakukan kunjungan ke subtree kiri dan selanjutnya ke subtree kanan. Algoritma umum traversal preorder adalah sebagai berikut:
  • 13. www.hansmichael.com - Bab X. Konsep Dasar Tree 96 ? Jika tree kosong, maka keluar. ? Proses node root. ? Traverse subtree kiri secara preorder. ? Traverse subtree kanan secara preorder. 2. Traversal inorder (symmetric order) Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, mencetak isi node yang dikunjungi, lalu melakukan kunjungan ke subtree kanan. Algoritma umum traversal inorder adalah sebagai berikut: ? Jika tree kosong, maka keluar. ? Traverse subtree kiri secara inorder. ? Proses node root. ? Traverse subtree kanan secara inorder. 3. Traversal postorder Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, lalu ke subtree kanan, dan selanjutnya mencetak isi node yang dikunjungi. Algoritma umum traversal inorder adalah sebagai berikut: ? Jika tree kosong, maka keluar. ? Traverse subtree kiri secara postorder. ? Traverse subtree kanan secara postorder. ? Proses node root. Semua algoritma traversal (preorder, inorder, postorder) yang diberikan di atas berupa algoritma rekursif, dan sebenarnya dapat dikerjakan secara iteratif dengan bantuan stack. Contoh: diberikan ekspresi matematika ((A * B) - (C ^ D)) + (E / F), apabila digambarkan dalam bentuk binary tree menjadi seperti gambar 10.9.
  • 14. www.hansmichael.com - Bab X. Konsep Dasar Tree 97 + - / * ^ E F A B C D Gambar 10.9 Representasi Ekspresi Matematika dalam Binary Tree Apabila binary tree di atas dikunjungi: ? secara preorder akan menghasilkan: +-*AB^CD/EF ? secara inorder akan menghasilkan: A*C-C^D+E/F ? secara postorder akan menghasilkan: AB+CD^-EF/+ 10.7 Latihan Soal 1. Tentukan level dan degree dari masing-masing node dalam tree yang ada pada gambar 10.10. A B K C F G D E H J I L M Gambar 10.10 Non Binary tree 2. Gambarkan bentuk tree pada soal no.1 dengan diagram Venn, nested parentheses, bar chart dan level-number notation. 3. Ubahlah ordered tree pada soal no. 1 menjadi sebuah binary tree.
  • 15. www.hansmichael.com - Bab X. Konsep Dasar Tree 98 4. Bagaimanakah representasi sekuensial dari binary tree jawaban soal no. 3? Sebelumnya tentukan dahulu tinggi maksimum dari binary tree yang dapat direpresentasikan dalam array tersebut. 5. Lakukanlah proses traversal preorder, inorder dan postorder pada binary tree jawaban soal no. 3. 6. Buatlah tiga buah procedure iteratif untuk melakukan traversal inorder, preorder dan postorder pada sebuah binary tree. 7. Buatlah sebuah procedure untuk melakukan traversal level order (berdasarkan level dari tree tersebut) pada sebuah binary tree dengan bantuan stack atau queue. 8. Buatlah sebuah function untuk mengembalikan jumlah node pada sebuah binary tree. 9. Buatlah sebuah function untuk mengembalikan ketinggian dari sebuah binary tree. 10. Buatlah tiga buah function untuk mengembalikan status (benar atau salah) apakah suatu binary tree merupakan balance tree, complete binary tree, full binary tree. 11. Gambarkan binary tree yang dimaksud: a) Traversal preorder pada sebuah binary tree menghasilkan urutan ｀A B C D E F G H I¨, sedangkan traversal inorder-nya menghasilkan urutan ｀C D E B F A I H G¨. b) Traversal postorder pada sebuah binary tree menghasilkan urutan ｀E D A C G F B H¨, sedangkan jumlah child untuk masing-masing node adalah sebagai berikut: A = 1, B = 2, C = 0, D = 1, E = 0, F = 1, G = 0 dan H = 2. 12. Buatlah sebuah program untuk mengkonversi antar ketiga notasi ekspresi matematika (prefix, infix dan suffix) dengan menggunakan binary tree.