MAKALAH MATEMATIKA DISKRIT " POHON "

MAKALAH

MATEMATIKA DISKRIT

BAB 9 POHON

Disusun Oleh :

Nursidrati                   (15.1.124.024)

JURUSAN PENDIDIKAN MATEMATIKA

FAKULTAS ILMU TARBIYAH dan KEGURUAN ( FITK )

INSTITUT AGAMA ISLAM NEGERI ( IAIN ) MATARAM

MATARAM

2013

BAB I

PENDAHULUAN

A.   LatarBelakang

Pohondidefinisikansebagaisuatugraftakberarahterhubungkan (connected undirected graph) yang tidakmengandungrangkaiansederhana.Pohonadalahbentukkhususdarisuatugraf yang banyakditerapkanuntukberbagaikeperluan.Misalnyastrukturorganisasisuatuperusahaan, silsilahsuatukeluarga, skemasistemgugursuatupertandingan, danikatankimiasuatumolekuladalahjenisgraf yang tergolongsebagaipohon.Padapohon, simpul-simpul yang berderajatsatudinamakandaun (leave), sedangkansimpul yang derajatnyalebihbesardaripadasatudinamakansimpulcabang (branch node) atausimpul internal (internal node) dankumpulanpohon-pohon yang terpisahkansatusama lain disebuthutan (forest).

B.   Rumsanmasalah

1.       Apakah Definisi dari Pohon itu ?

2.       Sebutkan sifat-sifat yang terdapat dalam Pohon ?

3.       Apakah yang di maksud dengan Pohon merentang ?

4.          Apakah yang di maksud dengan Pohon berakar ?

5.       Apakah yang di maksud dengan pohon berakar terurut ?

6.       Apakah yang di maksud dengan jumlah daun m-ary penuh ?

7.       Apakah yang di maksud dengan Pohon Biner ?

8.       Apakah yang diaksud dengan Pohon Ekspresi ?

9.       Apakah yang dimaksud dengan Pohon Keputusan ?

10.   Apakah  yang dimaksud dengan Kode awalan itu ?

11.   Apakah yang dimaksud dengan Pohon Pencarian ?

C.    Tujuan

1.       Untuk mengetahui  Definisi dari Pohon itu .

2.       Untuk mengetahui sifat-sifat yang terdapat dalam Pohon .

3.       Untuk mengetahui apa yang di maksud dengan Pohon merentang .

4.       Untuk mengetahui apa yang di maksud dengan Pohon berakar .

5.       Untuk mengetahui apa yang di maksud dengan pohon berakar terurut .

6.       Untuk mengetahui apa yang di maksud dengan jumlah daun m-ary penuh .

7.       Untuk mengetahui apa yang di maksud dengan Pohon Biner .

8.       Untuk mengetahui apa yang diaksud dengan Pohon Ekspresi .

9.       Untuk mengetahui apa yang dimaksud dengan Pohon Keputusan.

10.   Untuk mengetahui apa yang dimaksud dengan Kode awalan itu .

11.   Untuk mengetahui apa yang dimaksud dengan Pohon Pencarian .

BAB II

PEMBAHASAN

A.   Definisi pohon

Pohon adalah graf yang khusus.Definisi pohon adalah sebagai berikut:

Defnisi 9.1.Pohon adalah geraf tak Berarah  terhubung yang tidak mengandung sirkuit.

 Menurut definisi 9.1 di atas,ada dua sifat penting pada pohon:terhubung dan tidak mengandung sirkuit.Pada Gambar 9.1,hanya G1 dan G2 yang pohon,sedangkan G3 dan G4 bukan pohon.G3 bukan pohon karena ia mengandung sirkuit a,d,f,a,sedangkan  G4 bukan pohon karena ia tidak terhubung (anda jangan tertipu dengan persilangan dua buah sisi-dalam hal ini sisi (a,f)dan sisi (b,e)-karena titik silangnya bukan bukan menyatakan simpul).

G1                                                      G2                                      G3                                                                              G4

Gambar 9.1 G1 dan G2 adalah pohon ,sedangkan G3 dan G4 bukan pohon

Berikut contoh pohon lainnya,di ambil dari [LIU85],misalkan himpunan V={a,A,b,B,c,C,d,D} adalah  empat pasangan suami –istri tukang gossip,dengan a,b,c,dan d para suami,dan A,B,C,D para istri,Misalkan a menceritakan gosip lewat telpon kepada istrinya A,yang kemudian A yang menelpon para istri  lainnya untuk menyebarkan gosip itu ,dan setiap istri itu menelpon dan menceritakan gosip kepada suami masing-masing.pohon pada gambar 9.2 menunjukan bagaimana gosip tersebut tersebar ,dengan simpul menyatakan istri/suami dan sisi menyatakan panggilan telpon.

Gambar 9.2 pohon penyebaran gosip

