Pertemua 9
STRUKTUR POHON &
KUNJUNGAN POHON BINER
STRUKTUR POHON &
KUNJUNGAN POHON BINER
didefinisikan sebagai data yang terorganisir dari suatu
item informasi cabang yang saling terkait
Istilah – istilah Dalam Pohon
1. Predesesor
Node yang berada diatas node tertentu.
(contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu.
Istilah – istilah Dalam Pohon
(contoh : E dan F merupakan succesor dari B)
3. Ancestor
Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama.
(contoh : A dan B merupakan ancestor dari F)
4. Descendant
Seluruh node yang terletak sesudah node tertentu
dan terletak pada jalur yang sama.
(contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level diatas satu node
(contoh : B merupakan parent dari F)
6. Child
Succesor satu level dibawah satu node
(contoh : F merupakan child dari B)
7. Sibling
Node yang memiliki parent yang sama dengan satu
node (contoh : E dan F adalah sibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta
descendant-nya (contoh : Subtree B, E, F dan
Subtree D, G, H)
9. Size
Banyaknya node dalam suatu tree (contoh : gambar
tree diatas memiliki size = 8)
10. Height
Banyaknya tingkat/level dalam suatu tree (contoh :
gambar tree diatas memiliki height = 2) karena
program C++ diawali dari index ke-0
11. Root (Akar)
Node khusus dalam tree yang tidak memiliki
predesesor (Contoh : A)
12. Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun
(contoh : Node E,F,C,G,H)
13. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node
(contoh : Node A memiliki derajat 3, node B memiliki
derajat 2)
POHON BINAR (BINARY TREE)
Struktur ini biasanya digunakan untuk menyajikan data
yang mengandung hubungan hirarkial antara elemenelemennya.
Bentuk Pohon Berakar yang lebih mudah dikelola dalam
komputer adalah Pohon Biner (Binary Tree) yang lebih
dikenal sebagai Pohon Umum (General Tree) yang dapat
didefinisikan sebagai kumpulan simpul yang mungkin
kosong atau mempunyai akar dan dua Subpohon yang
saling terpisah yang disebut dengan Subpohon Kiri /
cabang kiri (Left Subtree) dan Subpohon Kanan / cabang
kanan (Right Subtree).
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap Simpul paling banyak hanya memiliki dua buah
anak
2. Derajat Tertinggi dari setiap Simpul adalah dua.
3. Dibedakan antara Cabang Kiri dan Cabang Kanan.
4. Dimungkinkan tidak mempunyai Simpul
Berikut ini diberikan contoh gambar Pohon Binar (Binary
Tree) dengan Cabang Kiri dan Cabang Kanan.
ISTILAH PADA POHON BINER
• Pohon Biner Penuh
(Full Binary Tree)
Semua simpul (kecuali daun)
memiliki 2 anak dan tiap cabang
memiliki panjang ruas yang sama
• Pohon Biner Lengkap
(Complete Binary Tree)
Hampir sama dengan Pohon Biner
Penuh, semua simpul (kecuali
daun) memiliki 2 anak tetapi tiap
cabang memiliki panjang ruas
berbeda
• Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi
informasinya berbeda
• Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang
sama
• Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu
anak / turunan kecuali daun
Penyajian Pohon Binar
(Binary Tree)
• Tree dapat dibuat dengan menggunakan linked list
secara rekursif.
• Linked list yang digunakan adalah double linked list non
circular
• Data yang pertama kali masuk akan menjadi node root.
• Data yang lebih kecil dari data node root akan masuk
dan menempati node kiri dari node root, sedangkan jika
lebih besar dari data node root, akan masuk dan
menempati node di sebelah kanan node root.
Bila diberikan untai HAKJCBL, maka proses untuk dapat
membentuk pohon biner dari untai diatas adalah :
1. Karakter pertama ‘H’ ditempatkan sebagai akar (root)
2. Karakter ‘A’,karena lebih kecil dari ‘H’, maka akan
menempati cabang kiri.
3. Karakter ‘K’, karena lebih besar dari ‘H’, maka akan
menempati cabang kanan.
4. Karakter ‘J’, lebih besar dari ‘H’ dan kecil dari ‘K’, maka
menempati cabang kiri ‘K’.
KUNJUNGAN
PADA POHON BINER
1. Kunjungan Secara PreOrder (Dept First Order)
a. cetak isi simpul yang di kunjungi (Simpul Akar)
b. kunjungi cabang kiri
c. kunjungi cabang kanan
2. Kunjungan Secara Inorder (Symetric Order)
a. kunjungi cabang kiri
b. cetak isi simpul yang di kunjungi (Simpul Akar)
c. kunjungi cabang kanan
3. Kunjungan Secara PostOrder
a. kunjungi cabang kiri
b. kunjungi cabang kanan
c. cetak isi simpul yang di kunjungi (Simpul Akar)
Cabang Kiri dilakukan terlebih dahulu, baru kemudian
kunjungan ke Cabang Kanan. Dengan orientasi
semacam ini, Ketiga kunjungan diatas disebut dengan
Left To Right Oriented (LRO).
Jika kunjungan ke Cabang Kanan dilakukan lebih
dahulu baru kemudian kunjungan ke Cabang Kiri, maka
Orientasi semacam ini disebut Right To Left Oriented
(RLO).
Kunjungan LevelOrder
Selain kunjungan yang dijelaskan diatas, masih ada
satu macam kunjungan masih ada satu macam
kunjungan lagi yaitu kunjungan LevelOrder.
Kunjungan dimulai dari simpul yang ada pada tingkat
1 (Akar), diteruskan pada simpul di tingkat 2, tingkat 3
dan seterusnya.
Secara singkat kunjungan Level Order ini dapat dijelaskan
sebagai berikut.
1. Dimulai dengan memasukkan Akar kedalam antrean.
2. Kemudian mengeluarkan Akar tersebut keluar dari
antrean.
Pada saat Akar tersebut dikeluarkan dari antrean, cabang
kiri dan cabang kanan secara berturut-turut dimasukkan
dalam antrean.
Dengan kata lain jika suatu elemen dikeluarkan dari
antrean, maka cabang kiri dan kanan dari elemen yang
baru saja dikeluarkan dimasukkan kedalam antrean.
APLIKASI POHON BINER
NOTASI PREFIX, INFIX DAN POSTFIX
Pada bagian ini akan dibahas tentang bagaimana
menyusun sebuah Pohon Binar yang apabila dikunjungi
secara PreOrder akan menghasilkan Notasi Prefix,
kunjungan secara InOrder menghasilkan Notasi Infix, dan
kunjungan PostOrder menghasilkan Notasi Postfix.
GRAPH dan
MATRIK PENYAJIAN GRAPH
1. Himpunan V yang elemennya disebut simpul (Vertex
atau Point atau Node atau Titik)
2. Himpunan E yang merupakan pasangan tak urut dari
simpul. Anggotanya disebut Ruas (Edge atau rusuk
atau sisi)
Graph seperti dimaksud diatas, ditulis sebagai G(E,V).
Suatu Graph yang tidak mengandung ruas sejajar maupun
self-loop, sering disebut juga sebagai Graph sederhana
atau simple Graph.
Suatu Graph G’(E’,V’) disebut Sub Graph dari G(E,V), bila E’
himpunan bagian dari E dan V’ himpunan bagian dari V.
Jika E’ mengandung semua ruas dari E yang titik ujungnya
di V’, maka G’ disebut Subgraph yang direntang oleh V’
(Spanning Subgraph).
GRAPH BERLABEL
Graph G disebut berlabel jika ruas dan atau simpulnya
dikaitkan dengan suatu besaran tertentu. Khususnya jika
setiap Ruas e dari G dikaitkan dengan suatu bilangan
non negatif d(e), maka d(e) disebut bobot atau panjang
dari ruas e.
DERAJAT GRAPH
Derajat simpul V, ditulis d(v) adalah banyaknya ruas
yang menghubungi v. Karena setiap ruas dihitung dua
kali ketika menentukan derajat suatu Graph, maka :
Jumlah derajat semua simpul suatu Graph (derajat) =
dua kali banyaknya ruas Graph (Size) Atau dapat
dituliskan :
Derajat Graph = 2 x Size
Jika Derajat masing-masing simpul pada Graph berjumlah
Genap maka Graph tersebut disebut EULER Graph
KETERHUBUNGAN
Walk atau perjalanan dalam Graph G adalah barisan simpul
dan ruas berganti-ganti : V1,e1,V2,e2,......., e n-1, Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis
lebih singkat dengan hanya menulis deretan ruas :
e1,e2, ...., en-1 atau deretan simpul : V1, V2,....., Vn-1, Vn
dimana : V1 = simpul awal
Vn = simpul akhir.
Walk disebut tertutup bila V1 = Vn
1. Walk disebut tertutup, yang menghubungkan V1 dan
Vn yaitu setiap ruas menghubungkan simpul awal dan akhir
2. Trail adalah walk dengan semua ruas dalam barisan adalah berbeda
3. Path atau jalur adalah walk yang semua simpul dalam barisan adalah berbeda.
Graph merupakan Walk Terbuka, karena tidak ada ruas
yang menghubungkan Simpul U dan T.
Merupakan suatu Path atau Trail terbuka dengan
derajat setiap simpulnya = 2, kecuali simpul awal U dan
simpul akhir T berderajat = 1.
· Barisan ruas a,b,c,d,b,c,g,h adalah Walk bukan Trail
(karena ruas b dua kali muncul).
· Barisan simpul A, B, E, F bukan Walk (karena tdk
ada ruas yang menghubungkan simpul B ke F).
· Barisan simpul A, B, C, D, E, C, F adalah Trail
bukan Jalur/Path (karena c dua kali muncul)
· Barisan ruas a, d, g, k adalah Jalur/Path karena
menghubungkan A dengan F
· Ruas a, b, h, g, e, a, adalah Cycle.
Graph yang tidak mengandung Cycle disebut Acyclic.
Contoh dari Graph Acyclic adalah pohon atau Tree.
GRAPH TERARAH (DIRECTED GRAPH / DIGRAPH)
Graph terarah adalah Graph yang dapat menghubungkan
V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah : n ( n - 1)
Suatu Graph Berarah (Directed Graph) D terdiri atas 2
himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut,
yang disebut ruas berarah atau arkus.
Bila arkus suatu Graph Berarah menyatakan suatu bobot,
maka Graph Berarah tersebut dinamakan jaringan /
Network. Biasanya digunakan untuk menggambarkan
situasi dinamis.
Bila V’ himpunan bagian dari V serta A’ himpunan bagian
dari A, dengan titik ujung anggota A’ terletak di dalam V’,
maka dikatakan bahwa D’(V’,A’) adalah Graph bagian
(Subgraph) dari D(V,A).
Bila A’ mengandung semua arkus anggota A yang titik
ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’)
adalah Graph Bagian yang dibentuk atau direntang oleh V’.
MINIMUM SPANNING TREE
Merupakan Spanning Tree yang mempunyai Bobot dan
tidak mempunyai arah dengan hasil penjumlahan
bobotnya adalah minimum.
Langkah yang dilakukan untuk membentuk minimum
spanning tree adalah :
Bentuk kembali semua simpul tetapi tanpa ruas.
Gambar dan telusuri ruas dengan bobot paling kecil,
seterusnya (secara ascending) hingga semua simpul
terhubung
2. Breadth First Search (BFS).
Berbeda dengan cara BFS, dengan BFS penelusuran
akan diawasi dari Node-1, kemudian melebar pada
Adjacent Node dari Node-1 dan diteruskan pada
Node-2, Node- 3 dan seterusnya.
Tidak ada komentar:
Posting Komentar