Pohon Biner

STRUKTUR DATA POHON BINER Gilang Maulana [email protected] gilang.mendozha@gmail./com Manajamen Informatika Akademik Bina Sarana Informatika Salemba, Jakarta INONESIA 2008 Pendahuluan Pohon atau (tree) adalah salah satu bentuk graph terhubung yang tidak mengandung sirkuit. Karena merupakan graoh terhubung, maka pada pohon (tree) selalau terdapat path atau jalur yan menghubungkan setiap simpul dalam dua pohon. Pohon (tree) dpat juga didefinisikan sebagai kumpulan element yang salah satu elemennya disebut dengan akar (root) dan sisa elemen lain (simpul) yang terpecah menjadi sebuah hmpuna yang saling tidak berhubungan yang disebut dengan subpohon (subtree) atau cabang. 1. Sifat Utama Pohon Berakar Sifat utama pohon berakar :  Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas adalah (n-1). Pada contoh : banyak simpul adalah 8 maka banyaknya ruas adalah 7.  Mempunyai simpul khusus yang disebut Root (Akar), jika simpul tersebut memiliki derajat keluar ≥ 0 dan derajat masuk = 0. Simpul P merupakan root.  Mempunyai simpul yang disebut Leaf (Daun), jika simpul tersebut memiliki derajat keluar = 0 dan derajat masuk = 1. Simpul R, S, V, W merupakan daun pada pohon T.  Setiap simpul mempunyai tingkatan (level), dimulai dari root dengan level 0 sampai dengan level n pada daun yang paling bawah.  Pada contoh :  P mempunyai level 0  Q, T mempunyai level 1  R, S, U mempunyai level 2  V, W mempunyai level 3

 Simpul yang mempunyai level yang sama disebut Bersaudara (Brother /Stribling)  Pohon mempunyai ketinggian (kedalaman / height) yaitu level tertinggi +1. Ketinggian pohon T adalah 3+1 = 3  Pohon mempunyai berat (bobot / weight) yaitu banyaknya daun pada pohon. Berat pohon T adalah 4 Ketinggian Minimum Dan Maksimum Pohon Binar Jika banyaknya simpul = N, maka : 1. Ketinggian Minimum adalah : Hmin = INT(2log N) + 1 2. Ketinggian Maksimum adalah : N Contoh : untuk N = 8 Ketinggian Minimum adalah : Hmin = INT(2log N) + 1 = INT(2log 8) + 1 = INT(2log 23) + 1 = INT(3) + 1 =3+1 =4 Ketinggian Maksimum adalah : 8 Penyajian Pohon Binar Dalam Memori Penyajian pohon binar dalam memori dengan dua cara, yaitu : 1. Penyajian Kait (link) 2. Penyajian Sequential.  Penyajian Kait Kalau tidak dinyatakan lain, suatu pohon binar T akan disimpan dalam memori secara penyajian kait. Penyajian ini menggunakan tiga array sejajar INFO, LEFT dan RIGHT, serta variabel penuding ROOT. Masing-masing simpul N dari pohon T berkorespondensi dengan suatu lokasi K, sedemikan sehingga : (1) INFO(K) berisi data pada simpul N. (2) LEFT(K) berisi lokasi dari anak kiri simpul N. (3) RIGHT(K) berisi lokasi dari anak kanan simpul N.

Contoh : Pohon Binar A B

C

D

E

G

H

F

J

K

L

Skema Penyajian Kait dari pohon binar T •

Root

• • x

D

•

•

B

•

•

x x

A

F

E

x

x

G

C

x

L

x

•

x •

x

•

J

x

H

• x

K

x

Root 2

Avail 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

INFO L A G C B F J E

D H K

LEFT 0 7 8 0 4 13 16 6 0 3 1 9 15 19 18 0 11 14 0 0

RIGHT 0 5 0 17 12 0 0 0

0 20 0

 Penyajian Sequential Penyajian pada pohon binar T ini hanya menggunakan sebuah array linear tunggal TREE sebagai berikut : 1. Akar R dari pohon T tersimpan sebagai TREE[1] 2. Jika simpul N menduduki TREE[K] maka anak kirinya tersimpan dalam TREE[2*K] dan anak kanannya dalam TREE[2*K+1] Contoh : 45 22 11

77 30

90

15

25

88

TREE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 29

45 22 77 11 30 90 15 25

88