Karena definisi pohon di acu dari teori graf,maka sebuah pohon dapat mempunyai hanya sebuah simpul tanpa sebuah sisipun.Dengan kata lain,jika G=(V,E) adalah pohon,maka v tidak boleh berupa himpunan kosong,namun E boleh kosong,pada sebagian literature,pohon yang di maksudkan oleh definisi 9.1 sering di sebut juga pohon Bebas (free tree) untuk membedakannya dengan  pohon berakar (rooted tree).Pohon berakar akan kita bahas lebih lanjut dalam upaBab 9.4 untuk selanjutnya ,jika di sebut pohon ,maka yang di maksudkan adalah pohon bebas.

Beberapa pohon dapat membentuk hutan.Hutan (forest)adalah kumpulan pohon yang saling lepas.Kita dapat juga menyatakan bahwa hutan adalah graf tak terhubung yang tidak mengandung sirkuit,yang dalam hal ini setiap komponen di dalam graf terhubung tersebut adalah pohon.Gambar 9.3 berikut adalah hutan yang terdiri atas 3 buah pohon.

Gambar 9.3 Hutan yang terdiri dari tiga buah pohon.

B.   Sifat-Sifat Pohon

Sifat-sifat (properties) pohon dinyatakan dengan teorema 9.1 di bawah ini.

Teorema 9.1.Misalkan G=(V,E) adalah graf tak berarah sederhana dan jumlah simpulnya n,maka,semua pernyataan di bawah ini adalah ekivalen:

1.       G adalah pohon.

2.       Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal.

3.       G terhubung dan memiliki m=n-1 buah sisi.

4.       G tidak mengandung sirkuit dan memiliki m=n-1 buah sisi.

5.       G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya sat sirkuit.

6.       G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila di hapus menyebabkan graf terpecah menjadi dua komponen).

Semua butir pernyataan di atas juga dapat di anggap sebagai definisi lain dari pohon.Kita juga dapat membuktikan bahwa hutan f dengan k komponen membpunyai m=n-k buah sisi.

Contoh:

Sebuah phon mempunyai 2n buah simpul berderajat 1,3n buah simpul berderajat2,dan n buah simpul berderajat 3.Tentukan banyaknya simpul dan sisi di dalam pohon itu.

Penyelesaiyan:

Menurut Lemma jabat tangan ,jumlah derajat semua simpul di dalam garaf adalah 2 kali jumlah sisi di dalam graf tersbut .jadi,

(2n x 1) + (3n x 2) + (n x 3)=2 IEI

Menurut teorema 9.1 jumlah sisi pada sebuah pohon adalah jumlah simpul minus satu ,jadi

IEI= (2n + 3n + n)-1=6n-1

Dengan menyulihkan persamaan terakhir ke persamaan pertama,

11n= 2(6n-1) = 12n-2         n=2

Jadi,jumlah simpul pada pohon = 6n= 6 x 2 =12 dan jumlah sisi = 6n – 1=11.

Pewarnaan pohon

Pewarnaan pada pohon T di lakukan dengan cara berikut:petakan warna pertama pada sembarang sebuah simpul.Kemudian ,petakan warna kedua pada simpul –simpu yang bertetangga dengan simpul pertama tadi.Selanjutnya,petakan warna pertama ke semua simpul yang bertetangga dengan simpul-simpul yang telah di beri warna kedua.Ulangi proses ini sampai semua simpul telah di warnai.sebagai contoh,tinjau G₁  pada gambar 9.1.Simpul-simpul pada G­₁ akan di warnai dengan warna kuning dan biru.simpul a di pilih pertama kali untuk di beri warna kuning.Kemudian simpul-simpul tetangga a ,yaitu b dan d, di beri warna biru.Selanjutnya simpul-simpul yang bertetangga dengan d, yaitu c,e dan f di beri warna kuning.

C.    Pohon Merentang

      Misalkan G= (V,E) adalah graf tak-berarah terhubung yang bukan pohon ,yang berarti di G terdapat beberapa sirkuit.G dapat di ubah menjadi phon T = (V₁,E₁) dengan cara memutuskan sirkuit-sirkui yang ada.Caranya,mula-mula di pilih sebuah sirkuitb,lalu hapus satu buah sisi dari sirkuit ini.G aakn tetap terhubung dan jumlah sirkuitnya berkurang satu.Bila proses ini di lakukan berulang-ulang sampai semua sirkuit di G hilang,maka G menjadi sebuah pohon T , yang di namakan pohon merentang (spanning tree).Di sebut pohon merentang karena semua simpul pada pohon T sama dengan semua simpul pada grap G,dan sisi-sisi pada pada pohon T subset  sisi-sisi pada graf G.Dengan kata lain ,V₁=V dan E₁subset E (Bandingkan dengan definisi upagraf terhubung berbentuk pohon ,maka upagrap merentang tersebut di namakan pohon merentang).Gambar 9.4 adalah graf lengkap dengan empat buah pohon merentang ).Gambar 9.4 adalah graf lengakap dengan empat buah pohon merentangnya (coba anda temukan seluruh pohon merentang lainnya).

G                          T1                                      T2                                            T3                                         T4

