Matematika diskrit

Penerapan Pohon Biner

Kadek Dwinda Yudha Pratamajackprudencent@gmail.com

Kadek Dwinda Yudha Pratama VI-C-1215051015

JURUSAN PENDIDIKAN TEKNIK INFORMATIKAFAKULTAS TEKNIK DAN KEJURUAN

UNIVERSITAS PENDIDIKAN GANESHA2015

MATEMATIKA DISKRIT

Matematika Diskrit | Teori Graf [Pohon]

Pohon Biner Pohon biner merupakan kasus khusus pohon m-ary jika m = 2. Pohon biner adalah pohon

yang setiap simpul cabangnya mempunyai maksimum dua buah anak, anak dengan arah kiri

disebut anak kiri (left child) dan anak kanan (right child).

• Left subtree (sub pohon kiri) adalah :

Pohon yang akarnya adalah left child (anak kiri)

• Right subtree (sub pohon kanan) adalah :

Pohon yang akarnya adalah right child (anak kanan)

• Skewed tree (pohon condong) adalah :

Pohon yang semua simpulnya terletak di bagian kiri saja atau bagian kanan

saja

• Skew left (pohon condong kiri) adalah :

Pohon yang condong ke kiri

• Skew right (pohon condong kanan) adalah :

Pohon yang condong ke kanan

• Full binary tree (pohon biner penuh) adalah :

Pohon biner yang setiap simpulnya mempunyai tepat 2 buah child (anak), kiri

dan kanan, kecuali simpul pada level bawah

Adapun beberapa contoh pohon biner adalah sebagai berikut :

`

1

2 3

4

1

2

3

4

1

2

3

4

[ A ]

Pohon Biner[ B ]

Pohon Biner Condong Kiri[ C ]

Pohon Biner Condong Kanan

MATEMATIKA DISKRIT

Penerapan Pohon BinerAdapun penerapan dari pohon biner dibagi menjadi beberapa cara yaitu :

Pohon Keputusan

Pohon dapat digunakan untuk memodelkan masalah dengan berbagai tahapan keputusan

yang memunculkan sebuah solusi. Sebagai contoh, dalam penggunaan Binary Search

Tree, kita dapat menggunakan urutan kemunculan elemen sebagai perbandingan apakah

kita sudah menemukan elemen yang kita cari atau kita harus bergerak ke upapohon kiri

atau upapohon kanan. Sebuah pohon berakar yang simpul dalamnya menentukan sebuah

keputusan , dengan setiap upapohonnya adalah kemungkinan dari segala keputusan,

disebut sebagai pohon keputusan. Pohon keputusan biner adalah salah satu dari contoh

pohon keputusan. Pohon keputusan biner sangat tepat untuk diterapkan pada

persoalan yang banyak berkaitan dengan “ya” dan “tidak” karena setiap simpul memiliki

maksimal jumlah anak 2.

Contoh :

Kita akan membuat pohon keputusan dengan petunjuk “ya” atau “tidak” dengan kondisi

bahawa kita memiliki ciri – ciri dari tokoh yang bersangkutan. Dengan ciri – ciri tokoh

tersebut yang akan menjadi simpul – simpul dari pohon keputusan sehingga dengan

membandingkan ciri – ciri tokoh tersebut akan meriujung pada tokoh yang diingikan.

Berikut adalah contoh 8 (dealapan) tokoh beserta ciri – ciri :

Soeharto : Laki – laki, Presiden, Indonesia

John Kennedy : Laki – laki, Presiden, Bukan Indonesia

Erwin Gutawa : Laki – laki, Bukan Presiden, Musisi

Andik Vermansyah : Laki – laki, Bukan Presiden, Bukan Musisi

Chealse Islan : Bukan Laki – laki, Aktris, Masih Hidup

Shasya Yunisha : Bukan Laki – laki, Aktris, Tidak Masih Hidup

Yayuk Basuki : Bukan Laki – laki, Bukan Aktris, Atlit

Krisdayanti : Bukan Laki – laki, Bukan Aktris, Bukan Atlit

`