Dapat dilihat bahwa penyajian membutuhkan 14 lokasi dalam array TREE, meskipun T hanya mempunyai 9 simpul. Kenyataannya, bila kita memasukkan elemen nol sebagai suksesor dari simpul terminal, dibutuhkan TREE[29] untuk suksesor kanan dari TREE[14]. A. KUNJUNGAN PADA POHON BINER Ada tida macam kunjungan pada pohon biner, yaitu kunjungan PreOrder, InOrder, dan PostOrder. Selain itu ada kunjungan LevelOrder, yaitu yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented (RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.

1. Kunjungan PreOrder Kunjungan PreOrder LRO atau sering disebut dengan depth first order menggunakan urutan sebagai berikut : Cetak isi simpul yang dikunjungi. Kunjungi cabang kiri. Kunjungi cabang kanan. Prosedur kunjungan PreOrder dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PreOrder LRO dengan rekursif disajikan berikut ini : Procedure PreOrder (Root:Pohon); Begin If Root <> nil then Begin Write (Root^.Info); PreOrder (Root^.kiri); PreOrder (Root^.kanan); End;

End; 2. Kunjungan InOrder Kunjungan InOrder LRO atau sering disebut dengan symmetric order menggunakan urutan sebagai berikut : Kunjungi cabang kiri. Cetak isi simpul yang dikunjungi. Kunjungi cabang kanan. Seperti pada kunjungan PreOrder, prosedur kunjungan InOrder dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara InOrder LRO dengan rekursif disajikan berikut ini : Procedure InOrder (Root:Pohon); Begin If Root <> nil then Begin InOrder (Root^.kiri); Write (Root^.Info); InOrder (Root^.kanan); End; End; 3. Kunjungan PostOrder Kunjungan PostOrder LRO menggunakan urutan sebagai berikut : Kunjungi cabang kiri. Kunjungi cabang kanan. Cetak isi simpul yang dikunjungi. Seperti halnya PreOrde dan InOrder, prosedur kunjungan PostOrder juga dapat dilakukan dengan cara rekursif atau non rekursif. Prosedur kunjungan secara PostOrder LRO dengan rekursif disajikan berikut ini : Procedure PostOrder (Root:Pohon); Begin If Root <> nil then Begin PostOrder (Root^.kiri); PostOrder (Root^.kanan); Write (Root^.Info); End; End; B. SORTING

Sorting adalah sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam himpunan yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang berbeda: 1. Pengurutan: merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur, 2. Kategorisasi: pengelompokan dan pemberian label kepada benda dengan sifat yang serupa. Sorting (pengurutan) adalah operasi yang sangat banyak dilakukan dalam ’Bussines Data Procesing’. Dalam hal ini pengurutan yang dilakukan adalah secara Ascepding (menaik dari kecil ke besar). Macam macam sorting (pengurutan) sebagai berikut : SELECTION SORT BUBLE SORT MERGE SORT QUICK SORT INSERTION SORT HEAP SORT Mensortir informasi atau data Salah satu cara sorting yang penting adalah mengatur benda informasi dalam urutan alfabetik sesuai dengan hubungan penyusunan yang telah didefinisikan sebelumnya, misal ketika seseorang mensortir buku-buku di perpustakaan berdasarkan judul, subyek atau penulis (Biasanya diurutkan dalam urutan membesar). Urutan yang dihasilkan dapat membesar atau mengecil, karena biasanya seluruh sorting adalah sorting angka. Sorting dalam Ilmu Komputer adalah salah satu subjek riset yang paling luas karena kebutuhan mempercepat operasi dalam ribuan atau jutaan data selama operasi pencarian. Tujuan utama mensortir informasi adalah untuk mengoptimalkan tugas tertentu. Pada umumnya, ada dua cara pengelompokan informasi: berdasarkan kategori, misal sebuah katalog belanja di mana barang disusun bersama di bawah judul seperti 'rumah', 'olah raga', 'pakaian wanita', dll. dan berdasarkan intensitas seperti harga, misal dari yang termurah sampai yang termahal.

C. GRAPH Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data.

1. Himpuna Graph dan Jenis Graph a.

Himpuna Graph

Suatu Graph terdiri dari himpunan verteks (node) dan himpunan sisi (edge, arc). Verteks menyatakan entitas-entitas data dan sisi menyatakan keterhubungan antara verteks. Notasi matematis graph G adalah : G = (V, E) Sebuah sisi antara verteks x dan y ditulis {x, y}. Subgraph : graph yang merupakan suatu subset (bagian) graph yang connected Graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian dari V dan E1 himpunan bagian dari E. b.

Jenis Graph

1.

Directed Graph (Digraph) Jika sisi-sisi graph hanya berlaku satu arah. Misalnya : {x,y} yaitu arah x ke y, bukan dari y ke x; x disebut origin dan y disebut terminus. Secara notasi sisi digraph ditulis sebagai vektor (x, y). Contoh Digraph G = {V, E} : V = {A, B, C, D, E, F, G, H, I,J, K, L, M} E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G), (C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K), (J,M), (L,K), (L,M)}. 2.