Gambar 9.4 Graf lengkap G dan empat buah pohon merentangnya,

           Aplikasi pohon merentang misalnya pada pemeliharaan jalan raya.Misalkan graf G pada gambar 9.4 adalah peta jaringan jalan raya yang menghubungkan empat buah kota.karena dana pemeliharaan yang terbatas,pemerintah daerah mempertimbangkan hanya memelihara jalan-jalan sesedikit mungkin sedemikian sehingga kempat kota masih tetap terhubung satu sama lain.Masalah ini dapat di pecahkan dengan membuat upagraf yang mengandung jumlah sisi minimum dan mengandung semua simpul di dalam graf.Graf semacam itu haruslah pohon merentang.

.Gambar 9.5 memperlihatkan contoh sebuah jaringan computer dan router-router yang membentuk pohon merentang.

           Gambar 9.5 (a) jaringan computer ,(b) Pohon merentang multicast

Pada graf terhubung terdapat setidaknya satu buah pohon merentang.sifat ini di nyatakan dengan Teorema 9.2 berikut ini.

Teorema 9.2 setiap graf terhubung mempunyai paling sedikit satu  buah pohon merentang.

Teorema 9.2 menyetakan bahwa geraf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri.Pada graf yang mengandung sirkuit ,pohon merentangnya di peroleh dengan cara memutuskan  sirkuit yang ada.

            Sisi pada pohon merentang-di sebut cabang (branch) – adalah sisi dari graf semula,sedangkan tali-hubung (chord atau link)dari pohon adalah sisi darai graf yang tidak terdapat pada pohon merentang.pada graf terhubung dengan m buah sisi dan n buah simpul terdapat n-1buah cabang dan m – n + 1 buah tali.Himpunan tali-hubung beserta simpul yang bersisian dengannya di sebut komplemen pohon.Untuk Graf terhubung G dengan n buah simpul dan m buah sisi,kita dapat menghitung jumlah cabang dan tali hubung dengan rumus.

Jumlah cabang = n-1

Jumlah tali-hubung= m-n+1

Dan pada graf tidak terhubung dengan k komponen,m buah sisi dan n buah simpul,

Jumlah cabang = n-k

Jumlah tali-hubung =m-n+k

Jumlah cabang pada pohon  merntang dari sebuah graf G di sebut Rank garaf G,dan jumlah tali hubung pada Graf G di sebut nullity graf G.Dapat di lihat bahwa

Rank + nullity =jumlah sisi graf G

            Pohon Merentang Minimum

Bobot pohon merentang T dan D diantara semua pohon merentang di G,pohon merentang yang berbobot minimum-dinamakan pohon merentang minimum(minimum spanning tree)-merupakan pohon merentang yang paling penting.Pohon merentang minimum mempunyai terapan yang luas dalam praktek.Misalkan pemerintah akan membangun jalur rel kereta api yang menghubungkan sejumlah kota.Ada dua buah algoritma yang membangun pohon merentang minimum yaitu: Algoritma prim dan Algoritma kruskal.

1.    Algoritma Prim

Misalkan T adalah pohon merentang yang sisi-sisinya diambil dari dari graf G.Algoritma prim membentuk pohon merentang minimum langkah per langkah.Pada setiap langkah kia mengambil sisi e dari graf G yang mempunyai bobot minimum dan bersisian dengan simpul-simpul didalam T tetapi e tidak membentuk sirkuit didalam T.

ALGORITMA PRIM

1.       Ambil sisi dari graf G yang berbobot minimum,masukkan kedalam T.

2.       Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T,tetapi e tidak membentuk sirkuit di T.Masukkan e kedalam T.

3.       Ulangi 2 sebanyak n-2 kali.

Jumlah langkah seluruhnya didalam algoritma prim adalah 1+(n-2)=n-1,yaitu sebanyak jumlah sisi didalam pohon merentang dengan n buah simpul. Dalam notasi pseudo-code,algoritma prim kita tuliskan sebagai berikut:

Algoritma kruskal untuk membentuk pohon merentang minimum:

Procedure prim(input G:graf,output T:pohon)

{ Membentuk pohon merentang minimum T dari Graf erhubung G.

Masukkan: graf-berbobot terhubung G=(V,E) yang mana |v|=n

Keluarkan: pohon merentang minimum T=(V,E) }

Deklarasi

e: sisi         

Algoritma

T           sisi E yang mempunyai bobot minmimun didalam E

E          E –{e} { e sudah dipilih,jadi buang e dari E}

For i            1 to n – 2 do

e        sisi yang mempunyai bobot terkecil didalam E dan bersisian dengan simpul di T

T         T U{e} {masukkan ke kedalam T yang sudah terbentuk}

E         E  - {e} { e sudah dipilih,jadi buang e dari E}

Endfor

            Prim tidak menentukan sisi mana yan dipih jika terdapat lebih dari satu buah sisi yang berbobot sama.Satu cara untuk mengatasi hal ini adalah dengan mengurutkan sisi-sisi itu berdasarkan bobotnya dari kecil kebesar. Lagipula,pohon merentang minium yang dihasilkan tidak selalu unik. Graf sederhana terhubung dan berbobot dapat memiliki lebih dari satu buah pohon merentag minimum yang berbeda tapi jumlah bobot minimumnya tetap sama.