MATEMATIKA DISKRIT

Pohon Keputusan untuk Contoh diatas

= Ya

= Tidak

Kode Awalan (Prefix)

Kode Prefix merupakan himpunan kode (misalnya kode biner) sedemikian hingga tidak

ada anggota kumpulan yang merupakan awalan dari anggota yang lain. Pohon prefix

mempunyai pohon biner yang bersesuaian dimana setiap sisi diberi label 0 atau 1, semua

sisi kiri diberi label 0 saja (atau 1 saja) sedangkan sisi kanan diberi label 1 saja (atau 0

saja). Barisan sisi-sisi yang dilalui oleh lintasan dari akar ke daun menyatakan kode

awalan (ditulis di daun). Kode prefix berfungsi untuk :

1. Mengirim pesan pada komunikasi data yang mana setiap karakter di dalam pesan

direpresentasikan dengan barisan angka 0 dan 1.

2. Pembentukan kode Huffman dalam pemampatan data (data compression)

`

Laki – Laki ?

Aktris ? Presiden ?

Hidup ?

Krisdayanti Yayuk Basuki Shasya Yunisha Chealse Islan John Kennedy SoekarnoAndik Vermansyah Erwin Gutawa

Atlit ? Indonesia ?Musisi?

001000

1110011

101

10

0

0

Pohon biner dari kode prefiks (000, 001, 01, 10, 11)

MATEMATIKA DISKRIT

Penerapan Kode Prefix pada Pohon Biner berhubungan dengan Pembuatan Pohon Biner

Kode Huffman, jadi contoh penerapan akan diberikan bersama dengan penerapan pohon

kode huffman.

Kode Huffman

Data Kompressi sangat diperlukan dalam kehidupan sehari – hari, terutama dalam bidang

Teknologi Informasi, kompresi data baik data berupa file gambar video dan lain – lain.

Seperti yang disampaikan sebelumnya pada kode prefix bahwa kode huffman digunakan

untuk kompresi data. Kompresi data dilakukan dengan mengkodekan setiap karakter di

dalam pesan atau di dalam arsip dikodekan dengan kode yang lebih pendek. Sistem kode

yang banyak digunakan adalah kode ASCII (setiap karakter dikodekan dalam 8 bit

biner). Ada beberapa tahapan dalam melakukan kompresi menggunakan kode Huffman

dengan membentuk pohon biner (dinamakan dengan pohon Huffman) yaitu :

1. Pilih 2 simbol dengan peluang (probability) paling kecil sebagai child kemudian

kedua simbol tersebut dikombinasikan sebagai parent peluang penjumlahan dari

kedua simbol tersebut

2. Pilih 2 simbol berikutnya termasuk simbol baru yang mempunyai peluang kecil

sebagai child kemudian kedua simbol tersebut dikombinasikan sebagai parent

peluang penjumlahan dari kedua simbol tersebut

3. Prosedur yang sama dilakukan pada 2 simbol berikutnya yang mempunyai peluang

terkecil sebagai child kemudian kedua simbol tersebut dikombinasikan sebagai

parent peluang penjumlahan dari kedua simbol tersebut

Contoh :

Dalam kasus ini kita akan membuat pohon huffman dengan kata TELKOMSEL

Tabel Probabilitas TELKOMSEL

HURUF

FREKUENSI

K 1/9M 1/9O 1/9S 1/9T 1/9E 2/9L 2/9

`

MATEMATIKA DISKRIT

Pohon Huffman

Dalam penerapan pohon huffman diatas, maka kode prefix atau

awalan akan terbentuk seiring dengan pembentukan pohon huffman masing – masing daun

memiliki nilai 0 atau 1.

`

LETSOKM

ETSOKM

TSOKM

OKM

KM

SOKM

L

T

S

O

K M

E

0

1

1

1

1

1

1

0

0

0

0

0

Huruf

Kode Huffman

K 111110M 111111O 11110S 1110T 110E 10L 0