pohon - ledyaldn.staff.telkomuniversity.ac.id
TRANSCRIPT
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