2.    Algoritma Kruskal

      Pada algoritma kruskal,sisi-sisi didalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil kebesar. Sisi yang dimasukkan kedalam himpunan  T adalah sisi graf G sedemikian sehingga T adalah pohon.Pada keadaan awal,sisi-sisi sudah diurut berdasarkan bobot membentuk hutan(forest),masing-masing pohon dihutan hanya berupa satu buah simpul.Hutan tersebut dinamakan hutan merentang(spanning forest).Sisi dari graf G ditambahkan ke T jika ia tidak membentuk siklus di T.

       Perbedaan prinsip antara algoritma prim dan kruskal adalah: jika pada algoritma prim dan kruskal adalah :jika pada algoritma prim sisi yang dimasukkan kedalam T harus bersisian dengan sebuah simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit(siklus).

                             ALGORITMA KRUSKAL

(Asumsi:sisi-sisi dari draf sudag diurut menaik berdasarkan bobotnya)

1.       T masih kosong

2.       Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T.Masukkan e ke dalam T

3.       Ulangi langkah 2 sebanyak n-1 kali.

Dalam notasi pseudo-code,algoritma prim kita tuliskan sebagai berikut:

Algoritma kruskal untuk membentuk pohon merentang minimum:

Procedure kruskal(input G :graf,output T : pohon)

{ Membentuk pohon merentang minium T dari graf terhubung G.

Masukkan: graf-berbobot terhubung G=(V,E).yamg mana |v|=n

Keluarkan:pohon rentang minimum T=(V,E’)

}

Deklarasi

I,p,q,u,v : integer

Algoritma

(Asumsi:sisi-sisi dari graf sudah diurut menaik berdasarkan bobotnya)

T           {}

While jumlah sisi T<n-1 do

e            sisi di dalam E yang bobotnya terkecil

E          E - {e} {e sudah dipilih,jadi buang e dari E}

If e tidak membentuk siklus di T then

T           T U {e} (Masukkan e kedalam T yang sudah terbentuk)

Endif

Endwhile

D.   Pohom Berakar

Definisi: pohon yang sebuah simpulnya diperlakuakan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar dinamakan pohon berakar(rooted tree).

Akar mempunyai derajat masuk sama dengan nol dan simpul-simpul lainnya berderajat masuk sama dengan satu. Simpul yang mempunyai derajat keluar sama dengan nol disebut daun atau simpul terminal. Simpul yang mempunyai derjat keluar tidak sama dengan nol disebut cabang atau simpul dalam.

Contoh 9.9 pohon berakar denagan A adalah simpul akarnya

b

a

c

d

g

f

e

j

i

h

 

Terminologi pada Pohon Berakar

Kebanyakan terminologi pohon yang ditulis dibawah ini diadopsi dari terminologi botani dan silsilah keluarga.

Anak (child atau children) dan Orangtua (parent)

Misalkan Xx adalah sebuah simpul didalam pohon berakar. Simpul y dikatakan anak simpul x jika ada sisi dari simpul x ke y. dengan demikian x disebut orangtua y.

b

a

c

d

f

e

j

i

h

Contoh gambar 9.11

m

l

k

g

 

B,C, dan, d adalah anak-anak simpul a, dan a adalah orangtua dari anak-anak itu. E an F adalah anak-anak simpul B, dan B adalah orangtua dari E dan F. G adalah anak simpul D dan D adalah orangtua G simpul H,I,J, dan M tidak mempunyai anak 

Keturunan (descendant) dan leluhur (ancestor)

jika terdapat lintasan dari simpul x ke simpul ydidalam pohon, maka x adalah leluhur dari simpul y, dan y adalah keturunan simpul x.

contoh gambar 9.11. B adalah leluhur simpul H, dengan demikian H adalh ketrunan B.

b

a

c

d

f

e

j

i

h

 

           

g

k

m

l

 

Saudara kandung (sibling)

simpul yang berorangtua sama adalah saudara kandung satu sama lain. Pada gambar 9.11 F adalah saudara kandung E. tetapi, G bukan saudara kandung E karena orangtua mereka berbeda.

Derajat (degree)

Derajat sebuah simpul pada pohon berakar adalah jumlah upapohon (atau jumlah anak) pad simpul tersebut  pada gambar 9.11 derajat A adalah 3, drajat b adalah 2, derajat D adalah 1 dan derajat C adalah 0. Jadi derajat tertinggi dari seluruh simpul sama dengan 3.

            Daun (leaf)

Simpul yang berderajat 0( atau tidak mempunyai anak) disebut daun. Simpul

h,I,j,f,c,l, dan m adalah daun.

            Simpul dalam (internal nodes)

b

a

c

d

f

e

j

i

h

g

k

l

m

 

Simpul yang mempunyai anak disebut simpul dalam. Contoh pada gambar 9.11 Simpul D,E,G, dan K adalah simpul dalam.

                                   

E.   Pohon Berakar Terurut

Definisi:pohon berakar yang urutan anak-anaknya penting disebut pohon terurut(orderet tree).Terdapat dua buah pohon yang berakar sama , tetapi sebagai pohon terurut,keduanya berbeda. Misalkan urutan anak-anak dari simpul 1 pada gambar (a) adalah 2,3,4 sedangkan urutan anak-anak  dari simpul 1 pada gambar (b) adalah 3,4,2.

