pohon - ledyaldn.staff.telkomuniversity.ac.id

POHON

Pohon

adalah graf tak-berarah terhubung yang tidakmengandung sirkuit

pohon pohon bukan pohon bukanpohon

a b

c d

e f

a b

c d

e f

a b

c d

e f

a b

c d

e f

Hutan (forest)

kumpulan pohon yang saling lepasgraf tidak terhubung yang tidak mengandung sirkuit. Setiap komponen di dalam graf terhubung tersebutadalah pohon.

Hutan yang terdiri dari tiga buah pohon

Sifat-sifat PohonMisalkan G = (V, E) adalah graf tak-berarah sederhana danjumlah simpulnya n. Maka, semua pernyataan di bawah iniadalah ekivalen:

G adalah pohon.Setiap pasang simpul di dalam G terhubung denganlintasan tunggal.G terhubung dan memiliki m = n – 1 buah sisi.G tidak mengandung sirkuit dan memiliki m = n – 1 buahsisi.G tidak mengandung sirkuit dan penambahan satu sisipada graf akan membuat hanya satu sirkuit.G terhubung dan semua sisinya adalah jembatan.

Pohon Merentang (spanning tree)

Pohon merentang dari graf terhubung adalah upagraf merentangyang berupa pohon.Pohon merentang diperoleh dengan memutus sirkuit di dalam graf.

Setiap graf terhubung mempunyai paling sedikit satu buah pohonmerentang.Graf tak-terhubung dengan k komponen mempunyai k buah hutanmerentang yang disebut hutan merentang (spanning forest).

G T1 T2 T3 T4

Aplikasi Pohon Merentang

Jalan-jalan seminimummungkin yang menghubungkan semuakota sehingga setiap kotatetap terhubung satusama lain.Perutean (routing) pesanpada jaringan komputer.

Contoh

(a) (b)Router

Subnetwork

Pohon Rentang Minimum

Graf terhubung-berbobot mungkin mempunyai lebih dari1 pohon merentang.Pohon rentang yang berbobot minimum –dinamakanpohon merentang minimum (minimum spanning tree).

a

bc

d

e

f

g

h55

5

40

25

45

30

5020

15

35 10

a

bc

d

e

f

g

h

5

40

25 30

20

15

10

Algoritma Prim

Langkah 1: ambil sisi dari graf G yang berbobotminimum, masukkan ke dalam T.

Langkah 2: pilih sisi (u, v) yang mempunyai bobotminimum dan bersisian dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Masukkan (u, v) ke dalam T.

Langkah 3: ulangi langkah 2 sebanyak n – 2 kali.

Algoritma Prim

Graph Pohon merentangminimum

1 2

3

4

5

6

10

45

2015

35

55

25

1 2

3

4

5

6

1050

4530

2015

35

55

25

40

Algoritma Kruskal

Langkah 0: sisi-sisi dari graf sudah diurut menaikberdasarkan bobotnya – dari bobot kecil kebobot besar

Langkah 1: T masih kosongLangkah 2: pilih sisi (u, v) dengan bobot minimum

yang tidak membentuk sirkuit di T. Tambahkan(u, v) ke dalam T.

Langkah 3: ulangi langkah 2 sebanyak n – 1 kali.

Algoritma Kruskal

Graph Pohon merentangminimum

1 2

3

4

5

6

10

45

2015

35

55

25

1 2

3

4

5

6

1050

4530

2015

35

55

25

40

Pohon Berakar

Pohon yang satu buahsimpulnya diperlakukansebagai akar dan sisi-sisinya diberi arahsehingga menjadi grafberarah dinamakanpohon berakar (rooted tree).

a bPohon berakar panah dibuang

Pohon Berakar

Pohon dan dua buah pohon berakar yang dihasilkan daripemilihan dua simpul berbeda sebagai akar

a

b

c

d

e f

g

h

f

g

a

b

cd

e

f

g h

d

e

hb

a c

b sebagai akar e sebagai akar

Terminologi pada Pohon Berakar

1. Anak (child atau children) dan Orangtua (parent)b, c, dan d adalah anak-anaksimpul a, a adalah orangtua dari anak-anak itu

2. Lintasan (path)Lintasan dari a ke j adalah a, b, e,

j. Panjang lintasan dari a ke j

adalah 3.

a

b

k

g

j

f

c d

ml

i

e

h

Terminologi pada Pohon Berakar

Saudara kandung (sibling)f adalah saudara kandung

e, tetapi, g bukan saudara

kandung e, karenaorangtua merekaberbeda.

Upapohon (subtree)

a

b

k

g

j

f

c d

ml

i

e

h

Terminologi pada Pohon Berakar

a

b

k

g

j

f

c d

ml

i

e

h

Derajat (degree)Derajat sebuah simpul adalah jumlah

upapohon (atau jumlah anak) pada simpultersebut.

Derajat a adalah 3, derajat b adalah 2, Derajat d adalah satu dan derajat c adalah 0. Jadi, derajat yang dimaksudkan disini adalah

