sesi 1. pohon bagian iii

UPT SAM

Sesi 1.

POHON BAGIAN III

Mata Kuliah 1041102

MATEMATIKA DISKRIT

D4 Prodi Teknologi Rekayasa Perangkat Lunak

Fakultas Informatika dan Teknik Elektro

Yoli Agnesia, S.Pd, M.Si

Referensi

Buku :

1. Rinaldi Munir

2. Rosen

1041102_MATEMATIKA DISKRIT_WEEK 13_YAG 2

SUB TOPIK

1. Pohon n-ary

2. Pohon Biner

3. Penerapan Pohon Biner

4. Penelusuran (Traversal) Pohon Biner


Pohon n-ary

Defenisi:

Pohon berakar yang setiap simpul cabangnya mempunyai paling banyak n buahanak disebut pohon n-ary.

Pohon n-ary dikatakan teratur atau penuh (full) jika setiap simpul cabangnyamempunyai tepat n anak Contoh:


Gambar 1. Pohon 3-ary

Sumber Gambar 1. : http://belajar-barengan.blogspot.com/2012/11/struktur-data-pohon-binar-1.html

Pohon Biner

• Adalah pohon n-ary dengan n = 2.

• Setiap simpul di dalam pohon biner mempunyai paling banyak 2 buah anak.

• Dibedakan antara anak kiri (left child) dan anak kanan (right child)

• Karena ada perbedaan urutan anak, maka pohon biner adalah pohon terurut.

Contoh:


Jenis-jenis Pohon Biner

1. Pohon Biner Condong

2. Pohon Biner Penuh

3. Pohon Biner Seimbang


Penerapan Pohon Biner

1. Pohon Pencarian Biner

2. Pohon Keputusan

3. Kode Huffman

4. Pohon Ekspresi


Pohon Pencarian Biner

• Pohon pencarian biner sangat berguna untuk menyelesaikan masalah yang berkaitan dengan pencarian, penyisipan, dan penghapusan elemen.

• Simpul pada pohon pencarian biner berupa kunci/data itu sendiri (harus bersifat unik).

• Pohon pencarian biner adalah pohon biner yang setiap kuncinya diatur dalam suatu urutan tertentu, aturannya adalah:

a. Semua simpul pada upapohon kiri mempunyai nilai kunci lebih kecil dari kunci pada akar (R)

b. Semua simpul pada upapohon kanan mempunyai nilai kunci lebih besar dari kunci pada akar (R)



Contoh 1: Buatlah pohon pencarian biner dengan kata: mathematics, physics, geography, zoology, meteorology, geology, psychology, and chemistry (menggunakan urutan abjad)



Contoh 2:

Buatlah pohon pencarian biner dengan data berikut

Data:


Pohon Keputusan

Pohon keputusan digunakan untuk memodelkan persoalan yang terdiri dari serangkaiankeputusan yang mengarah ke solusi.

Tiap simpul dalam menyatakan keputusan, sedangkan daun menyatakan solusi.

Contoh: akan diurutkan tiga buah bilangan a, b, dan c

Gambar Pohon keputusan untuk mengurutkan 3 buah elemen


Kode Huffman

• Pohon Huffman adalah pohon yang digunakan untuk menemukankode untuk huruf pada pesan.

• Kode Huffman berguna untuk meminimumkan jumlah bit yang dibutuhkan dalam merepresentasikan pesan sehingga kita dapat memampatkan (compression) data.

• Kode untuk setiap huruf/karakter pada setiap pesan unik.

• Dalam membangun sebuah pohon huffman, setiap cabang (sisi) kiridiberi label 0 dan pada setiap cabang (sisi) kanan diberi label 1.


Kode Huffman

Contoh 1:

Temukan kode Huffman untuk setiapkarakter dengan peluang kemunculansebagai berikut:

A: 0.08,

B: 0.10,

C: 0.12,

D: 0.15,

E: 0.20,

F: 0.35.


Kode Huffman yang diperolehDari pohon Huffman adalahA : 111B : 110C : 011D : 010E : 10F : 00

Kode Huffman

Contoh 2: Berikut pohon Huffman untuk pesan ‘ABACCDA’


Kode Huffman untuk setiap karakter:A = 0B = 110C = 10D = 111

‘ABACCDA’ dapat ditulis dalam kodeHuffman sebagai berikut,

0110010101110

Pohon Ekspresi

Pohon ekspresi ialah pohon biner dengan daun menyatakan operand dan simpul dalam (termasuk akar) menyatakan operator.

Contoh:

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


Pohon Ekspresi

Pohon ekspresi digunakan untuk mengevaluasi ekspresi yang ditulisdalam notasi :

1. Prefix : operator mendahului dua buah operandnya

2. Infix : operator berada di antara dua buah operand

3. Postfix : kedua operand mendahului operatornya

Contoh:

*+ab/c+de dalam bentuk prefix

(a+b)*(c/(d+e)) dalam bentuk infix

ab+cde+/* dalam bentuk postfix


Penelusuran (Traversal) Pohon Biner

• Operasi dasar yang sering dilakukan pada pohon biner ialah mengunjungi(traversal) setiap simpul tepat satu kali.

• Proses yang dilakukan terhadap simpul yang dikunjungi misalnya mencetakinformasi yang disimpan di dalam simpul, memanipulasi nilai dan lain sebagainya

• Misal R adalah akar, T1 adalah upapohon kiri dan T2 adalah upapohon kanan.

Ada 3 skema mengunjungi simpul-simpul di dalam pohon biner:

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



Contoh Traversal Preorder:

Temukan lintasan preorder daripohon biner berikut ini,



2. Inorder : T1, R, T2

- kunjungi T1 secara inorder

- kunjungi R

- kunjungi T2 secara inorder



Contoh Traversal Inorder:

Temukan lintasan inorder daripohon biner T berikut ini,



2. Postorder : T1, R, T2

- kunjungi T1 secara postorder

- kunjungi T2 secara postorder

- kunjungi R



Contoh Traversal Preorder:

Temukan lintasan preorder daripohon biner berikut ini,



Notasi/ekspresi (lintasan) hasil traversal pohon biner disebut juga dengan:

1. Traversal preorder disebut prefix

2. Traversal inorder disebut infix

3. Traversal postorder disebut postfix




Contoh: temukan lintasan dari masing-masing traversal dari pohon biner berikut,

THANK YOU1041102_MATEMATIKA DISKRIT_WEEK 13_YAG 25

sesi 1. pohon bagian iii

Documents