F.   Pohon  m-ary

Definisi:pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buah anak disebut m-ary.Pohon m-ary diktakan pohon penuh atau pohon teratur jika setip simpul cabangnya mempunyai tepat m buah anak.

            Jumlah daun pada pohon m-ary penuh

Pohon m-ary penuh adalah pohon yang setiap simpulnya tepat mempunyai m buah anak. Pada pohon m-ary penuh dengan ,mlah daun ad jutiggi h, jumlah daun adalah m^h

Contoh pohon 3-ary penuh dengan jumlah daun=3²=9

Jumlah seluruh simpul pada pohon m-ary penuh

Pada pohon m-ary penuh dengan tinggi h,

Aras 0         jumlah simpul=m⁰=1

Aras 1        jumlah simpul=m¹

Aras 2         jumlah simpul=m²

…

Aras  h         jumlah simpul=m^h

                             Maka jumlah seluruh simpul adalah

                             S=m⁰+m¹+m²+….+m^h=

G.   Pohon Biner

a

a

Pohon m-ary yang paling penting adalah pohon biner (binary tree). Pohon biner pmerupakan pohon m-ary jika m = 2. Pohon biner adalah pohon yang setiap simpul cabangnya mempunyai paling banyak dua buah anak.

b

c

d

Gambar 9.20 dua buah pohon biner yang berbeda

Gambar 9.22 Pohon Biner Penuh

a

a

b

c

d

b

c

d

b

c

d

 

Pohon Biner Penuh ( fuul binary tree ) adalah pohon biner yang setiap simpulnya tepat dua buah anak, kiri dan kanan, kecuali simpul pada baris bawah.

                             Gambar 9.22 Pohon biner penuh

        Pohon Biner Seimbang( balanced binary tree ) adalah pohon buner yang perbedaan tinggi antara upapohon kiri dan upapohon maksimal.

               Pohon biner merupakan struktur yang penting dalam ilmu komputer. Terapan pohon biner didalam ilmu komputer sangat banyak, diantaranya yang disebutkan disini adalah pohon ekspresi ( expression tree ), pohon keputusan ( decision tree ), kode prefiks ( prefix code ) kode huffman ( Huffman code ) dan pohon pencarian biner ( binary search tree ).

H.   Pohon Ekspresi

Pohon ekspresi di gunakan oleh Compiler bahasa tingkat tinggi untuk mengevaluasi ekspresi yang di tuliskan dalam notasi Infix, Prefix (Polis Natation), dan Prefix (Inverse Polish Natation).Dalam notasi Infix, Operator berada di antara dua operand, pada notasi prefix, operator mendahului dua buah operand-nya, dan padanotasi prestfix ke dua operand mendahului operatornya.

Ekspresi (a+b).*(c/(d+e)) adalah dalam bentuk infix, sedangkan ekspresi prefix-nya adalah *+ab/c +de dan ekspresi prefix-nya adalah a b + c d e + / *

Contoh 9.7Gambarkan pembentukan pohon ekspresi dari ekspresi (a+b)*(c/(d+e)) di atas ??

Penyelesaian :

Pohon ekspresi dari notasi infix di bangun dari bawah ke atas dengan memperhatikan urutan prioritas pengerjaan operator. Operator / dan * mempunyai prioritas yang lebih tinggi dari pada operator + dan -. Mula-mula membentuk upapohon untuk (d+e), kemudian upapohon untuk c/(d+e), pohon untuk (a+b) dan akhirnya menggabungkan upapohon (a+b) dengan upapohon d/(d+e). pohon ekspresi di perlihatkan pada Gambar 9.25

(I)

(iii)

+

+

*

+

/

+

Gambar 9.25 Pembentukan Pohon Ekspresi dari (a+b)*(c/(d+e))

+

/

(iv)

(ii)

 

Pembentukan Pohon Ekspresi dari Notasi Postfix

Jika di berikan ekspresi dalam notasi Postfix, kita dapat membangun pohon ekspresinya dengan algoritma di bawah ini. Untuk itu, kita membutuhkan sebuah tabel dan sebuah tumpukan (Stack)

1.      Setiap Elemen (Operand dan Operator) dari notasi postfix yang panjangnya n di simpan di dalam tabel sebagai elemen P_1,P₂,…..,P_n.

1	2	3	4	5	6	7	8	n=9
A	B	+	C	d	e	+	/	*

2.       Tumpukan S Menyimpan pointer ke simpul pohon biner (Bayangkanlah Tumpukan Tumbuh dari “Kiri” ke “Kanan”)

Arah Pertumbuhan Tumpukan

 

Prosedur bangun pohon ekspresi dari Postfix (Input P_1,,P₂….P_n : Elemen Postfix, output T : Pohon)

{ Membangun Pohon Ekspresi dari notasi Postfix

Masukan           : Notasi Postfix, setiap elemennya di simpan di dalam tabel P

Keluarkan         : Pohon Ekspresi T

}

Deklarasi

I           : Integral

S          : Stack

T₁,T₂     : Pohon

Algoritma