derajat-keluar.Derajat maksimum dari semua simpul

merupakan derajat pohon itu sendiri. Pohon di samping berderajat 3

Terminologi pada Pohon Berakar

a

b

k

g

j

f

c d

ml

i

e

h

Daun (leaf)Simpul yang berderajat nol(atau tidak mempunyai anak) disebut daun. Simpul h, i, j, f, c, l, dan madalah daun.

Simpul Dalam (internal nodes)Simpul yang mempunyai anakdisebut simpul dalam. Simpul b, d, e, g, dan k adalahsimpul dalam.

Terminologi pada Pohon Berakar

Aras (level) atau Tingkat Tinggi (height) atauKedalaman (depth)

Aras maksimum darisuatu pohon disebuttinggi atau kedalamanpohon tersebut. Pohon disebelah mempunyaitinggi 4.

a

b

k

g

j

f

c d

ml

i

e

h

0

1

2

3

4

Aras

Pohon Terurut

Pohon berakar yang urutan anak-anaknya pentingdisebut pohon terurut (ordered tree).

1

2

6 87

34

9

10

5

1

2

68 7

3 4

9

10

5

Pohon m-ary

Pohon berakar yang setiap simpulcabangnya mempunyai paling banyak mbuah anak disebut pohon m-ary. Jika m = 2, pohonnnya disebut pohonbiner (binary tree. Pohon m-ary dikatakan teratur ataupenuh (full) jika setiap simpul cabangnyamempunyai tepat m anak.

Terminologi pada Pohon Berakar

Pohon parsing dari kalimat A tall boy wears a red hat

<subject> <verb> <object>

<article> <noun phrase> wears article> <noun>

A <adjective> <noun> a <adjective> <noun>

tall boy red hat

< sentence>

Pohon m-ary Teratur

Jumlah daun pada pohon n-ary teraturdengan tinggi h adalah nh

Jumlah seluruh simpul pada pohon n-aryteratur dengan tinggi h

S= n0+n1+n2+…..+nh

111

−−

=+

nnh

Pohon Binera

b c

d

a

b c

d

Gambar Dua buah pohon biner yang berbeda

Pohon Biner

a

b

c

d

a

b

c

d

Pohon condong-kiri pohon condong kanan Pohon biner penuh

Pohon Biner Seimbang

Pada beberapa aplikasi, diinginkan tinggi upapohon kiridan tinggi upapohon kanan yang seimbang, yaituberbeda maksimal 1.

T1 T2 T3

T1 dan T2 adalah pohon seimbang, sedangkan T3 bukan pohonseimbang.

Terapan Pohon Biner

Pohon Ekspresi

Pohon ekspresi dari (a + b)*(c/(d + e))

*

+ /

a b+

d e

c

Terapan Pohon Biner

Pohon Keputusan

Pohon keputusan untuk mengurutkan 3 buah elemen

a : b

a : c b : c

b : c c > a > b a : c c > b > b

a > b > c a > c > b b > a > c b > c > a

Terapan Pohon Biner

Kode Awalan

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

1

11

1

0

0

0

0

111001

001000

Terapan Pohon Biner

Kode Huffmanrangkaian bit untuk string ‘ABACCDA’: 01000001010000010010000010100000110100000110100010001000001atau 7 × 8 = 56 bit (7 byte).

1000100D

1000011C

1000010B

1000001A

Kode ASCIISimbol

Terapan Pohon Biner

Kode Huffmanrangkaian bit untuk’ABACCDA’:0110010101110hanya 13 bit!

1111/71D

102/72C

1101/71B

03/73A

KodeHuffman

PeLuang

Kekera

pan

Simbol

Terapan Pohon Biner

Pohon Pencarian Biner

R

T1 T2

Kunci(T1) < Kunci(R)

Kunci(T2) > Kunci(R)

Terapan Pohon Biner

Data: 50, 32, 18, 40, 60, 52, 5, 25, 7050

32

4018

50

52 70

5 25

Penelusuran Pohon Biner

1. Preorder : R, T1, T2- kunjungi R- kunjungi T1 secara

preorder- kunjungi T2 secara

preorder

R

T1 T2

Langkah 1: kunjungi R

Langkah 2: kunjungi T1secara preorder

Langkah 3: kunjungi T2secara preorder

Penelusuran Pohon Biner

2. Inorder : T1 , R, T2- kunjungi T1 secara

inorder- kunjungi R- kunjungi T2 secara

inorder

R

T1 T2

Langkah 2: kunjungi R

Langkah 1: kunjungi T1secara inorder

Langkah 3: kunjungi T2secara inorder

Penelusuran Pohon Biner

Postorder : T1, T2 , R- kunjungi T1 secara

postorder- kunjungi T2 secara

postorder- kunjungi R

R

T1 T2

Langkah 3: kunjungi R

Langkah 1: kunjungi T1secara postorder

Langkah 2: kunjungi T2secara postorder

Penelusuran Pohon Biner

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