Buku Ajar Struktur Data
Bagian
5 Tujuan Instruksional Khusus
Mahasiswa mampu menjelaskan struktur data nonlinier Tree. Mahasiswa mampu memahami operasi pada struktur data Tree
Pokok Bahasan
Struktur data Tree secara umum. Representasi struktur data tree dalam memori. Operasi pada struktur data Tree: Traversing, Search, Insert dan Delete
elama ini telah dipelajari struktur data berjenis linier: array, list, stack, dan queue. Bagian ini akan membahas struktur data nonlinier, yaitu tree. Struktur data ini digunakan untuk data yang mempunyai hubungan hirarki antar datanya, misalnya record, pohon keluarga dan daftar isi. Yang akan dibahas pertama kali adalah tree khusus, yaitu binary tree, yang dapat dikelola dalam komputer.
Binary tree. Sebuah tree biner T adalah himpunan elemen terbatas, yang disebut dengan simpul (node), sehingga 1. T disebut dalam kondisi kosong, yang disebut dengan tree null atau tree kosong, 2. T berisi simpul yang berbeda, yaitu simpul R, disebut dengan root dari tree, dan pasangan simpul berikutnya, yang membentuk subtree berbeda, yaitu T1 dan T2. Jika T berisi root R dan 2 subtree T1 dan T2, yang sering disebut dengan subtree kiri dan subtree kanan dari tree T. jika T1 tidak kosong, maka rootnya ini disebut dengan penerus kiri dari R. Hal sama juga berlaku untuk T 2, jika T2 tidak kosong maka rootnya disebut dengan penerus kanan dari R. Sebuah tree biner T biasanya dipresentasikan dalam bentuk diagram. Gambar 5.1 menunjukkan diagram tree biner T, yang mempunyai 11 simpul, yang ditunjukkan dengan huruf A sampai L, kecuali huruf I. Root dari T adalah A, yang terletak pada posisi paling atas dalam diagram terKadwi Suharsono
107
Buku Ajar Struktur Data sebut. Sebelah kiri-bawah dari diagram tersebut, mulai dari simpul B, adalah penerus kiri dari A, mulai dari simpul C, merupakan penerus kanan dari A. subtree kiri A berisi simpul-simpul B, D, E dan F, sedangkan subtree kanan A berisi simpul-simpul C, G, H, J, K, dan L. Setiap simpul N dalam tree biner mempunyai 0, 1 atau 2 penerus. Simpul A, B, C dan H mempunyai 2 penerus. Simpul E dan J hanya mempunyai 1 penerus dan Simpul D, F, G, K, dan L tidak mempunyai penerus. Simpul yang tidak mempunyai penerus disebut dengan simpul ujung (terminal node). Definisi tree biner T di atas karena T didefinisikan mempunyai subtree T1 dan subtree T2. Ini berarti bahwa setiap simpul N dari T mempunyai subtree kiri dan subtree kanan. Jika N adalah simpul ujung, maka kedua subtreenya adalah kosong. A
B
C
D
E
G
H
F
J
K
L
Gambar 5.1. Struktur Data Binary Tree Suatu tree biner T dan T’ disebut sama (similar) jika keduanya mempunyai struktur yang sama atau mempunyai bentuk yang sama. Suatu tree biner disebut salinan (copy) jika keduanya sama dan mempunyai isi pada simpul yang berhubungan, sama. Contoh 5.1. Gambar 5.2 berisi 4 gambar tree biner. Tiga tree biner (a), (c) dan (d) adalah sama. Secara khusus tree (a) dan (c) salinan, karena mempunyai simpul yang sama. Tree (b) tidak sama dan bukan salinan dari (d), karena penerus kiri dan penerus kanan dibedakan, meskipun hanya mempunyai 1 penerus. E
A
D (a)
E
F
B
C
A
B
H
G (b)
C
F
D (c)
G
H (d)
Gambar 5.2. Beberapa Struktur Data Tree Biner
Kadwi Suharsono
108
Buku Ajar Struktur Data Contoh 5.2. Ekspresi Aljabar. Ekspresi aljabar apa saja, terdiri dari operasi biner, seperti contoh berikut: 𝐸 = (𝑎 − 𝑏)/((𝑐 ∗ 𝑑) + 𝑒) E dapat direpresentasikan dalam tree biner T seperti yang tertera pada gambar 5.3. Setiap variabel atau konstanta E muncul sebagai simpul ‘internal’ dari T, subtree kiri dan kanan berhubungan dengan operan. Contohnya: 1. Dalam ekspresi E, operan dari + adalah c*d dan e. 2. Dalam tree T, subtree dari simpul + berhubungan dengan subekspresi c*d dan e. Jadi jelas bahwa setiap ekspresi aljabar berhubungan dengan tree yang unik, dan juga sebaliknya. /
-
a
+
b
*
c
e
d
Gambar 5.3. 𝐸 = (𝑎 − 𝑏)/((𝑐 ∗ 𝑑) + 𝑒) Istilah. Istilah yang berhubungan dengan relasi keluarga sering digunakan untuk menjelaskan hubungan antar simpul pada tree T. Misalkan N adalah sebuah simpul dari tree T, mempunyai penerus kiri S1, dan penerus kanan S2. Maka N disebut orangtua dari S1 dan S2. S1 disebut anak kiri dari N, dan S2 adalah anak kanan dari N. S1 dan S2 disebut bersaudara. Setiap simpul N dalam tree biner T, kecuali root, mempunyai orangtua yang unik, disebut sebagai pendahulu dari N. Istilah keturunan dan buyut mempunyai arti yang sama. Jadi, jika sebuah simpul L disebut sebagai keturunan dari simpul N (dan N disebut sebagai nenek moyang dari L) jika terdapat anak berikutnya dari N ke L. Secara khusus, L disebut sebagai keturunan kiri atau kanan dari N oleh karena itu L adalah subtree kiri atau kanan dari N. Istilah dari teori graph dan hortikultur juga digunakan dalam tree biner. Garis lurus dari suatu simpul N menuju penerusnya disebut sisi, dan serangkaian sisi yang bersambungan disebut jalur. Sebuah simpul ujung disebut daun, dan jalur akhir dari daun disebut cabang. Setiap simpul dalam tree biner T diberi nomor tingkat. Root R dari tree T diberi level 0, dan setiap simpul lainnya diberi level 1 tingkat di atasnya dari level orangtuanya. Oleh karena itu simpul yang mempunyai level sama disebut generasi yang sama.
Kadwi Suharsono
109
Buku Ajar Struktur Data Kedalaman (ketinggian) suatu tree T adalah angka maksimum dari simpul dalam cabang T. Ini akan menghasilkan angka 1 lebih banyak dari pada level dari T. Sehingga tree T pada gambar 5.1 mempunyai kedalaman 5. Tree Biner lengkap Misalkan suatu tree biner T, masing-masing simpul T hampir mempunyai 2 anak. Oleh karena itu dapat dilihat bahwa tingkat r dari T dapat mempunyai hampir 2r simpul. Suatu tree T disebut lengkap jika pada semua tingkat, kecuali simpul terakhir, mempunyai jumlah simpul yang mendekati jumlah maksimal, dan jika semua simpul pada tingkat terakhir muncul pada sisi sebelah kiri. Jadi terdapat Tree lengkap Tn dengan n simpul. Gambar 5.4 adalah tree lengkap T26 dengan 26 simpul. 1
2
3
4
9
8 16
5
17
18
6
10 19
20
11 21
22
7
12 23
24
13 25
14
15
26
Gambar 5.4. Tree Lengkap T26 Simpul-simpul pada tree biner lengkap T26 di atas diberi label dengan angka 1, 2, 3,… , 26, dari kiri ke kanan, dari generasi ke generasi. Dengan pelabelan seperti ini dapat dengan cepat diketahui anak atau orangtua dari suatu simpul K dari tree biner lengkap Tn. Anak kiri dan kanan dari simpul K adalah 2*K dan 2*K+1, dan orangtua K adalah K/2. Sebagai contoh, anak simpul ke 9 adalah simpul 18 dan 19, dan orangtua simpul 9 adalah ⌊9/2⌋ = 4. Kedalaman dn dari tree lengkap Tn dengan n simpul adalah 𝐷𝑛 = ⌊log 2 𝑛 + 1⌋ Angka kedalaman ini relatif kecil. Sebagai contoh, untuk tree lengkap Tn dengan n = 1.000.000, kedalamannya adalah 21. Tree Biner Ekstended: tree-2 Sebuah tree biner T disebut sebagai tree-2 atau tree biner ekstended jika setiap simpul N nya mempunyai 0 atau 2 anak. Dalam hal ini simpul yang mempunyai 2 anak disebut simpul internal, dan simpul yang tidak mempunyai anak disebut simpul eksternal. Sering kali simpul dibedakan dalam diagram dengan menggunakan lingkaran sebagai simpul internal dan persegi sebagai simpul eksternal.
Kadwi Suharsono
110
Buku Ajar Struktur Data Istilah tree biner ekstended berasal dari operasi berikut. Misalkan suatu tree biner T seperti yang tertera pada gambar 5.5 (a). Kemudian T dikonversikan menjadi tree 2 dengan mengganti setiap simpul kosong dengan simpul baru seperi pada gambar 5.5 (b). Perhatikan bahwa tree baru adalah sebuah tree 2. Oleh karena itu simpul asli dari tree T sekarang menjadi simpul internal pada tree ekstended, dan simpul baru adalah simpul eksternal pada tree ekstended. Contoh penting dari tree 2 adalah tree T yang berhubungan dengan ekspresi aljabar E yang hanya menggunakan operasi biner. Seperti contoh pada gambar 5.3 variabel E akan muncul sebagai simpul eksternal dan operasi E akan muncul sebagai simpul internal.
(a) binary tree T
(b) Extended 2-tree
Gambar 5.5 Konversi tree biner T menjadi tree-2.
Representasi tree biner di memori Jika T adalah tree biner, bagian ini akan membahas cara representasi T di memori. Cara pertama menggunakan representasi berkait T dan ini mirip dengan cara representasi list berkait di memori. Cara kedua dengan menggunakan array tunggal, yang disebut representasi urut dari T. Kebutuhan utama dari representasi manapun harus mempunyai akses langsung ke root R dari T, yang memberikan simpul N manapun dari T yang mempunyai akses langsung ke anak N. Representasi berkait dari tree biner Perhatikan tree biner T, walaupun tidak dinyatakan secara eksplisit T akan disimpan di memori menggunakan representai berkait dengan 3 array parallel, INFO, KIRI, dan KANAN, dan sebuah variabel pointer ROOT. Pada awalnya setiap simpul N dari T akan berhubungan dengan lokasi dari K sebagai berikut : 1. INFO[K] berisi data pada simpul N. 2. KIRI[K] berisi lokasi anak kiri dari simpul N. 3. KANAN[K] berisi lokasi anak kanan simpul N.
Kadwi Suharsono
111
Buku Ajar Struktur Data ROOT akan berisi lokasi dari R. Jika subtree kosong maka pointer yang berhubungan akan bernilai null. Jika tree T kosong maka ROOT akan berisi nilai null. Catatan: 1. Contoh yang ada sering menggunakan item tunggal informasi untuk setiap simpul N dari tree biner T. Dalam prakteknya, seluruh record akan disimpan dalam simpul N. Dengan kata lain, INFO merupakan array linier dari record atau sekumpulan array parallel. 2. Karena simpul mungkin disisipkan ke dalam tree biner atau dihapus dari tree biner, juga akan diasumsikan terdapat lokasi kosong dalam array INFO, KIRI, dan KANAN yang membentuk list berkait dengan pointer AVAIL, seperti yang telah dibahas dalam bagian 3. Array KIRI akan digunakan untuk menyimpan pointer list AVAIL ini. 3. Alamat yang tidak valid akan digunakan untuk menunjukkan pointer null. Sering digunakan angka 0 atau angka negatif untuk nilai null tersebut. Contoh 5.3 Perhatikan Tree biner T pada gambar 5.1. Diagram skematis dari representasi berkait tertera pada gambar 5.6. Masing-masing simpul mempunyai 3 field, dan subtree yang kosong diberi simbol x, sebagai null. Gambar 5.7 menunjukkan bagaimana representasi berkait tersimpan di memori. Pilihan array dengan 20 elemen adalah contoh saja. Pointer AVAIL tetap diperlukan untuk mengelola memori yang tidak terpakai. Root x A x x C x
x B x x D x
x E x
x G x
x H x x J x
x F x
x K x
x L x
Gambar 5.6. Tree biner.
Kadwi Suharsono
112
Buku Ajar Struktur Data
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Root 5 Avail 8
INFO K C G A H L
B F E
J D
KIRI KANAN 0 0 3 6 0 0 14 10 2 17 1 0 0 9 4 0 18 13 19 0 0 12 0 15 16 11 7 0 0 0 20 0
Gambar 5.7. Contoh 5.4. Suatu file pegawai dari sebuah perusahaan kecil berisi data 9 orang, dengan struktur seperti berikut: Nama, NIP, Jenis Kelamin, dan Gaji bulanan Gambar 5.8 menunjukkan bagaimana file tersebut tersimpan di memori dalam sebuah tree biner. Bandingkan struktur data tersebut dengan gambar 3.11, yaitu data yang sama dengan pengorganisasian dengan list tunggal. Nama ROOT 14
AVAIL 8
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
NIP
Kelamin
Gaji
Durno Kresno Gatotkoco
192-38-7282 165-64-3351 175-56-2251
Pria Pria Pria
22800 19000 27200
Bismo Limbuk
178-52-1065 181-58-9939
Pria Wanita
14700 16400
Cakil Rahwono
177-44-4557 135-46-6262
Pria Pria
19000 15500
Emban
168-56-8113
Wanita
34200
Hanoman
208-56-1654
Pria
22800
KIRI 0 0 0 2 1 0 3 11 6 0 13 0 5 9
KANAN 12 0 0 0 10 4 0 0 7
Gambar 5.8. Tree biner data pegawai
Kadwi Suharsono
113
Buku Ajar Struktur Data Jika akan digambar diagram tree yang berhubungan dengan gambar 5.8, untuk memudahkan notasinya, label simpul dalam diagram hanya berupa filed Nama. Susunan tree tersebut adalah sebagai berikut: a. Isi Root = 14, menunjukkan Hanoman merupakan root dari tree b. Kiri[14] = 9, menunjukkan Cakil sebagai anak kiri dari Hanoman, dan Kanan[14] = 7, menunjukkan Limbuk sebagai anak kanan Hanoman Langkah b diulang untuk memasukkan simpul baru dalam tree, seperti yang terlihat pada gambar 5.9. Hanoman
Cakil
Limbuk
Gatotkoco
Bismo
Kresno
Rahwono
Durno
Emban
Gambar 5.9 Representasi Sekuensial dari tree biner. Jika T adalah tree biner komplet atau hamper komplit, maka terdapat cara efisien untuk mengelola T di memori yang disebut dengan representasi sekuensial. Representasi ini hanya menggunakan sebuah linier array tunggal sebagai berikut: a. Root R disimpan dalam Tree[1] b. Jika sebuah simpul N menempati Tree[K], maka anak kirinya disimpan dalam Tree[2*K] dan anak kanannya akan disimpan dalam Tree[K*2+1] Null akan digunakan untuk menunjukkan subtree yang kosong. Secara khusus, jika Tree[1] = Null menunjukkan bahwa Tree tersebut kosong. Representasi sekuensial dari tree biner yang terdapat pada gambar 5.10. (a) tersebut terdapat pada gambar 5.10. (b). Perhatikan, tetap diperlukan 14 lokasi pada array Tree walaupun T hanya mempunyai 9 simpul. Pada kenyataannya, jika disertakan nilai null untuk simpul setelah simpul ujung, maka diperlukan simpul Tree[29] yang merupakan anak kanan Tree[14]. Secara umum dapat dikatakan bahwa representasi sekuensial dari Tree dengan kedalaman d akan memerlukan sebuah array kira-kira 2𝑑+1 elemen. Oleh karena itu representasi sekuensial ini biasanya kurang efisien, kecuali jika diterapkan pada tree yang komplit. Contohnya, Tree T pada gambar 5.1 mempunyai 11 elemen dan mempunyai kedalaman 5, akan memerlukan kira-kira 26 = 64.
Kadwi Suharsono
114
Buku Ajar Struktur Data
45
22
11
77
30
90
15 25
88
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 .. .. .. 29
(a)
Tree 45 22 77 11 30 90 15 25
88
(b)
Gambar 5.10
Traversing pada Tree Biner Terdapat 3 cara baku untuk operasi traversing pada struktur data Tree biner T dengan root R. Ketiga algoritma ini disebut preorder, inorder dan postorder, seperti berikut ini: Preorder: 1. Proses root R 2. Kunjungi subtree kiri dari R secara preorder 3. Kunjungi subtree kanan dari R secara preorder Inorder:
1. Kunjungi subtree kiri dari R secara inorder 2. Proses root R 3. Kunjungi subtree kanan R secara inorder
Postorder:
1. Kunjungi subtree kiri dari R secara postorder 2. Kunjungi subtree kanan dari R secara postorder 3. Proses root R
Perhatikan bahwa masing-masing algoritma mempunyai 3 langkah yang sama, yaitu subtree kiri dikunjungi terlebih dahulu sebelum mengunjungi subtree kanan. Perbedaan algoritmanya adalah waktu yang diperlukan untuk memproses root R. secara khusus, algoritma ‘pre’ adalah root R diproses terlebih dulu sebelum memroses subtreenya. Pada algoritma ‘in’ Kadwi Suharsono
115
Buku Ajar Struktur Data root R diproses diantara kedua subtree dan pada algoritma ‘post’, root R diproses setelah memroses kedua subtree. Ketiga algoritma tersebut sering disebut kunjungan simpul-kiri-kanan (sikika), kiri-simpul-kanan (kisika) dan kiri-kanan-simpul (kikasi). Ketiga algoritma ini didefinisikan secara rekursif karena algoritma melakukan kunjungan subtree sesuai dengan urutannya. Oleh karena itu diperlukan sebuah stack untuk pengimplementasiannya ke dalam komputer. Contoh 5.5 Perhatikan Tree biner T dalam gambar 5.11, A merupakan root, dan subtree kiri adalah LT, yang berisi simpul B, D dan E, dan subtree kanan RT, yang berisi simpul C dan F. A
RT
LT B
D
C
E
F
Gambar 5.11. Tree Biner (a) Kunjungan preorder tree T adalah memroses A, mengunjungi LT dan mengunjungi RT. Kunjungan preorder LT memroses root B, kemudian simpul D dan E, kunjungan preorder RT memroses root C, kemudian simpul F. Hasil kunjungan preorder Tree T adalah A-B-D-E-C-F (b) Kunjungan inorder tree T adalah mengunjungi LT, memroses A dan mengunjungi Rt. Kunjungan inorder LT akan memroses simbul D, B dan E, dan kunjungan inorder RT akan memroses simpul C dan F. Hasil kunjungan inorder Tree T adalah D-B-E-A-C-F (c) Kunjungan postorder tree T adalah mengunjungi LT, mengunjungi RT dan memroses A. Kunjungan postorder LT akan memroses simpul D, E dan B, sedangkan kunjungan postorder RT akan memroses simpul F dan C. Hasil kunjungan postorder tree T adalah D-E-B-F-C-A. Contoh 5.6. Perhatikan tree T pada gambar 5.12 berikut. Kunjungan preorder pada T menghasilkan A-B-D-E-F-C-G-H-J-L-K. Urutan ini sesuai dengan jalur penelusuran ke kiri yang ditunjukkan pada gambar 5.12 tersebut.
Kadwi Suharsono
116