For i        1 to n do

     If  P₁ = operand then

       Buat (Create) satu buah simpul untuk P

      Masukan (Push) pointernya ke dalam tumpukan S

Else   {P₁ =Operator}

     Ambil (pop) pointer dua upapohon T₁ dan T₂ dari puncak tumpukan S

    Buat pohon T yang akarnya adalah Operator dan Upapohon kiri

   Dan upapohon kanannya masing T₁  dan T₂.

Endif

Endtor

Algoritma 9.3 Pembentukan Pohon Ekspresi dari Notasi Postfix.

Algoritma Pembentukan Pohon ekspresi dari notasi prefix relatif sukar di pahami sehingga tidak di bicarakan di dalam bab ini.

Contoh 9.8

Terapkan Algoritma Bangun Pohon Ekspresi Dari posfix Untuk Membangun Pohon Ekspersi dari Notasi posfix   a b + c d e + / * .

Penyelesaian

        i.            Mulai dari elemen potfix pertama, P_1. Karena P₁ = ‘a’ = operand, buat simpul untuk P_1, Push pointer-nya ke dalam tumpukan S.

a

      ii.            Baca P_2. Karena P₂ = ‘b’ = operand, Buat simpul untuk P_2, Push pointernya ke tumpukan S.

b

a

    iii.            Baca P₃, Karena P₃ = ‘+’ = Operator, Buat Pohon T dengan ‘a’ dan ‘b’ sebagai anak.

+

a

b

     iv.            Baca P₄,P₅,P₆ Karena P₄,P₅,P₆= operand, buat simpul untuk P₄,P₅dan P₆push pointer-nya kedalam tumpukan S

e

d

c

a

b

+

       v.            Baca P₇karena P₇= ‘+’ = operator, buat pohon T dengan ‘d’ dan ‘e’ sebagai anak.

a

d

e

b

c

+

     vi.            Baca P₈Karena P₈= ‘/’=operator, buat pohon T dengan ‘c’ dan ‘+’ sebagai anak.

/

a

c

d

e

+

b

+

vii.              Baca P₉karena P₉ = ‘*’ = operator, buat pohon T dengan ‘+’ dan ‘*’sebagai anak.

+

a

b

d

e

/

+

c

*

Karena elemen tabel P sudah habis di baca, maka tumpukan S akan berisi pointer yang menunjuk ke akar pohon ekspresi.

I.    Pohon Keputusan

Pohon Keputusan digunakan untuk memodelkan persoalan yang terdiri dari serangkaian keputusan yang mengarah kesolusi. Sebagai contoh kita ingin mengurutkan tiga buah bilangan, a,b, dan c. pohon keputusan untuk persoalan ini di tunjukan pada gambar 9.26.

a : b

a : b

a : b

a : b

c >a>b

a : c

c >b>a

a>b

b>a

a>c

c>a

b>c

c>b

a>b>c

a>c>b

b>a>c

b>c>a

b>c

c >b

a>c

c >a

Gambar 9.26 Pohon Keputusan Untuk Mengurutkan 3 Buah Elemen

 

J.    Kode Awalan

          Kode awalan (prefix code) adalah himpunan kode, misalnya kode biner, sedemikian sehingga tidak ada anggota kumpulan yang merupakan awalan dari anggota yang lain. Contohnya himpunan :

{000,001,01,10,11}

Adalah kode awalan, tetapi

{1,00,01,000,0001}

Bukan kode awalan sebab 00 adalah prefiks dari 0001.

            Kode aawalan mempunyai pohon biner yang bersesuain. Sisi di beri label 0 atau 1. Pelabelan sisi harus taat-asas, yakini semua sisi kiri di labeli 0 saja (atau 1 saja),sedangkan sisi kanan di labeli 1 saja (atau 0 saja). baRisan sisi yang di lalui oleh lintasan dari akar ke daun menyatakan kode awalan. Kode awalan ini di tulis pada daun. Contoh himpunan pertama mempunyai pohon biner pada Gambar 9.27.

Kegunaan kode awalan adalah untuk mengirim pesan pada komunikasi data. Setiap karakter di dalam pesan di representasikan dengan angka 0 dan 1. Untuk mengirim pesan kita Cuma mengirimkan string angka 0 dan 1 yang merepresentasikan karakter dalam pesan oleh pihak penerima, string angka 0 dan 1 ini di kembalikan lagi ke karakter penyusun pesan semula agar tidak timbul ambigu dalam mengkonfersikan kembali string 0 dan 1 menjadi karakter semula, maka setiap karakter tidak boleh mempunyai kode yang merupakan awalan bagi kode yang lain.

0

1

0

0

0

1

1

1

000

001

01

10

11

 

Gambar 9.27 Pohon biner dari kode prefiks {000,001,01,10,11}

                    

K.   Kode Huffman

