ݺߣ

ݺߣShare a Scribd company logo

Eeeee

•Download as PPTX, PDF•
•
H
hasznud89
Convert to study materialsBETA

Transform any presentation into ready-made study material—select from outputs like summaries, definitions, and practice questions.

1 of 41
Download to read offline
Eeeee
Contoh pohon berakar
Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1). Pada pohon P di Gambar, banyak simpul adalah n = 8, dan banyak edge (n – 1) = 8 – 1 = 7
Mempunyai simpul khusus yang disebut “root,” yang merupakan simpul yang memiliki derajat keluar >= 0, dan derajat masuk = 0. Simpul P merupakan root pada pohon di Gambar di atas. Mempunyai simpul yang disebut sebagai “daun” atau “leaf,” yang merupakan simpul berderajat keluar 0, dan berderajat masuk = 1. Simpul-simpul R, S, V, W merupakan daun pada pohon di Gambar.
Setiap Simpul mempunyai tingkatan atau level, yang dimulai dari root yang levelnya = 0, sampai dengan level n pada daun paling bawah. Pada pohon P di Gambar : P berlevel 0 Q dan T berlevel 1 R, S dan U berlevel 2 V dan W berlevel 3 “Simpul yang mempunyai level sama disebut “bersaudara” atau “brother” atau “siblings”.
Pohon mempunyai ketinggian atau kedalaman atau “height,” yang merupakan level tertinggi + 1. Pohon di Gambar mempunyai ketinggian atau kedalaman 3+1 = 4. Pohon mempunyai berat atau bobot atau “weight,” yang merupakan banyaknya daun pada pohon. Pohon di Gambar mempunyai bobot = 4.
Simpul akar adalah simpul yang digambar pada bagian paling atas. Untuk mengambarkan suksesor kiri serta suksesor kanan, dibuat garis ke kiri bawah dan ke kanan bawah. Perhatikan pada Gambar tersebut bahwa B adalah suksesor kiri dari A, sedangkan C adalah suksesor kanan dari A.
Subpohon kiri dari A mengandung simpul-simpul B, D, E dan F, sedangkan subpohon kanannya mengandung simpul-simpul C, G, H, A, K dan L H Simpul J, B, C dan mempunyai 2 anak, simpul E dan J mempunyai satu anak. Sementara itu simpul-simpul D, F, G, L dan K tidak mempunyai satu anakpun. Simpul yang tidak mempunyai anak disebut “daun” atau “terminal.”
disebut “similar” jika mereka mempunyai bangun (susunan) yang sama.
menggambarkan dua pohon yang tidak saja similar tetapi juga sama persis antara satu dengan lainnya (baik susunan atau struktur pohon, maupun isi dari setiap simpulnya) yang disebut dengan salinan (copy / copies)
Contoh untuk terminologi Pada Gambar, K misalnya adalah keturunan kanan dari D, tetapi bukan keturunan dari F, E ataupun M. Simpul G adalah ayah dari K dan L. Di sini K dan L adalah bersaudara, masing-masing anak kiri dan kanan dari G. Selain terminologi hubungan keluarga di atas, terminologi dari teori graph juga banyak digunakan. Garis yang ditarik dari simpul N ke suksesor disebut ruas dan sederetan ruas yang berturutan disebut jalur atau path. Sebuah jalur yang berakhir pada daun (simpul terminal) disebut cabang.
Contoh untuk terminologi Sebagai contoh, pada gambar tersebut, garis AD, ataupun GL adalah contoh ruas. Sedangkan barisan ruas (AD, DG, GL) adalah jalur dari simpul A ke simpul L. Jalur ini sekaligus merupakan cabang, karena berakhir di Simpul terminal (daun) L. Jalur (AD, DG) bukan sebuah cabang. Setiap simpul dari pohon mempunyai nomor tingkat (level).
Contoh untuk terminologi Pohon Binar pada Gambar , simpul A mempunyai tingkat 0. Simpul-simpul D dan E berada pada generasi dengan tingkat 1. Generasi berikutnya terdiri atas simpulsimpul F, G dan M dengan tingkat 2. Generasi terakhir, diisi oleh simpul K dan simpul L dengan tingkat = 3.
Contoh untuk terminologi Pohon pada Gambar mempunyai ketinggian 4. Perhatikan bahwa cabang (AD, DG, GK) ataupun (AD, DG, GL) mengandung simpul dengan jumlah maksimum, yakni = 4. Cabang yang lain mengandung simpul yang lebih sedikit, cabang (AE, EM) serta (AD, DF) misalnya hanya mengandung 3 simpul.
Jadi pohon binar lengkap dengan n simpul, Tn adalah tunggal (dalam hal ini dengan mengabaikan label simpul). Gambar berikut menggambarkan berturut-turut T4, T6, T11, dan T21.
Pohon binar yang akan dijadikan pohon-2 Simpul internal digambar sebagai lingkaran, sedangkan simpul eksternal sebagai bujur sangkar.
Sebuah pemakaian penting dari pohon-2 adalah untuk menyajikan suatu ekspresi aritmetik yang mengandung operasi binar. Di sini simpul eksternal menyajikan operand (variabel) sedangkan simpul internal menyajikan operator yang bekerja terhadap ke dua subpohonnya. Sebagai contoh adalah pohon2 pada Gambar berikut yang menyajikan ekspresi (a-b) / ((c+d) *e) Pohon binar (a-b) / ((c+d) *e)
Pohon binar yang mempunyai sifat bahwa ketinggian subpohon kiri dan subpohon kanan dari pohon tersebut berbeda paling banyak 1, disebut pohon ketinggian seimbang atau height balanced tree (HBT).
Untuk menentukan ketinggian minimum, jika diberikan banyaknya simpul N, dapat digunakan rumus : Sebagai contoh, untuk N = 80 Banyaknya simpul pohon binar merupakan ketinggian maksimum Pohon binar tersebut.
Contoh sebuah pohon binar Penggambaran skema penyajian LIST pada pohon binar
Eeeee
Diagram pohon binar dari Gambar Harga dari ROOT = 14 menunjukkan bahwa record nomor 14 dengan NAME = “Harris” adalah akar dari Pohon. LEFT[14] = 9 menunjukan bahwa Cohen (record nomor 9) adalah anak kiri dari Harris, dan RIGHT[14] = 7 menunjukkan bahwa Lewis adalah anak kanan dari Harris.
Penyajian sekuensial dari pohon binar
Contoh pohon umum Langkah pertama pembentukan pohon binar
Langkah pertama pembentukan pohon binar Langkah kedua pembentukan pohon binar
Pohon binar Pohon umum
operator operand Penyajian notasi (c+d)*e Penyajian notasi ((a+b) * (c/d) + (e^f)) / g
Traversal preorder Tiga kegiatan yang terdapat dalam traversal pohon binar adalah : (1) mengunjungi simpul akar (root) (2) melakukan traversal subpohon kiri dan (3) melakukan traversal subpohon kanan.
Ketiga traversal tersebut adalah : 1. Traversal pre-order, 2. in-order 3. post-order. Pada traversal pre-order dilakukan berturut-turut : (1) Kunjungi simpul akar (2) Lakukan traversal subpohon kiri secara pre-order (3) Lakukan traversal subpohon kanan secara pre-order
Gambar 1 Gambar 3 Gambar 2 Gambar 1 : c * d + e Gambar 2 : a / b + c * d + e / f ^ g Gambar 3 : M E B A D L P N V T Z
Untuk jelasnya perhatikan Gambar dengan arah dari traversal (dinyatakan dengan garis putus-putus)
1. 2. 3. Lakukan traversal subpohon kiri secara in-order Kunjungi simpul akar Lakukan traversal subpohon kanan secara inorder Kalau kita lakukan traversal in-order terhadap pohon pada Gambar maka diperoleh deretan urutan linear, berturut-turut : Gambar 1 : (c + d) * e Gambar 2 : ((a + b) * (c / d) + (e ^ f)) / g Gambar 3 : A B D E L M N P T V Z
Gambar 1
1. Lakukan traversal subpohon kiri secara post-order 2. Lakukan traversal subpohon kanan secara post-order 3. Kunjungi simpul akar. Traversal post-order terhadap Pohon pada Gambar menghasilkan: Gambar 1 : c + d * e Gambar 2 : a + b / c * d ^ e + f / g Gambar 3 : A D B L E N T Z V P M
Traversal post-order
Apakah kedua notasi tersebut akan memiliki struktur pohon yang sama ? Kita mulai dengan pohon binar (1). c + d * e; maka operasi yang akan dilakukan pertama kali adalah d * e (sesuai kaidah derajat operasi matematika). Bila d * e kita anggap sebagai f, maka notasi semula bisa disederhanakan menjadi c + f. c + f; struktur pohonnya adalah :
Kita ganti f di atas menjadi d * e, sehingga hasil akhirnya menjadi :
f * e akan digambarkan sebagai : Kita tahu bahwa f adalah (c + d) yang struktur pohonnya adalah :
Eeeee
 Contoh Ekspresi infix : ( K + L + M – N – E – F ) * G / H Prefix untuk Gambar adalah : K / L * M – N – E – F +G+H Postfix untuk Gambar adalah : K + L + M – N – E – F * G / H
