tugas algoritma pengolahan paralel

8/15/2019 Tugas Algoritma Pengolahan Paralel

1/10

TUGAS ALGORITMA PENGOLAHANDAN PARALEL(TREE TRAVERSAL)

Nama Kelompok : Agus Haryanto

Fajar Rizky PramonoIchsan Octama

Riyan MardikaRiyana Wicaksono

Rizki Fajar RamadhanTaufik Sudarmadi

Kelas : 4IA!

FAKULTAS TEKNOLOGI INDUSTRIUNIVERSITAS GUNADARMA

2!"

T#ee T#a$e#sal

Tr"" tra#"rsa$ atau Tr"" S"arch ada$ah sa$ah satu %"ntuk darigra&h tra#"rsa$ yang ditujukan untuk &ros"s kunjungan tia& nod" 'hanyas"ka$i( da$am struktur data &ohon 'tr""()Tia& tra#"rsa$ digo$ongkan%"rdasarkan urutan nod" yang dikunjungi) A$goritma t"rs"%ut ditujukan


2/10

untuk &ohon %inary '%inary s"arch( ta&i umumnya digunakan untuk j"nis&ohon $ainnya)

Pohon 'Tr""( ada$ah graf t"rhu%ung yang tidak m"ngandung sirkuit)*ar"na m"ru&akan graf t"rhu%ung maka &ada &ohon s"$a$u t"rda&at &athatau ja$ur yang m"nghu%ungkan k"dua sim&u$ di da$am &ohon) Pohondi$"ngka&i d"ngan Root (akar))

+ontoh , Pohon %"rakar T

P

% T

R S U

V &

Sifat utama &ohon %"rakar ,-) .ika &ohon m"m&unyai sim&u$ s"%anyak n/ maka %anyaknya ruas

ada$ah 'n0-() Pada contoh , %anyak sim&u$ ada$ah 1 maka %anyaknyaruas ada$ah 2)

3) M"m&unyai sim&u$ khusus yang dis"%ut Root 'Akar(/ jika sim&u$

t"rs"%ut m"mi$iki d"rajat k"$uar ≥ dan d"rajat masuk ) Sim&u$ P

m"ru&akan root)!) M"m&unyai sim&u$ yang dis"%ut 5"af '6aun(/ jika sim&u$ t"rs"%ut

m"mi$iki d"rajat k"$uar dan d"rajat masuk -) Sim&u$ R/ S/ 7/ Wm"ru&akan daun &ada &ohon T)

4) S"tia& sim&u$ m"m&unyai tingkatan '$"#"$(/ dimu$ai dari root d"ngan$"#"$ sam&ai d"ngan $"#"$ n &ada daun yang &a$ing %a8ah)Pada contoh ,P m"m&unyai $"#"$ 9/ T m"m&unyai $"#"$ -R/ S/ : m"m&unyai $"#"$ 37/ W m"m&unyai $"#"$ !Sim&u$ yang m"m&unyai $"#"$ yang sama dis"%ut ;"rsaudara ';roth"r


3/10

?) Pohon m"m&unyai %"rat '%o%ot < 8"ight( yaitu %anyaknya daun &ada&ohon) ;"rat &ohon T ada$ah 4

POHON 'INAR ('INAR TREE)

Pohon %inar ada$ah him&unan sim&u$ yang t"rdiri dari 3 su%&ohon'yang disjoint < sa$ing $"&as( yaitu su%&ohon kiri dan su%&ohon kanan)

S"tia& sim&u$ dari &ohon %inar m"m&unyai d"rajat k"$uar maksimum 3)P"nd"finisian &ohon %inar %"rsifat r"kursif) Pohon %inar aca&ka$i disajikan

da$am %"ntuk diagram)

+ontoh ,

A

'

D E G H

F * K

L

:ntuk m"nggam%arkan suks"sor kiri dan suks"sor kanan/ di%uatgaris k" kiri %a8ah dan k" kanan %a8ah) ; ada$ah suks"sor kiri dari A/s"dangkan + ada$ah suks"sor kanan dari A) Su%&ohon kiri dari Am"ngandung sim&u$ ;/ 6/ @ dan F/ s"dangkan su%&ohon kananm"ngandung sim&u$ +/ / H/ ./ * dan 5)

Pada contoh di atas ,Root ada$ah ASim&u$ yang m"m&unyai 3 anak ada$ah sim&u$ A/ ;/ + dan H)Sim&u$ yang m"m&unyai - anak ada$ah sim&u$ @ dan .)Sim&u$ yang tidak m"m&unyai anak dis"%ut daun 't"rmina$( ada$ah 6/ F// * dan 5)


4/10

P"rhatikan &ohon T- dan T3 dan T! ini ,

T- T3 T!

A S A

' T U '

D E V & D E

6ua &ohon %inar dis"%ut simi$ar jika m"m&unyai struktur '%angun


5/10

A

' D

E F G H I *

K L

Langkah Pertama

A

' D

E F G H I *

K L


6/10

Langkah kedua A

'

E

F D

G H

K I

L *

NOTASI PREFI+, INFI+ DAN POSTFI+ SERTA TRAVERSAL

POHON

Tra#"rsa$ ada$ah &ros"s kunjungan da$am &ohon/ d"ngan s"tia& Sim&u$

hanya dikunjungi t"&at satu ka$i)

Tiga k"giatan yang t"rda&at da$am tra#"rsa$ &ohon %inar ada$ah ,

-) M"ngunjungi sim&u$ akar 'root(

3) M"$akukan tra#"rsa$ su%&ohon kiri/ dan

!) M"$akukan tra#"rsa$ su%&ohon kanan


7/10

T"rda&at tiga macam tra#"rsa$ &ohon/ yaitu ,

-) Tra#"rsa$ Pr"0ord"r/ di$akukan %"rturut0turut ,

a) *unjungi sim&u$ akar

%) 5akukan tra#"rsa$ su%&ohon kiri

c) 5akukukan tra#"rsa$ su%&ohon kanan

3) Tra#"rsa$ In0ord"r/ di$akukan %"rturut0turut ,

a) 5akukan tra#"rsa$ su%&ohon kiri

%) *unjungi sim&u$ akar

c) 5akukan tra#"rsa$ su%&ohon kanan

!) Tra#"rsa$ Post0ord"r/ di$akukan %"rturut0turut ,

a) 5akukan tra#"rsa$ su%&ohon kiri

%) 5akukan tra#"rsa$ su%&ohon kanan

c) *unjungi sim&u$ akar

+ontoh ,

F :ntai yang dihasi$kan s"cara Pr"0ord"r

F6;A+@

D G

' E

A


8/10


9/10

F :ntai yang dihasi$kan s"cara In0ord"r

A;+6@F

D G

' E

A

F :ntai yang dihasi$kan s"cara Post0ord"r

A+;@6F

D G

' E

A


10/10

tugas algoritma pengolahan paralel

Documents