Dalam komunikasi data, pesan (message) yang dikirim seringkali ukurannya sangat besar sehingga waktu pengirimannya lama. Begitu juga dalam penyimpanan data, arsip (file) yang berukuran besar memakan ruang penyimpanan yang besar. Kedua masalah ini dapat diatasi dengan mengkodekan pesan atau isi sesingkat mungkin, sehingga waktu pengiriman pesan juga relatif cepat, dan ruang penyimpanan yang dibutuhkan juga sedikit. Cara pengkodean seperti ini disebut pemampatan (compression) data. Pemampatan data dilakukan dengan mengkodekan setiap karekter di dalam pesan atau di dalam arsip dikodekan dengan kode yang lebih pendek. Sistem kode yang banyak digunakan adalah kode ASCII. Dengan kode ASCII, setiap karekter dikodekan dalam 8 bit biner. Tabel 9.3 berikut adalah contoh kode ASCII untuk beberapa karekter:

Tabel 9.3 Kode ASCII

Simbol	Kode ASCII
A	01000001
B	01000010
C	01000011
D	01000100

Dengan mengikuti ketentuan pengkodean diatas, string  ‘ABACCDA’ direpresentasikan menjadi rangkaian bit:

010000010100000100100000101000100100000110100000110100010001000001

Jadi, dengan sistem pengkodean ASCII, representasi 7 huruf membutuhkan 7 x 8 = 56 bit (7 byte). Untuk meminimumkan jumlah bit yang dibutuhkan, panjang kode untuk setiap karekter sedapat mungkin diperpendek, terutama untuk karekter yang kekerapan (frequency) kemunculannya besar. Pemikiran seperti inilah yang mendasari munculnya Kode Huffman. Misalnya pada pesan ‘ABACCDA’, kekerapan kemunculan A adalah 3, kekerapan B adalalah 1, kekerapan C adalah 2, kekerapan kemunculan D adalah 1, sehingga dapat dibuat Tabel 9.4 berikut:

Tabel 9.4 Tabel Kekerapan dan Kode Huffman ubtuk string ‘ABACCDA’

Simbol	Kekerapan	Peluang	Kode Huffman
A	3	3/7	0
B	1	1/7	110
C	2	2/7	10
D	1	1/7	111

Dengan menggunakan Kode Huffman didalam Tabel 9.4, pesan “ABACCDA” direpresentasikan menjadi rangkaian bit:

0110010101110

Jadi, dengan menggunakan Kode Huffman ini, jumlah bit yang dibutuhkan untuk string ‘ABACCDA’ hanya 13 bit. Kode Huffman adalah kode prefiks. Cara pembentukan Kode Huffman adalah dengan membentuk pohib biner, yang dinamakan pohon Huffman, sebagai berikut:

a.       Pilih dua simbol dengan peluang (probability) paling kecil (pada contoh diatas simbol B dan D). Kedua simbol tadi dikombinasikan sebagai simpul orangtua dari simbol B dan D sehingga menjadi simbol BD dengan peluang 1/7 + 1/7 = 2/7, yaitu jumlah peluamg kedua anaknya.

b.       Selanjutnya, pilih dua simbol berikutnya, termasuk simbol baru, yang mempunyai peluang terkecil. Pada contoh ini, dusa simbol tersebut adalah C (peluang = 2/7) dan BD (peluang = 2/7).

c.        Prosedur yang sama dilakukan pada dua simbol berikutnya yang mempunyai peluang terkecil., yaitu A (peluang = 3/7) dan CBD(peluang 4/7) sehingga menghasilkan simpul ABCD, yang merupakan akar pohon Huffman dengan peluang 3/7 + 4/7 = 7/7.

Perhatikan bahwa Kode Huffman tidak bersifat unik, artinya kode untuk setiap karakter berbeda-beda pada setiap pesan bergantung pada kekerapan kemunculan karakter tersebut di dalam pesan. Selain itu, keputusan apakah suatu simpul pada pohon Huffman diletakkan di keri atau di kanan juga menentukan kode yang dihasilkan (tetapi tidak mempengaruhi panjang kodenya).

L.   Pohon Pencarian

Pohon pencarian biner ( binary search tree – BST ) mungkin adalah pohon biner yang paling penting, khususnya pada persoalan yang banyak melakukan operasi pencarian, penyisipan, dan penghapusan elemen. Untuk operasi semacam itu, pohon pencarian biner memiliki kinerja yang lebih baik dari pada struktur data lain, yang dalam hal ini waktu pencarian.

            Simpul pada pohon pencarian dapat berupa field kunci ( kunci ) pada data record, atau data itu sendiri ( dengan catatan setiap data adalah unik ). Kunci adalah nilai yang membedakan setiap simpul dengan simpul yang lainnya. Kunci harus unik, karena itu tidak ada dua buah simpul atau lebih yang mempunyai kunci yang sama.

            Pohon pencarian biner adalah pohon biner yang setiap kuncinya diatur dalam suatu urutan tertentu. Ketentuan pengaturan kunci adalah sebagai berikut :

Jika R adalah akar, dan semua kunci yang tersimpan pada setiap simpul tidak ada yang sama maka :

a.       Semua simpul pada upapohon kiri mempunyai kunci lebih kecil dari kunci ( R )

b.       Semua simpul di upapohon kanan mempunyai kunci nilai lebih besar dari kunci ( R )

Contoh :

Data 50, 32, 18, 40, 60, 52, 5, 25, 70

50

32                     60

18                     40         52         70

5                      25