Ekspresi infix ((A + B) * C + D) / (E + F * H), mempunyai pohon binar seperti terlihat pada Gambar.

More Related Content

Eeeee

  • 3. Jika pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1). Pada pohon P di Gambar, banyak simpul adalah n = 8, dan banyak edge (n – 1) = 8 – 1 = 7
  • 4. Mempunyai simpul khusus yang disebut “root,” yang merupakan simpul yang memiliki derajat keluar >= 0, dan derajat masuk = 0. Simpul P merupakan root pada pohon di Gambar di atas. Mempunyai simpul yang disebut sebagai “daun” atau “leaf,” yang merupakan simpul berderajat keluar 0, dan berderajat masuk = 1. Simpul-simpul R, S, V, W merupakan daun pada pohon di Gambar.
  • 5. Setiap Simpul mempunyai tingkatan atau level, yang dimulai dari root yang levelnya = 0, sampai dengan level n pada daun paling bawah. Pada pohon P di Gambar : P berlevel 0 Q dan T berlevel 1 R, S dan U berlevel 2 V dan W berlevel 3 “Simpul yang mempunyai level sama disebut “bersaudara” atau “brother” atau “siblings”.
  • 6. Pohon mempunyai ketinggian atau kedalaman atau “height,” yang merupakan level tertinggi + 1. Pohon di Gambar mempunyai ketinggian atau kedalaman 3+1 = 4. Pohon mempunyai berat atau bobot atau “weight,” yang merupakan banyaknya daun pada pohon. Pohon di Gambar mempunyai bobot = 4.
  • 7. Simpul akar adalah simpul yang digambar pada bagian paling atas. Untuk mengambarkan suksesor kiri serta suksesor kanan, dibuat garis ke kiri bawah dan ke kanan bawah. Perhatikan pada Gambar tersebut bahwa B adalah suksesor kiri dari A, sedangkan C adalah suksesor kanan dari A.
  • 8. Subpohon kiri dari A mengandung simpul-simpul B, D, E dan F, sedangkan subpohon kanannya mengandung simpul-simpul C, G, H, A, K dan L H Simpul J, B, C dan mempunyai 2 anak, simpul E dan J mempunyai satu anak. Sementara itu simpul-simpul D, F, G, L dan K tidak mempunyai satu anakpun. Simpul yang tidak mempunyai anak disebut “daun” atau “terminal.”
  • 9. disebut “similar” jika mereka mempunyai bangun (susunan) yang sama.
  • 10. menggambarkan dua pohon yang tidak saja similar tetapi juga sama persis antara satu dengan lainnya (baik susunan atau struktur pohon, maupun isi dari setiap simpulnya) yang disebut dengan salinan (copy / copies)
  • 11. Contoh untuk terminologi Pada Gambar, K misalnya adalah keturunan kanan dari D, tetapi bukan keturunan dari F, E ataupun M. Simpul G adalah ayah dari K dan L. Di sini K dan L adalah bersaudara, masing-masing anak kiri dan kanan dari G. Selain terminologi hubungan keluarga di atas, terminologi dari teori graph juga banyak digunakan. Garis yang ditarik dari simpul N ke suksesor disebut ruas dan sederetan ruas yang berturutan disebut jalur atau path. Sebuah jalur yang berakhir pada daun (simpul terminal) disebut cabang.
  • 12. Contoh untuk terminologi Sebagai contoh, pada gambar tersebut, garis AD, ataupun GL adalah contoh ruas. Sedangkan barisan ruas (AD, DG, GL) adalah jalur dari simpul A ke simpul L. Jalur ini sekaligus merupakan cabang, karena berakhir di Simpul terminal (daun) L. Jalur (AD, DG) bukan sebuah cabang. Setiap simpul dari pohon mempunyai nomor tingkat (level).
  • 13. Contoh untuk terminologi Pohon Binar pada Gambar , simpul A mempunyai tingkat 0. Simpul-simpul D dan E berada pada generasi dengan tingkat 1. Generasi berikutnya terdiri atas simpulsimpul F, G dan M dengan tingkat 2. Generasi terakhir, diisi oleh simpul K dan simpul L dengan tingkat = 3.
  • 14. Contoh untuk terminologi Pohon pada Gambar mempunyai ketinggian 4. Perhatikan bahwa cabang (AD, DG, GK) ataupun (AD, DG, GL) mengandung simpul dengan jumlah maksimum, yakni = 4. Cabang yang lain mengandung simpul yang lebih sedikit, cabang (AE, EM) serta (AD, DF) misalnya hanya mengandung 3 simpul.
  • 15. Jadi pohon binar lengkap dengan n simpul, Tn adalah tunggal (dalam hal ini dengan mengabaikan label simpul). Gambar berikut menggambarkan berturut-turut T4, T6, T11, dan T21.
  • 16. Pohon binar yang akan dijadikan pohon-2 Simpul internal digambar sebagai lingkaran, sedangkan simpul eksternal sebagai bujur sangkar.
  • 17. Sebuah pemakaian penting dari pohon-2 adalah untuk menyajikan suatu ekspresi aritmetik yang mengandung operasi binar. Di sini simpul eksternal menyajikan operand (variabel) sedangkan simpul internal menyajikan operator yang bekerja terhadap ke dua subpohonnya. Sebagai contoh adalah pohon2 pada Gambar berikut yang menyajikan ekspresi (a-b) / ((c+d) *e) Pohon binar (a-b) / ((c+d) *e)
  • 18. Pohon binar yang mempunyai sifat bahwa ketinggian subpohon kiri dan subpohon kanan dari pohon tersebut berbeda paling banyak 1, disebut pohon ketinggian seimbang atau height balanced tree (HBT).
  • 19. Untuk menentukan ketinggian minimum, jika diberikan banyaknya simpul N, dapat digunakan rumus : Sebagai contoh, untuk N = 80 Banyaknya simpul pohon binar merupakan ketinggian maksimum Pohon binar tersebut.
  • 20. Contoh sebuah pohon binar Penggambaran skema penyajian LIST pada pohon binar
  • 22. Diagram pohon binar dari Gambar Harga dari ROOT = 14 menunjukkan bahwa record nomor 14 dengan NAME = “Harris” adalah akar dari Pohon. LEFT[14] = 9 menunjukan bahwa Cohen (record nomor 9) adalah anak kiri dari Harris, dan RIGHT[14] = 7 menunjukkan bahwa Lewis adalah anak kanan dari Harris.
  • 24. Contoh pohon umum Langkah pertama pembentukan pohon binar
  • 25. Langkah pertama pembentukan pohon binar Langkah kedua pembentukan pohon binar
  • 27. operator operand Penyajian notasi (c+d)*e Penyajian notasi ((a+b) * (c/d) + (e^f)) / g
  • 28. Traversal preorder Tiga kegiatan yang terdapat dalam traversal pohon binar adalah : (1) mengunjungi simpul akar (root) (2) melakukan traversal subpohon kiri dan (3) melakukan traversal subpohon kanan.
  • 29. Ketiga traversal tersebut adalah : 1. Traversal pre-order, 2. in-order 3. post-order. Pada traversal pre-order dilakukan berturut-turut : (1) Kunjungi simpul akar (2) Lakukan traversal subpohon kiri secara pre-order (3) Lakukan traversal subpohon kanan secara pre-order
  • 30. Gambar 1 Gambar 3 Gambar 2 Gambar 1 : c * d + e Gambar 2 : a / b + c * d + e / f ^ g Gambar 3 : M E B A D L P N V T Z
  • 31. Untuk jelasnya perhatikan Gambar dengan arah dari traversal (dinyatakan dengan garis putus-putus)
  • 32. 1. 2. 3. Lakukan traversal subpohon kiri secara in-order Kunjungi simpul akar Lakukan traversal subpohon kanan secara inorder Kalau kita lakukan traversal in-order terhadap pohon pada Gambar maka diperoleh deretan urutan linear, berturut-turut : Gambar 1 : (c + d) * e Gambar 2 : ((a + b) * (c / d) + (e ^ f)) / g Gambar 3 : A B D E L M N P T V Z
  • 34. 1. Lakukan traversal subpohon kiri secara post-order 2. Lakukan traversal subpohon kanan secara post-order 3. Kunjungi simpul akar. Traversal post-order terhadap Pohon pada Gambar menghasilkan: Gambar 1 : c + d * e Gambar 2 : a + b / c * d ^ e + f / g Gambar 3 : A D B L E N T Z V P M
  • 36. Apakah kedua notasi tersebut akan memiliki struktur pohon yang sama ? Kita mulai dengan pohon binar (1). c + d * e; maka operasi yang akan dilakukan pertama kali adalah d * e (sesuai kaidah derajat operasi matematika). Bila d * e kita anggap sebagai f, maka notasi semula bisa disederhanakan menjadi c + f. c + f; struktur pohonnya adalah :
  • 37. Kita ganti f di atas menjadi d * e, sehingga hasil akhirnya menjadi :
  • 38. f * e akan digambarkan sebagai : Kita tahu bahwa f adalah (c + d) yang struktur pohonnya adalah :
  • 40.  Contoh Ekspresi infix : ( K + L + M – N – E – F ) * G / H Prefix untuk Gambar adalah : K / L * M – N – E – F +G+H Postfix untuk Gambar adalah : K + L + M – N – E – F * G / H
  • 41. Ekspresi infix ((A + B) * C + D) / (E + F * H), mempunyai pohon binar seperti terlihat pada Gambar.