Panjang Lintasan [PDF]

Citation preview

PANJANG LINTASAN DAN ALGORITMA HUFFMAN’S



Struktur Data



PENDAHULUAN Panjang Lintasan Luar (LE) adalah jumlah Panjang lintasan dari akar sampai ke semua simpul luar (daun)



Panjang Lintasan Dalam (LI) adalah jumlah panjang lintasan dari akar sampai kesemua simpul dalam Panjang Lintasan Luar Berbobot (P) adalah jumlah panjang lintasan dari akar sampai ke semua simpul luar (daun) dikalikan dengan bobot masing-masing daun P =  (bobot masing-masing daun * level daun tersebut)



KRONOLOGI Level 0



Level 1



Level 2



Keterangan : NE NI LE LI P



= Jumlah Simpul luar; = Jumlah Simpul dalam; = Panjang Lintasan NE; = Panjang Lintasan NI; = Panjang lintasan luar berbobot



Level 3



KRONOLOGI Level 0



Level 1



Level 2



Keterangan : NE NI LE LI P



= 6; = 5; = 2 + 2+ 3 + 3 + 3 + 3 = 16; = o + 1 + 1 + 2 + 2 = 6; = Berlaku bila NE memiliki bobot



Level 3



PANJANG LINTASAN LUAR BERBOBOT (P) Level 0



Level 1 2



2



4



Level 2 2 Sehingga Nilai P adalah = 2.2 + 2.2 + 2.4 + 3.2 + 3.1 =4+4+8+6+3 = 8 +14 + 3 = 25



1



Level 3



TREE DENGAN PANJANG LINTASAN LUAR BERBOBOT (P) MINIMUM Untuk membentuk 2-Tree dengan P minimum dapat dilakukan dengan menerapkan Algoritma HUFFMAN Algoritma Huffman menggunakan struktur pohon dalam prosesnya. Algoritma HUFFMAN merupakan salah satu metode paling lama dan paling terkenal dalam kompresi teks. Metode ini adalah suatu teknik kompresi data secara statistik yang bekerja dengan mereduksi panjang kode rata-rata dan menghasilkan kode prefiks yang digunakan untuk merepresentasikan simbol-simbol dari suatu jenis huruf.



ALGORITMA HUFFMAN Digunakan untuk membentuk 2-tree dengan Panjang lintasan luar berbobotnya minimum, dengan langkahlangkah sebagai berikut : 1. Pilih 2 daun (child) atau akar (parent) dengan nilai terkecil 2. Padukan kedua daun atau akar tersebut menjadi sebuah sub tree dengan nilai akar (parent) hasil penjumlahan kedua daun atau akar tersebur 3. Ulangi langkah ke 1 sampai terbentuk sebuah 2-tree yang utuh



ALGORITMA HUFFMAN’S Berdasarkan data berikut, bentuklah 2-tree sehingga P-nya minimum : Data



A



B



C



D



Bobot



5



4



2



3



Langkahnya sebagai berikut



a. menentukan data dengan bobot terendah 1 dan ke dua (data C [2] dan data D [3]), jadikan dalam bentuk tree dengan Root adalah jumlah dari ke 2 data terendah Note : data dengan bobot terendah, diletakkan sebagai anak kiri



C



D



2



3



5 C



D



2



3



b. Menentukan data dengan bobot terendah berikutnya, dan menjumlahkannya dengan tree sebelumnya B



9



4 5



B 4 C



D



2



3



c. Menjumlahkan dengan data terakhir 14



Level 0



A



5



9



A



Level 1



5



5



B



Level 2



4



Maka Nilai P = 1.5 + 2.4 + 3.2 + 3.3 =5+8+6+9 = 13 + 15 = 28



C



D



2



3



Level 3



CONTOH KASUS Berdasarkan data berikut, bentuklah 2-tree sehingga P-nya minimum : Data



A



B



C



D



E



Bobot



3



3



1



2



4



Tentukan : a. Gambarkan Tree-nya b. Nilai P c. Nilai NI, NE, LI dan LE