Graph Tak Berarah (undirected graph atau undigraph) setiap sisi {x, y}berlaku pada kedua arah: baik x ke y maupun y ke x. Secara grafis sisi pada undigraph tidak memiliki mata panah dan secara notasional menggunakan kurung kurawal. Contoh Undigraph G = {V, E} V = {A, B, C, D, E, F, G, H, I,J, K, L, M} E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E}, {D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}. Banyak entitas-entitas data dalam masalah-masalah nyata secara alamiah memiliki keterhubungan langsung (adjacency) secara tak terbatas demikian. Contoh: informasi topologi dan jarak antar kota-kota di pulau Jawa. Dalam masalah ini kota x bisa berhubungan langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa

keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya yang memperantarainya. Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.

Masalah-masalah Graph Masalah path minimum (Shortest mencari route dengan jarak terpendek dalam suatu path problem) jaringan transportasi. Masalah aliran maksimum menghitung volume aliran BBM dari suatu reservoir (maximum flow problem) ke suatu titik tujuan melalui jaringan pipa. Masalah pencariah dalam graph mencari langkah-langkah terbaik dalam program (graph searching problem) permainan catur komputer. menentukan urutan pengambilan mata-mata kuliah Masalah pengurutan topologis yang saling berkaitan dalam hubungan prasyarat (topological ordering problem) (prerequisite). Masalah jaringan tugas (Task membuat penjadwalan pengerjaan suatu proyek yang Network Problem) memungkinkan waktu penyelesaian tersingkat. Masalah pencarian pohon rentang mencari rentangan kabel listrik yang totalnya adalah minimum (Minimum Spanning minimal untuk menghubungkan sejumlah kota. Tree Problem) tukang pos mencari lintasan terpendek melalui semua Travelling Salesperson Problem alamat penerima pos tanpa harus mendatangi suatu tempat lebih dari satu kali. dalam menggambar peta, memberikan warna yang Four-color problem berbeda pada setiap propinsi yang saling bersebelahan.

D. MATRIKS Pandang bahwa G graf dengan N simpul dan M ruas. Untuk mempermudah komputasi, graf dapat disajikan dalam bentuk matriks, disebut Matriks Ruas, yang berukuran (2 x M) atau (M x 2) yang menyatakan ruas dari graf. Matriks adjacency dari graf G tanpa ruas sejajar adalah matriks A berukuran (N x N), yang bersifat : 1, bila ada ruas (vi, vj) aij = 0, dalam hal lain Matriks adjacency merupakan matriks simetri. Untuk graf dengan ruas sejajar, matriks adjacency didefinisikan sebagai berikut :

p, bila ada p buah ruas menghubungkan (vi, vj) (p > 0) aij = 0, dalam hal lain Matriks Incidence dari graf G, tanpa self-loop didefinisikan sebagai matriks M berukuran (N x M) 1, bila ruas ej berujung di simpul vi, mij = 0, dalam hal lain Contoh : e5 v1 • e1

v4 • e8

e4 e2

• v2

e6

e3

v3

v5 •

e7 •

Matriks Ruas 1 1 1 1 2 3 3 4 2 3 4 5 3 4 5 5

atau

1 1 1 1 2 3 3 4

2 3 4 5 3 4 5 5

Matriks Adjacency : N x N

v1 v2 v3 v4 v5

v1

v2

v3

v4

v5

0 1 1 1 1

1 0 1 0 0

1 1 0 1 1

1 0 1 0 1

1 0 1 1 0

Matriks Incidence : N x M

v1 v2 v3 v4 v5

e1

e2

e3

e4

e5

e6

e7

e8

1 1 0 0 0

1 0 1 0 0

0 1 1 0 0

1 0 0 1 0

1 0 0 0 1

0 0 1 1 0

0 0 1 0 1

0 0 0 1 1

GRAF BERARAH (DIGRAF) Suatu graf berarah (digraf) D terdiri atas 2 himpunan : 1. Himpunan V, anggotanya disebut simpul 2. Himpunan A, merupakan himpunan pasangan terurut, yang disebut ruas berarah atau arkus. Notasi : D(V, A) Simpul, anggota v, digambarkan sebagai titik (atau lingkaran kecil). Sedangkan arkus a=(u,v), digambarkan sebagai garis dilengkapi dengan tanda panah mengarah dari simpul u ke simpul v. Simpul u disebut titik pangkal, dan simpul v disebut titik terminal dari arkus tersebut. Contoh : Graf berarah D (V, A) dengan : 1. V mengandung 4 smpul, yaitu : 1, 2, 3 dan 4 2. A mengandung 7 arkus, yaitu : (1,4), (2,1), (2,1), (2,2), (2,3), (2,4), (4,3).

1

4

2

•

•

•

• 3

Arkus (2, 2) : gelung / self loop Arkus (2,1) : arkus sejajar / arkus berganda