Perhatikanlah contoh diatas, bahwa simpul di upapohon kiri 50 mempunyai kunci lebih kecil dari 50, dan simpul di upapohon kanan 50 mempunyai kunci lebih besar dari 50. Secara rekursif, simpul lainnya juga mempunyai pola demikian.

Tranversal Pohon Biner

Operasi dasar yang sering dilakukan pada pohon biner ialah mengunjungi ( transversal ) setiap simpul tepat satu kali. Misalkan T  adalah pohon biner, akarnya R, upapohon T₁dan upapohon kanan T₂.

Ada tiga macam skema mengunjungi simpul-simpul di dalam pohon biner T :

1.       Preorder

a.       Kunjungi R ( sekaligus memproses simpul R )

b.       Kunjungi T₁ secara preorder

c.        Kunjungi T₂ secara preorder

2.       Inorder

a.        Kunjungi T₁ secara inorder

b.       Kunjungi R ( sekaligus memproses simpul R )

c.        Kunjungi T₂ secara inorder

3.       Postorder

a.       Kunjungi T₁ secarapostorder

b.       Kunjungi T₂ secara postorder

c.        Kunjungi R ( sekaligus memproses simpul R  )

Proses yang dilakukan terhadap simpul yang dikunjungi misalnya mencetak informasi yang disimpan didalam sampul, memanifulasi nilai, dan sebagainya.

Tinjau pohon biner T dibawah ini :

A

B                      C

D                     E          F          G

                        H                                 I           J

Lintasan preorder, inorder, dan postorder dari T adalah :

            preorder : A, B, D, E, F, C, F, G, I, J

inorder : D, B, H, E, A, F, C, I, G, J

postorder : D, H, E, B, F, I, J, G, C, A

Ada korespondensi antara ketiga cara mengunjungi pohon biner dengan notasi prefix, infix, dan postfix. Misalkan pohon yang dikunjungi adalah pohon ekspresi. Penelusuran pohon secara preorder, inorder, dan postorder masing-masing menghasilkan ekspresi dalam notasi prefix, infix, dan postfix sebagai berikut :

Preorder            : *+a / b c – d*e f                      ( prefix )

Inorder  : a + b / c*d – e * f                    ( infix )

Postorder           : a b c / + d e f* - *                    ( postfix )

*

+                      -

a                      /          d          *

                                    b          c           e           f

Preorder, Inorder, dan Postorder pada Pohon m-ary

Skema preorder, postorder dan inorder pada pohon biner dapat dirampatkan sehingga berlaku untuk sembarang pohon m-ary. Misalkan T adalah pohon m-ary, akarnya R, dan upaohonnya adalah T₁, T₂, …., T_n. Transversal preorder, inorder, dan postorder pada pohon m-ary  didefinisikan sebagai berikut :

1.       Preorder

a.       Kunjungi R

b.       Kunjungi T_1, T₂, ….., T_nsecara preorder

2.       Inorder

a.       Kunjungi T₁secara inorder

b.       KunjungiR

c.        Kunjungi T₂, T₃, ….., T_nsecara inorder

3.       Postorder

a.       Kunjungi T_1, T₂, ….., T_nsecara postorder

b.       KunjungiR

        

BAB III

PENUTUP

A.        Kesimpulan

            Pohondidefinisikansebagaisuatugraftakberarahterhubungkan (connected undirected graph) yang tidakmengandungrangkaiansederhana.Pohonadalahbentukkhususdarisuatugraf yang banyakditerapkanuntukberbagaikeperluan.Misalnyastrukturorganisasisuatuperusahaan, silsilahsuatukeluarga, skemasistemgugursuatupertandingan, danikatankimiasuatumolekuladalahjenisgraf yang tergolongsebagaipohon.Padapohon, simpul-simpul yang berderajatsatudinamakandaun (leave), sedangkansimpul yang derajatnyalebihbesardaripadasatudinamakansimpulcabang (branch node) atausimpul internal (internal node) dankumpulanpohon-pohon yang terpisahkansatusama lain disebuthutan (forest).

            Pohonkeputusanjugadapatdipergunakanuntukmemperhitungkandanmelakukananalisaterhadapresiko-resiko yang mungkinmunculdalamsuatualternatifpemilihankeputusan.Selainitu, pohonkeputusanjugadapatdipakaiuntukmemperhitungkanberapanilaisuatuinformasitambahan yang mungkinkitaperlukan agar kitadapatlebihmampudalammembuatsuatupilihankeputusandarisuatualternatif-alternatifkeputusan yang ada.

B.        Kritik dan Saran

Semogamakalahinidapatmemberikanpelajaranbagikitasemuauntukmenambahwawasan yang adadanilmu yang bermanfaatsertamembantudalam proses pembelajaranMatematika Diskrit khususnya.

Atasketerbatasankemampuanpenulis/kelompoksertaketerbatasan media yang di gunakandalampembuatanmakalahinisehinggamakalahinidapatterselesaikan, danapabilaterdapatbanyakkesalahanataupunkekurangan yang dimilikimakalahinipenulismengharapkankritikdan saran yang membangun demi memperbaikimakalahselanjutnya.