BAB I PENDAHULUAN. Struktur data non abstrak dikelompokkan dalam beberapa bagian yaitu : 1. Set 2. Array 3. Record 4. File 5. Pointer, dan lain-lain

Diktat : KBMI3305 - Struktur Data

Hal : 16

BAB I PENDAHULUAN I.1. PENGERTIAN Berbicara dengan struktur data maka perlu memperhatikan beberapa aspek seperti logika, algoritma dan kompleksitas program. Struktur data menjadi sangat penting dalam mendisain sebuah program yang efisien dengan akses yang sangat efektif. Sebuah program merupakan proses bentukan dari stuktur data dan algoritma. Data diorganisasi sedemikian rupa dengan cara yang berbeda-beda, baik menurut logika maupun model model matematika kemudian disusun menurut aturan-aturan yang benar yang disebut dengan struktur data. Data adalah fakta-fakta / angka-angka yang sudah terekam tetapi belum digunakan untuk suatu keperluan. Struktur adalah elemen-elemen pebentuk atau pengaturan hubungan antar elemen dalam suatu sistem. Model data dapat dipandang dengan 2 cara yaitu : 1. Struktur yang cukup menghubungkan data dalam dunia nyata 2. Struktur sederhana untuk dapat mengefektifkan proses data yang diperlukan. Struktur data dibagi atas 3 tingkatan struktur yaitu : 1. Defenisi fungsional 2. Referensi logika 3. Referensi fisik Nilai data (data value) adalah suatu data yang dipandang sebagai satu kesatuan tunggal (single entity) sedangkan tipe data adalah kombinasi antara himpunan nilai data (set of value) dan himpunan operasi terhadap nilai-nilai data tersebut. Struktur data abstrak dibagi menjadi beberapa bagian yaitu : 1. List linier (Linked list) 2. linked list banyak (Multi linked list) 3. Tumpukan (Stack) 4. Antrian (Queue) 5. Pohon (Tree) 6. Grafik (Graph) Struktur data non abstrak dikelompokkan dalam beberapa bagian yaitu : 1. Set 2. Array 3. Record 4. File 5. Pointer, dan lain-lain Tipe data abstrak (TDA) Dapat dipadang sebagai model matematika dan sekumpulan operasi yang didefenisikan terhadap suatu model.

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 17

Contoh : Himpunan bilangan bulat : { ...,-3,-2,-1,0,1,2,3, ... } operasi yang dapat dilakukan terhadap himpunan ini adalah gabungan, irisan, dan lain-lain. TDA dapat dibagi menjadi : 1. Generalisasi : proses membangkitkan tipe-tipe data dasar / primitif (real, integer, dan lainlain) seperti juga prosedur yang merupakan generalisasi dari operasi-operasi dasar, seperti : +, -, *, /, dan lain-lain 2. Enkapsulasi : Merupakan TDA yang melingkupi / menyelimuti tipe data, artinya defenisi jenis data dan operasi-operasi yang diperbolehkan dilokalisasi dalam satu bagian program. Tipe data dari sebuah variabel adalah kumpulan nilai tertentu yang dimuat oleh variabel tersebut. Misalnya tipe data boolean yang hanya bernilai true atau false dan tidak boleh yang lain.

I.2. KONSEP ARRAY Array merupakan struktur data yang paling sederhana, kesederhanaannya dapat dilihat dari pemberian notasi model linier (dimensi). Dalam array linier dengan jumlah data terbatas (finite) didefenisikan sebagai berikut : A1, A2, A3, ..., An atau dengan notasi dalam kurung : A(1), A(2), A(3), ..., A(n) atau dengan notasi dalam kurung siku : A[1], A[2], A[3], ... A[n]. Dilihat dari notasi-notasi di atas bahwa A adalah variabel operand dan 1, 2, 3, ... , n adalah indeks yang menyatakan sekuensi proses. Selain model notasi linier satu dimensi juga diperbolehkan untuk dua atau tiga dimensi misalnya, dengan dimensi 2 : A[1,1], A[1,2], ..., A[1,n], A[2,1], A[2,2], …, A[m,n] dan oleh karena itu array disebut juga dengan dense list (struktur data statis). Dimensi Array : 1. Array 1 dimensi : List dan vektor 2. Array 2 dimensi : tabel dan matriks 3. Array multidimensional : secara teoritis bahwa jumlah dimensi tidak terbatas akan tetapi hanya dibatasi oleh besarnya memory 4. Array-array special : − Array segitiga (triagular array) : ¾ Lower triangular array : array 2-dimensi berbentuk bujur sangkar (U1 = U2), dimana semua komponen di atas diagonal berisi 0 ¾ Upper triangular array : perbedaan lower triangular array adalah semua komponen di bawah diagonal yang berisi 0. Penyimpanan memerlukan lebih sedikit memory, karena angka 0 tidak perlu disimpan. Rumus AMF untuk triangular array adalah : Address (S[i,j] = C0 + C1 x (i x (i-1)) + C2 x j, dimana C0 = B, C1 = L/2 , C2 = L Jumlah elemen = (U x (U+100/2 dan Jumlah memory = L x jumlah elemen − Array jarang (Sparse Array) : Array yang kebanyakan komponennya mempunyai satu nilai yang sama, misalnya nilai 0, hanya sebagian kecil yang tidak sama dengan 0.

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 18

I.3. KONSEP LINKED LIST List dianalogikan sebagai daftar (record), kemudian beberapa daftar / record digabung atau dihubungkan sebagai rangkaian suatu proses yang disebut dengan link. Suatu entitas dimana record-recor yang termuatdi dalamnya dihubungkan (linked) menjadi satu proses bersama disebut linked list. Linked list untuk pertama kalinya dapat dikenali dan dihubungkan dengan suatu pointer head. Perhatikan diagram berikut dalam gambar 1.1 Contoh :

Record / list

Gambar 1.1. Bentuk list Pada gambar 1.1. ditunjukkan bahwa head akan merujuk (menyimpan alamat) record tersebut. Rangkaian linked list dikenali dengan head, listlist terkait dan tail Jenis-jenis linked list antara lain : 1. List dengan elemen terkahir menunjuk diri sendiri

2. List yang mencatat dari elemen pertama sampai terakhir

3. List circular

4. Double linked list head

head prev

tail

5. Binary list

head

tail

prev

head

6. Multiple linked list

Gambar 1.2. Jenis-jenis linked list

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 19

I.4. KONSEP TREE Tree (pohon) adalah struktur data yang menyatakan frekuensi data dengan relasi dalam suatu hirarki antara elemen-elemen data, induk relasi tersebut adalah root (akar) dan cabangcabang yang memiliki data disebut dengan leave dan leaf. Contoh : Record : mahasiswa {nim, nama, alamat{jalan, area{kota,kdpos}}, umur, jurusan, hobby} Perhatikan diagram berikut dalam gambar 1.3. Mahasiswa NIM

Nama

Alamat

Jalan

Umur

Jurusan

Hobby

Area Kota

kdpos

Gambar 1.3. Bentuk pohon

I.5. KONSEP STACK Stack (tumpukan) adalah struktur data (list linier) yang menganut paham LIFO (last in first out), dimana proses yang dapat dilakukan adalah sisip dan hapus data, dan selalu mengambil posisi di akhir tumpukan (top of stack) dengan bentuk penotasiannya dengan postfix. Operasi pada stack adalah PUSH (memasukkan data dalam stack) dan POP (mengambil data dari stack). Perhatikan diagram berikut dalam gambar 1.4.

Gambar 1.4. Bentuk Tumpukan

I.6. KONSEP QUEUE SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 20

Queue (antrian) adalah struktur data (list linier) yang menganut paham FIFO (first in first out) dimana operasi penghapusan dilakukan di depan (front) list dan operasi sisip dilakukan di belakang (rear) list. Perhatikan diagram berikut dalam gambar 1.5.

in

out

Gambar 1.5. Bentuk Antrian

1.7. KONSEP GRAPH Graph (grafik) merupakan bagian struktur data yang mengindikasikan adanya relasirelasi (many to many) yang beraturan dan tidak beraturan diantara pasangan elemen-elemen data baik untuk tipe yang sama atau berbeda dengan berbentuk network / jaringan. Contoh Grafik : Gambar 1.6. Bentuk salah satu graph

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 21

BAB II FUNGSI, TIPE DATA DAN NOTASI ALGORITMA Demi kelancaran pemahaman akan struktur data lebih lanjut maka perlu mengetahui bentuk-bentuk fungsi dan notasi yang sering digunakan baik dalam algoritma maupun program. II.1. FUNGSI DAN NOTASI MATEMATIKA FUNGSI FLOOR DAN CEILING Misalkan X adalah bilangan real, dimana X berada diantara 2 buah bilangan integer disebut dengan FLOOR dan CEILING. FLOOR X ( ⎣X⎦ ) adalah pembulatan nilai X ke bawah dan diambil desimal terbesar. CEILING X ( ⎡X⎤ ) adalah pembulatan nilai X ke atas dan diambil desimal terbesar. Contoh : ⎣3.14⎦ = 3 ⎡3.14⎤ = 4 ⎣8.5⎦ = 8 ⎡8.5⎤ = 9 FUNGSI SISA (MODULUS) Misalkan X adalah nilai integer dan M adalah positif integer maka nilainya adalah sisa pembagian. Bentuknya adalah X (mod) M. Contoh : 25 (mod) 7 = 4 25 (mod) 5 = 0 35 (mod) 11 = 2 FUNGSI INTEGER dan ABSOLUTE Misalkan X adalah integer, maka nilai integer X ditulis INT(X) dengan mengkonversi X ke dalam integer dan menghapus bagian fraksional bilangan. Contoh : int (3.14) = 3 int (8.5) = 8 int (7) = 7 abs |-15| = 15 abs |-3.33| = 3.33 abs|4.44| = 4.44 FUNGSI SUM (Σ) Proses berdasarkan sikuensi a1, a2, a3, ... , an maka a1 + a2 + a3 + ... + an maka bentuknya adalah : n

Sum (Σ) = Σ ai j=1

FUNGSI FAKTORIAL Misalkan bilangan integer positif dari satu sampai dengan n dinotasi dengan n ! maka bentuknya adalah n ! = 1 x 2 x 3 x ... x (n-2) x (n-1) x n. Contohnya : 5! = 5 * 4! 4 = 4 * 3! 3 = 3 * 2! 2 = 2 * 1! =2*1=2 3=3*2=6 4 = 4 * 6 = 24 5 ! = 5 * 24 = 120

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 22

FUNGSI PERMUTASI Jumlah pasangan berurutan suatu himpunan dari n buah objek dengan jumlah pasangan masing-masing adalah r buah besaran, dimana r ≤ n. Misalnya : {a, b, c} b (a,b) a

terdapat 6 buah pasangan n = 3 dan r = 2 maka rumus :

c (a,c) a (b,a) b

n! P (n, r) = (n –r) !

c (b,c) a (c,a) c b (c,b)

II.2. TIPE DATA Dalam mendisain sebuah program yang baik maka sangat penting memperhatikan jenis tipe data yang akan dipakai untuk menentukan efisiensi penggunaan memori. Jenis-jenis tipe data sebagai berikut : - Numeric integer (Int) - Numerik real (real, Float) - Charakter (Char) - String - Boolean (True, False) - Pointer - Ordinal (subset tipe data sederhana kecuali tipe data real dan tipe data yang didefenisi oleh user yaitu enumerate type dan subrange type) NUMERIK INTEGER Merupakan nilai bilangan bulat dalam bentuk decimal maupun hexadecimal. Perhatikan tabel 2.1. berikut : Tabel 2.1. Tipe data integer Tipe Ukuran memori (byte) Byte 1 Shortint 2 Integer 4 Word 8 Longint 10

Range nilai 0 ... 125 -128 ... 127 -32768 …32767 0 … 65535 -2147483648 … 2147483647

NUMERIK REAL Nilai konstanta numeric berkisar dari 1E-38 sampai dengan 1E + 38 dengan mantissa yang signifikan sampai dengan 11 digit. Nilai E menunjukkan 10 pangkat. Nilai konstanta numerik real menempati memori 6 byte. SINAR SINURAT, ST

STMIK BUDIDARMA


Tabel 2.2. Tipe data real Tipe Ukuran Memori (byte) Single 4 Double 8 Extended 10 Comp 16

Hal : 23

Range nilai

Signifikansi Digit 7–8 15 – 16 19 – 20 19 - 20

1.5 x 10E-45 … 3.4 x 10E38 5.0 x 10E-324 … 1.7 x 10E308 1.9 x 10E-4951 … 1.1 x 10E4932 -2E + 63 + 1 … 2E +63- 1

II.3. NOTASI ALGORITMA Notasi algoritma yang dipakai pada umumnya adalah : Assign ekspressi adalah = atau := atau ← Misalnya : untuk meng-assign suatu nilai terhadap suatu variabel X = 2 atau

X := 2 atau

X←2

Assign kondisi adalah == atau = Pembanding adalah case … of atau if … then … [else] …. Misalnya untuk membandingkan dua buah nilai butuh operator == atau = (tergantung bahasa pemrograman yang digunakan) dan dimuatkan ke dalam suatu pembanding atau perulangan suatu operasi dapat dilakukan dengan : If (a == b) then ekspressi

atau if (a ==b) then ekspressi1 else ekspressi 2

Case a of 1: ekspressi1 ; 2: ekspressi2; ...... end; Operator adalah + atau - atau / atau * Misalya : untuk mejumlahkan atau mengurangkan atau membagi bahkan untuk mengalikan dilakukan dengan : a*b

atau a / b

atau a + b

atau a-b

Perulangan adalah for … do atau while ... do atau do … while atau repeat … until () Relasi adalah ≥ atau > atau ≤ atau < atau <> atau .GE. atau .GT. atau .LE. atau .LT. atau .NE. dan lain-lain. Misalnya : untuk membandingkan dua buah nilai maka harus menggunakan operator kondisi atau looping for ( a < b) do ekspressi

atau while (a < b) do ekspressi

Repeat Ekspressi Until (kondisi)

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 24

BAB III ARRAY, RECORD, SET, POINTER II.1. ARRAY Merupakan gugus yang menggambarkan struktur yang mengalokasi alamat (storage) di memory untuk suatu operand dengan suatu indeks. Array dapat bertipe data sederhana ataupun tipe data enumerate. Perhatikan diagram berikut pada gambar 3.1. Tipe Array

Array

[

Tipe Indeks

]

of

Tipe

; Tipe indeks

Tipe Ordinal

Gambar 3.1. Diagram proses Array Pencapaian / akses data dibagi 2 : 1. Positional access Merupakan akses dilakukan berdasarkan nilai indeksnya, sedangkan 2. Associative access Merupakan akses berdasarkan nilai atau isi komponennya. Akses berdasarkan indeks adalah alamat komponen memory dapat dihitung berdasarkan komponen indeksnya. Akses berdasarkan indeks dibedakan : 1. Alamat (address) komponen dalam memory dapat dihitung berdasarkan nilai indeksnya 2. Untuk array dengan D dimensi, dibutuhkan D penjumlahan dan D perkalian 3. Kecepatan perhitungan tidak tergantung kepada banyaknya komponen, tetapi tergantung kepada besarnya dimensi. Parameter array adalah berdasarkan : 1. Base Address (B) Alamat (byte pertama) dari array yang diberikan pada saat binding time. Binding time adalah waktu dimana array diberikan pada suatu lokasi /address di memory, bisa pada saat compile, execute, dan lain-lain. 2. Component length (L) Panjangnya memory untuk menyimpan satu komponen. L tergantung dari tipe komponen dan bahasa pemrograman, misalnya pada Turbo Pascal 7.0 tipe integer mempunyai L=2, Turbo C 2.0 tipe integer L = 2, Visual C++ 5.0 tipe integer L = 4 3. Upper Bound (Ik) dan Lower bound (Uk) Ik adalah nilai indeks yang terkecil sedangkan Uk adalah nilai indeks yang terbesar. Contoh : int s[10]; maka Ik = 0 , Lk = 9 4. Dimension (D) Besarnya dimensi dari suatu array. Contoh : int S[10][20]; atau var S : array[1..10][1..20] of integer; maka D = 2 int S[9]; atau var S : array[1..9] of integer; maka D = 1

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 25

Sistem Operasi

Gambar 3.2. Konsep Array dalam memory ARRAY MAPPING FUNCTION (AMF) AMF merupakan suatu fungsi untuk memetakan nilai indeks ke alamat komponen. Fungsi Mapping / Pemetaan yaitu : 1. Row major order Merupakan cara penyimpanan array dalam bahasa pemrograman 2. Virtual origin atau virtual base nilai konstan C0 (lokas dari komponen dengan indeks 0) dalam AMF. Rumus dalam AMF : Address (S[I1][I2] … [Id]) = C0 + C1 x I1 + C2 x I2 + … + Cn x id ; dimana Cd = L Ct-1 = (Ut – It + 1) x Cd x Ct ; dan i
atau int S[5];

Jika diketahui : B = 500, L = 2 Maka I1 = 0, U1 = 4 C1 = L = 2 C0 = B + (C1 x I1) = 500 + (2 x 0) = 500 Catatan : dalam bahasa C bahwa indek selalu dimulai dari 0, maka C0 = B sedangkan dalam bahasa Pascal dideklarasikan sendiri oleh programmer-nya. jadi address dalam pemrograman bahasa C: SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 26

S[I] = C0 + C1 x I1 maka S[4] = 500 + (2 x 4) = 508 S[3] = 500 + (2 x 3) = 506 S[2] = 500 + (2 x 2) = 504 S[1] = 500 + (2 x 1) = 502 Besarnya memory yang dibutuhkan adalah : M = L x ( U1 – I1 + 1) = 2 x (5 – 0 + 1) = 10 byte Bila dideklarasikan suatu variabel dengan var x : array [1..n] of integer; maka implementasi array secara linier dalam memory adalah : X[1] X[2] X[3] X[4] … X[n]

?

?

?

?

?

?

Gambar 3.3. Bentuk array linier Contoh fragmen program dari /* Bahasa Pascal adalah : */ Uses CRT; Var x : array [1..7] of integer; i : byte; Begin For i := 1 to 7 do Readln(x[i]); For i := 1 to 7 do Writeln(x[i]); End.

/* Bahasa C/C++ adalah : */ #include ,stdio.h> int x[7], i; { for (i=0; i <= 7; i++) scanf(“%d”, &x[i]); for (i=0; i<=7;i++) printf(“%d\n”,x[i]); }

II.2. RECORD Data terstruktur yang mengumpulkan beberapa item data untuk masing-masing tipe data yang sama atau berbeda disebut field. Perhatikan diagram berikut pada gambar 3.3. Tipe Record

Tipe

Record Daftar field

Gambar 3.4. Diagram proses Record

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 27

Contoh fragmen program dari /* Bahasa Pascal adalah : */ Uses CRT Type Data = Record Nama :string; Umur : byte; End; Var x : data; Begin Readln(x.nama); Readln(x.umur); Writeln(x.nama, x.umur); End;

/* Bahasa C/C++ adalah : */ #include <stdio.h> struct data { char *nama; int umur; } data x; { scanf(“%s”, &x.nama); scanf(“%d”, &x.umur); printf(“%s\n”, x.nama); printf(“%d\n”, x.umur); }

Proses pembacaannya dapat digantikan dengan cara : Begin With x do begin Readln(nama, umur); end; end

III. SET Bagian struktur data yang mengatur objek-objek dalam set, dimana anggota-anggota set mempuyai tipe yang sam (base type) yaitu tipe ordinal (integer, boolean, cahr, skalar kecuali real). Perhatikan diagram berikut pada gambar 3.4. Tipe Set

Set

of

Tipe Ordinal

Gambar 3.5. Diagram proses Set Fragmen program dari Bahasa Pascal adalah : Contoh1 : Type huruf_hidup = set of (’a’, ’e’, ’o’, ’i’, ’u’); Var teks : string; Jlh, i : integer; Begin Readln(teks); Jlh := 0; For i:=1 to ord(teks[0]) do If teks[i] in huruf_hidup then Jlh := jlh + 1; Writeln (‘Jumlah huruf hidup : ‘, jlh); End.

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 28

Contoh 2 : { Menghasilkan huruf yang pernah dipakai dalam suatu kalmia } Type karakter = set of char; Var karset : karakter; i : byte; pakai, kalimat : string; Begin Karset := []; Write(‘Masukkan suatu kalimat : ‘); readln(kalimat); For i:=1 to length(kalimat) do If not ([kalimat[i]] <= karset) then Begin Karset := karset + kalimat[i]; Pakai := pakai + kalimat[i] + ’ ’ End; Writeln (‘Karakter-karakter yang digunakan : ‘, pakai); End.

III.4. POINTER Merupakan struktur data berupa variable dinamis yang tidak dapat dideklarasikan secara eksplisit seperti variabel statis dan tidak dapat langsung ditunjukkan oleh suatu pengenal (identifier). Pointer ini hanya dapat ditunjukkan oleh variable khusus yang berisi alamat memory yang digunakan oelh variable dinamis. Jadi variabel pointer hanya dapat dideklarasikan dengan tipe data pointer (simbol ↑ baca carat atau circumflex). Perhatikan contoh fragmen program berikut : Contoh 1 : Type kalimat : string; pointkal = ^kalimat; Var nama : pointkal; Begin Nama^ := ’Belajar struktur data’; Write(nama^); End. Contoh 2 : Type kar = ^catchar; Catchar = record Kode : string; Nama : string; Gaji : real; End; Var datakar : array [1..5] of kar; i : byte; Begin For i := 1 to 5 do Begin New (datakar[i]); SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 29

With datakar[i]^ do Begin Readln(kode); Readln(nama); Readln(gaji); End; End; For i := 1 to 5 do Begin With datakar[i]^ do Begin Writeln(i, kode, nama, gaji); End; End; End; Tugas : Buatlah program dari salah satu bahasa pemrograman untuk menginput beberapa data kemudian mengurutkan hasilnya secara menaik (ascending) atau menurun (descending).

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 30

BAB IV LINKED LIST Linked list merupakan struktur data dinamis, dimana list dianalogikan sebagai daftar / record yang berisi item data. Dalam list kita harus mengenali masing-masing elemen / node, misalnya : elemen1, elemen2, ...., elemenn. Elemen-elemen ini harus dihubungkan (link) dengan suatu pointer (penujuk) pada alamat-alamat tertentu. Berikut akan dijelaskan lebih dahulu deklarasi-deklarasi list. IV.1. STATEMENT NEW, DISPOSE DAN VARIABEL POINTER Statement NEW Digunakan untuk mengalokasi storage dalam node baru kemudian kita mereferensi masing-masing node baru yang menyimpan informasi tentang variabel pointer tersebut. Statement DISPOSE Digunakan untuk membebaskan list dari rangkaian linked list yang ada. Perhatikan diagram berikut pada gambar 4.1. Type Str1 = array [1..3] of char; Node = Record Kata : String; Next : ^node; End; Nodepointer = ^node; Sehingga operasi dapat dilakukan dengan : New (P) New (Q)

P ?

Dispose (P) { List P akan hilang }

?

Dispose (Q) { List Q akan hilang }

Q

Gambar 4.1. Operasi New dan Dispose Jika dimisalkan entry data adalah : P^.Kata =’Agus’ dan Q^.Kata = ’Budi’ maka bentuk listnya adalah sebagai berikut : P Agus Q Budi

Gambar 4.2. Operasi entri list

Perhatikan proses perpindahan ke list berikutnya dengan memisalkan bahwa : SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 31

P^.Next = 3 dan Q^.Next = 5 maka bentuk listnya sebagai berikut : P Agus

3

Budi

5

Q

Gambar 4.3. Operasi pointer next Sehingga bentuk linked list yang sebenarnya dapat dideskripsikan sebagai berikut : Head

Head 2

1

Agus

3

4

5

Budi

2

Gambar 4.4. Deskripsi linked list Misalkan statement

r:=q ; p:=q; q:=r

maka bentuk linked listnya adalah :

Q

P Agus

Budi

3

5

Sehingga : R

Agus

3

Budi

5

P Q

Gambar 4.5. Operasi pertukaran head list Bila gambar 4.5. dibubuhi operasi : Write(P^.Kata, Q^.Kata, R^.Kata) maka akan diperoleh hasilnya : BudiAgusAgus. IV.2. LINKED LIST (LINIER) Linked list (linier) merupakan deretan list-list yang terhubung dengan suatu head / start di depan. Perhatikan diagram berikut pada gambar 4.6. Head 1

2

?

?

3

?

Informasi tentang data (record data item)

4

5

?

?

Next pointer field = nil = null

Alamat node berikut (next pointer field)

Gambar 4.6. Linked list dengan 5 node

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 32

Bagaimana implementasi data dalam linked list dengan pointer masing-masing yang merujuk mulai dari list awal sampai dengan list terakhir. Perhatikan diagram berikut dalam gambar 4.7. Head 1

2

Agus P = Head

P^.Kata

P^.Next^.Kata

Cerry

Dedy

P^.Next^.Next^.Kata

P^.Next^.Next

P^.Next

4

3

Budi

P^.Next^.Next^.Next^.Kata P^.Next^.Next^.Next^.Next = nil

P^.Next^.Next^.Next

Gambar 4.7. Proses pointer dalam linked list

Dalam merepresentasi list-list dalam array dilakukan dengan : 1

Agus

2

Budi

1

Agus

2

3

Budi

3

Cerry

4

Cerry

4

Dedy

0

Dedy

0

?

?

a. List original

b. Operasi New

Gambar 4.8. Bentuk implementasi New dalam array IV.2.1. ALGORITMA TRAVERSAL LINKED LIST a.Traversal proses linked list // Traversing dengan array : Ptr = head While (ptr <> nil) do Proses (info [ptr]) Ptr = link [ptr] Endwhile

b.Traversal cetak linked list // Dengan array : Ptr = head While (ptr <> nil) do Write (info [ptr]) Ptr = link [ptr] Endwhile

// Traversing proses dengan pointer : Ptr = head While (ptr <> nil) do Proses (ptr^.info) Ptr = ptr^.next Endwhile

// Dengan pointer : Ptr = head While (ptr <> nil) do Write (ptr^.info) Ptr = ptr^.next Endwhile

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 11

// Menghitung jumlah proses : num =0 ptr = head While (ptr <> nil) do Num = num + 1 Ptr = ptr^.next Endwhile

Endwhile d. Algoritma mencari suatu item pada data terurut : ptr = head while (ptr <> nil) do if (item = ptr^.info) then ptr = ptr^.next else if (item = ptr^.info) then loc = ptr exit else loc = nil endif endif Endwhile

c.Algoritma mencari suatu item pada data tidak terurut : ptr = head While (ptr <> nil) do If (item = ptr^.info) then Loc = ptr Else Ptr = ptr^.next Endif Loc = nil

IV.2.2. ALGORITMA SISIP DATA DALAM LINKED LIST Head 1

New(P)

2

3

New(Q)

P

Q

4

New(R)

Type node = ^data Data = record Nilai : char; Next : node End;

R

Gambar 4.9. Bentuk sisipan list baru dalam linked list

Var head, tail, p,q : node;

A. SISIP AWAL Head

(2) New (Q)

P

(1)

(3) Read (Q^.data

a. Sisip list baru di awal linked list

SINAR SINURAT, ST

New (Q) Read (q^.nilai) ……………(3) Q^.next = nil P = Head If p = nil then Tail = Q else Q^.Next = P ………. (1) P = Q …………….. (2)

STMIK BUDIDARMA


Hal : 20

B. SISIP TENGAH Head B

D

(2)

E (1)

P

New (Q)

C (3) Read (Q^.data

a. Sisip list baru di tengah linked list

New (Q) Read (Q^.nilai) , Q^.next = nil P = Head While (p<> nil) If p^.nilai = ‘B’ then Q^.Next = P^.Next ……. (1) P^.Next = Q ………….. (2) Else p = p^.next Endwhile

C. SISIP AKHIR Head

B (1)

C New (Q)

D (2)

P

E (3) Read (Q^.data

If ( p=nil) then Sisip_awal Else Last = P While (last^.next <> Nil) do Last = last^.next Endwhile New (Q) P^.Next = Q ……………(1) Q^.Next = Nil ………….(2) Endif

new (Q) Q^.nilai = ‘E’ Q^.next = nil P = head if p = nil then P=Q else Tail^.next = Q Tail = Q endif

a. Sisip list baru di akhir linked list Gambar 4.10. Proses penyisipan list baru pada linked list

IV.2.3. ALGORITMA HAPUS DATA DALAM LINKED LIST A. HAPUS LIST AWAL Head (1) (2)

a. Hapus list awal dari linked list B. HAPUS LIST TENGAH

P = Head If (P <> nil) then Q = P …………………. (1) P = Q^.Next ………….. (2) Dispose (Q) Endif

(1)

P = Head Q = P^.Next ………………. (1) P^.Next = P^.Next^.Next ……(2) Q^.next = nil Dispose (Q)

b. Hapus list awal dari linked list

Catatan : Untuk menentukan posisi data yang akan dihapus maka dapat dibuat suatu pembanding

Head (2)

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 21

C. HAPUS LIST AKHIR

Head (2)

(1)

b. Hapus list awal dari linked list

Gambar 4.11. Proses penghapusan Suatu list dari Linked List

P = Head If (P^.next = nil) then Last = P P = Nil While (Last^.next <> Nil) do P = Last Last = Last^.Next EndWhile Q = Last If (P = Nil) then P^.next = nil Else P = p^.next Endif Else p = p^.next endif

Berikut ini disajikan program pascal yang mengimplementasi proses linked list (sisip awal, tengah, akhir dan hapus awal, tengah, akhir) : Uses CRT; Const garis = ’-------------------------------’; Pesan =’Linked list masih kosong’ ; Type simpul = ^data; Data = Record Nama : string; Alamat : string; Next : simpul; End; Var head, tail : simpul; Pilih : char; Cacah : integer; Function menu : char; Var p : char; Begin Clrscr; Writeln(’Pilihan Anda : ’); Writeln(‘a. Sisip list di awal’); Writeln(‘b. Sisip list di tengah’); Writeln(‘c. Sisip list di akhir’); Writeln(‘d. Hapus list di awal’); Writeln(‘e. Hapus list di tengah’); Writeln(‘f. Hapus list di akhir’); Writeln(‘g. Cetak isi linked list’); Writeln(’h. Selesai’); Repeat Writeln(’Pilih salah satu : ’); P := upcase (readkey); Until p in[‘A’,‘B’,‘C’,‘D’,’E’,’F’,’G’];

SINAR SINURAT, ST

Menu := p End; Function simpul_baru : simpul; Var b : simpul; Begin New(b) ; With b^ do Begin Writeln(‘Nama :‘); readln(nama); Writeln(‘Alamat :’); readln(alamat); Next := nil; End; Simpul_baru := b End; Procedure sisip_awal(n : integer); Var baru : simpul; Begin If n<> 0 then Begin Writeln(‘Menambah list di awal link list’); Writeln(copy(garis,1,45)) End; Baru := simpul_baru; If head = nil then tail := baru else Baru^.next := head; Head :=baru End;

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data Procedure sisip_tengah; Var baru, Bantu : simpul; Posisi, i : integer; Begin Writeln(’Menambah list ditengah linked list’) Writeln(garis); Writeln(’Linked list berisi :’,cacah:2,’ simpul’); Repeat Writeln(‘List baru ditempatkan di urutan ke berapa ?’); Readln(posisi); Until posisi in[1 .. cacah+1); If posisi = 1 then sisip_awal(0) else If posisi = cacah+1 then sisip_akhir(0) else Begin Baru := simpul_baru; Bantu := head; For i:=1 to posisi-2 do Bantu := Bantu^.next; Baru^.next := Bantu^.next; Bantu^.next := baru; End; End; Procedure sisip_akhir(n:integer); Var baru : simpul; Begin If n<> 0 then Begin Writeln(’Menambah list baru di akhir linked list’); Writeln(copy(garis,1,46)) End; Baru := simpul_baru; If head = nil then Head = baru else Tail^.next := baru; Tail := baru; End ; Procedure hapus_awal ; Begin If head <> nil then Begin Head := head^.next; Writeln(‘List awal telah dihapus’) End else writeln(pesan); Writeln(‘Tekan sembarang tombol’); Repeat until keypressed End; Procedure hapus_tengah; Var posisi,I : integer; Bantu, bantu1 : simpul; Begin If cacah = 0 then

SINAR SINURAT, ST

Hal : 22 Begin Writeln(pesan); Writeln(‘Tekan sembarang tombol’); Repeat until keypressed End else Begin Writeln(‘Menghapus list di tengah’); Writeln(copy(garis,1,35)); Writeln(‘Linked list berisi :’,cacah:2,’ simpul’); Repeat Writeln(‘Urutan list yang akan dihapus ? ’); Readln(posisi); Until posisi in[1..cacah]; If posisi = 1 then hapus_awal else If posisi = cacah then hapus_akhir else Begin For i:=1 to pisisi – 2 do Bantu := Bantu^.next; Bantu1 := bantu^.next; Bantu^.next := bantu1^.next; Bantu1^.next := nil; Dispose(bantu1) End End End; Procedure hapus_akhir; Var bantu : simpul; h : integer; Begin If head = nil then Begin Writeln(pesan); h := 0 End else If head = tail then Begin Head := nil; Tail := nil; h:=1 End else Begin Bantu := head; While (bantu^.next <> tail) do Bantu := bantu^.next; Tail := bantu Tail^.next := nil; h := 1 End ; If h=1 then Writeln(‘List akhir telah dihapus’) ; Writeln(‘Tekan sembarang tombol’); Repeat until keypressed End;

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data Procedure baca_list; Var bantu : simpul; i : integer; Begin i := 1; Writeln(’Membaca isi linked list’); Writeln(‘copy(garis,1,42)); Bantu := head; If bantu = nil then writeln(pesan) else While (bantu <> nil) do Begin Writeln(‘Simpul : ‘,i:2,’ → nama ‘,bantu^.nama); Writeln(’ ’:17,’Alamat : ’,bantu^.next); Inc (i) End; Repeat until keypressed End; {Program utama} Begin

Hal : 23

:

Cacah := 0; Head := nil; Tail := nil; Repeat Pilih := menu; Clrscr ; Case pilih of ‘a’ : sisip_awal(1) ; ‘b’ : sisip_tengah; ‘c’ : sisip_akhir(1); ‘d’ : hapus_awal; ‘e’ : hapus_tengah; ‘f’ : hapus_akhir; ‘g’ : baca_list; End; If pilih in [‘A’,’B’,’C’,] then Inc(cacah) else If pilih in [’D’,’E’,’F’] and (cacah <> 0) Then dec(cacah); Until pilih = ‘H’ End.

Tugas : 1. Buatlah prosedur untuk mengiput dua buah linked list dan menggabung keduanya menjadi Satu 2. Buatlah prosedur untuk mencari data tertentu pada linked list 3. Buat prosedur untuk mengganti data tertentu dalam linked list 4. Buatlah prosedur untuk mengurutkan data linked list

IV.3. LINKED LIST DENGAN MULTI POINTER IV.3.1. LIST CIRCULAR List circular (list berputar) adalah linked list yang tidak mempunyai node awal dan node akhir. Perhatikan diagram berikut pada gambar 4.12. Head

Gambar 4.12. Linked list circular Operasi-operasi pada list circular ditunjukkan pada algoritma berikut : Traverse : P = head Ptr = p^.next While ptr <> p do Proses ptr^.data Ptr = ptr^.next Endwhile SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 24

Mencari (search) posisi loc yang berisi item : Procedure search (data, next, p, item, loc) Ptr = p^.next While (ptr^.next <> item) and (ptr <> p) do Ptr = p^.next Endwhile If ptr^.data = item then Loc = ptr Else loc = nil Endif Endproc Menemukan posisi loc pada node awal dimana item berada : Procedure FindHL (data, next, p, item, locp); Save = p Ptr = p^.next While (ptr^.data <> item) and (ptr <> p) do Save = ptr Ptr = p^.next Endwhile If ptr^.data = item then Loc = ptr Locp = save Else Loc = nil Locp = save Endif Endproc Menghapus (delete) node awal : Procedure dellocHL (data, next, p, avail, item) FindHL (data, next, p, item, locp) If loc = nil then Write(‘Data tidak ada dalam list’) Exit Endif Locp^.next = loc^.next Loc^.next = avail Avail = loc Endproc

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 25

IV.3.2. LINKED LIST MULTI ARAH Deklarasi tipe data sebagai berikut : Type link = ^multi_node; Multi_node = Record field1 : type_field1 ; … : …….. ; fieldn : type_fieldn ; left, right : link ; End; Bentuk umum diagram multi linked list diperlihatkan pada gambar 4.13. Head

Tail

Pointer next Pointer back Data field

Gambar 4.13. Linked list dua arah Linked list 2 arah dengan bentuk circular terdapat perbedaan dengan linked list lainnya. Perhatikan diagram berikut pada gambar 4.14. Tail

Head

Pointer next Pointer back Data field

Gambar 4.14. Linked list circular dua arah Perhatikan proses penghapusan node tertentu dalam linked list dua arah dan urutan proses, ditunjukkan dalam gambar 4.15. berikut : Loc Node N

Gambar 4.15. Proses penghapusan Linked list dua arah

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 26

Demikian juga proses penyisipan node baru pada posisi tertentu dalam linked list 2 arah. Perhatikan urutan proses pada gambar 4.16. berikut : Loc B

Loc A

Baru

Gambar 4.16. Proses penyisipan node baru pada linked list dua arah

Operasi-operasi pada linked list 2 arah diperlihatkan pada algoritma berikut : Menyisip list baru ke dalam linked 2 arah : Procedure insert (data, forwd, back, p, avail, locA, locB, item) If avail = nil then Write(‘Overflow’) Exit Endif Baru = avail Avail = forwd^.avail Baru^.data = item LocA^.forwd = new New^.forwd = locB LocB^.back = locA Endproc Menghapus node tertentu dalam linked list dua arah : Procedure delete (data, forwd, back, p, avail, loc) Loc^.(back^.forwd) = loc^.forwd (Loc^.forwd)^.back = loc^.back Loc^.forwd = avail Avail = loc Endproc Berikut ini implementasi algoritma linked list dua arah dalam Bahasa pemrograman Pascal : Program linked_list; Type Penunjuk = ^RecNama; RecNama = Record Nama : string; Pra, post : penunjuk; End; Var datanama, head, tail : penunjuk; SINAR SINURAT, ST

STMIK BUDIDARMA


Procedure MasukData; Var lagi : char; Begin Mark(datanama); Head : datanama; Tail := datanama; Lagi := ’Y’; While (UpCase(lagi)=’Y’) do Begin New (datanama); Writeln(‘Nama : ‘); Readln(datanama^.nama); Datanama^.pra := nil; Tail^.post := datanama; Datanama^.pra := nil; Tail:= datanama; Write(’Ada lagi (Y/T) : ’); Readln(lagi0 ; End ; End ; Procedure urutkan ; Var x, i, j : penunjuk ; Begin Tail = head; Datanama := head^.post; Head^.pra := nil; While (datanama^.nama <> nil) do Begin i := datanama^.post; If datanama^.nama >= tail^.nama Then begin Datanama^.pra := tail; Tail^.post := datanama; Tail := datanama; Datanama^.post := nil End else Begin j := tail^.pra; While(datanama^.nama<= j^.nama) and (j <> nil) do j := j^.pra; If j = nil then Begin Head^.pra := datanama; Datanama^.post := head; Head := datanama End else SINAR SINURAT, ST

Hal : 27

Begin x := j^.post; j^.post := datanama; x^.pra := datanama; datanama^.pra := j; datanama^.post := x; End End Datanama := i End End; Procedure tampilkan; Begin Datanama := head; While datanama <> nil do Begin Writeln(datanama^.nama); Datanama := datanama^.post End End; { Program utama } Begin MasukData; Writeln(’Data sebelum diurutkan : ’); Tampilkan; Urutkan; Writeln(’Data sesudah diurutkan : ’); Tampilkan; End.

STMIK BUDIDARMA


Hal : 28

BAB V NOTASI POLISH, REKURSIF, STACK, QUEUE V.1. NOTASI POLISH Suatu metode untuk menulis/memetakan semua operator-operator sesuai dengan presedensi (prioritas) sebelum (prefix) operand-operand, sesudah (postfix) operand-operand atau diantara (infix) operand-operand yang juga merupakan operasi dalam stack. Berikut diberikan evaluasi skala prioritas operator seperti : Tabel 5.1. Skala prioritas Operator-operator Keterangan ^ * , / , div , mod + , - (binary) =,≠,<,>,≤,≥

not and , or :=

Presedensi (prioritas) Ekponensial / pemangkatan 6 Perkalian, pembagian, sisa bagi 5 Penjumlahan, Pengurangan 4 Sama dengan, tidak sama dengan, lebih kecil, 3 lebih besar, Lebih kecil atau sama dengan, Lebih besar atau sama dengan Tidak 2 Dan, Atau 1 Sama dengan 0

Notasi infix adalah jika operator berada diantara kedua operandnya, misalnya : suatu ekspressi c := a + b. Notasi prefix (notasi polish) adalah jika operator berada di depan kedua operandnya, misalnya : dari infix c := a + b menjadi := c + a b. Notasi postfix/suffix (reverse polish) adalah jika operator berada di belakang kedua operandnya, misalnya : dari infix c := a + b menjadi c a b + := Algoritma infix : 1. Scan dari kiri ke kanan sampai ketemu dengan kurung tutup yang paling awal 2. Scan kembali dari posisi sebelumnya ke kiri sampai ketemu kurung buka pertama 3. Lakukan operasi yang berada dalam tanda kurung 4. Ganti ekspresi di dalam kurung tersebut dengan hasil operasi 5. Ulangi langkah 1 sampai dengan selesai. Kelemahan algoritma ini adalah lama dan tidak efisien Algoritma posfix/suffix : 1. Scan dari kiri ke kanan sampai ketemu dengan operator 2. Ambil 2 operand yang berada langsung di sebelah kiri operator tersebut 3. Ganti ekspresi dengan hasil operasi 4. Scan lagi hasil operasi tadi ke kanan, jadi tidak perlu discan dari depan sekali seperti pada proses infix SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 29

Keuntungan dari notasi postfix/suffix ini adalah tidak perlu memakai tanda kurung untuk menyatakan prioritas pengerjaan serta lebih cepat dan efisien, karena tidak perlu selalu scan dari depan atau paling kiri. Untuk pekerjaan algoritma posfix/suffix ini, dipergunakan stack untuk menyimpan operand yang dibaca, yang belum dilakukan operasi terhadapnya. Perhatikan contoh ekspresi berikut : Infix : ( A + ( B * C – ( D / E ^ F ) * G ) * H ) Postfix : A B C * D E F ^ / G * - h * + Tabel 5.2. Operasi Stack No Simbol Stack yang discan ( A 1 (+ + 2 (+( ( 3 (+( B 4 (+(* * 5 (+(* C 6 (+(7 (+(-( ( 8 (+(-( D 9 (+(-(/ / 10 (+(-(/ E 11 (+(-(/^ ^ 12 (+(-(/^ F 13 (+() 14 (+(-* * 15 (+(-* G 16 (+ ) 17 (+* * 18 (+* 19 H 20 )

Ekspresi postfix

A A A AB AB ABC ABC* ABC* ABC*D ABC*D ABC*DE ABC*DE ABC*DEF ABC*DEF^/ ABC*DEF^/ ABC*DEF^/G ABC*DEF^/G*ABC*DEF^/G*ABC*DEF^/G*-H ABC*DEF^/G*-H*+

Keterangan

Baris 13 : Tanda ^ dipop karena sudah ketemu pasangan ( dan ) Baris 16 : Pasangan ( dan ) sudah ketemu maka dipop semua operator yang ada diantara ( dan ) Baris 19 : sudah ketemu pasangan ( dan )

V.2. REKURSIF Rekursif adalah merupakan salah bagian yang penting yang harus dipahami untuk operasi stack (tumpukan) maupun queue (antrian). Karakteristik rekursif adalah : 1. Terdapat satu atau lebih kasus sederhana dengan solusinya (stopping cases) 2. Kasus lain diselesaikan dengan mensubstitusi satu atau lebih kasus yang disederhanakan (closer to stopping cases) 3. Masalah yang disederhanakan hanya pada stopping cases yang relatif mudah diselesaikan. SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 30

Fungsi-fungsi yang menggunakan prinsip rekursif adalah : a. Fungsi faktorial Misalkan n ! = 1 x 2 x 3 x … x n Jika n = 0 atau 1 maka n ! = 1 lainnya n ! = n * (n – 1) ! Contoh : 4 ! = 4 * 3 ! 3!=3*2! 2!=2*1! =2*1=2 3! = 3 * 2 = 6 4 ! = 4 * 6 = 24 Algoritma : Function Factorial (n : integer) : integer; Begin If (n = 0) or (n = 1) then Factorial := 1 else Factorial := n * Factorial (n –1); End; b. Fungsi Fibonacci Jika n=0 atau n = 1 atau n = 2 maka Fibonacci = 1 lainnya Fibonacci = Fibonacci (n-1) * Fibonacci(n-2); Algoritma : Function Fibo(n : integer) : integer; Begin If (n=0) or (n=1) or (n=2) then Fibo := 1 else Fibo := Fibo(n-1) * Fibo(n-2); End; c. Fungsi Loop Proses penulisan ulang dengan cara berulang-ulang (rekursif) Algoritma : Procedure Deret (n : integer); Begin Writeln(n:3); If n <=10 then Deret(n+1); End; d. Menara Hanoi Merupakan proses rekursif dalam implementasi stack. Konsep rekursif ini dipakai untuk memindahkan piringan dari tiang 1 ke tiang 3 dengan bantuan tiang 2. Perhatikan diagram berikut :

SINAR SINURAT, ST

STMIK BUDIDARMA


Tiang 1

Tiang 2

Hal : 31

Tiang 3

Gambar 5.1. Menara Hanoi Implementasi algoritma dengan fragmen program dalam bahasa pemrograman pascal : Var cacah, cacah_gerak : integer; Procedure Hanoi(var cacah_gerak : integer; cacah, asal, lewat, tujuan : integer); Begin If cacah>0 then Begin Hanoi(cacah_gerak, cacah-1, asal, tujuan, lewat); Cacah_gerak := succ(cacah_gerak); Write(‘Langkah ke : ‘, cacah_gerak:2); Write(‘, pindahkan piringan no. ‘, cacah:2); Write(‘ dari tiang ‘, char(asal+64)); Writeln(‘ ke tiang ‘, char(tujuan+64)); Hanoi(cacah_gerak, cacah-1, lewat, asal, tujuan); End End; Begin Write(‘Berapa jumlah piringan : ‘); readln(cacah); Cacah_gerak := 0; Hanoi(cacah_gerak, cacah, 1, 2, 3); Writeln(‘Piringan sebanyak : ‘, cacah:2, ‘ buah, memerlukan’, Cacah_gerak:3,’ kali pemindahan’); End.

V.3. STACK Stack (tumpukan) merupakan bagian dari list (struktur linier) dimana item-item data ditambah atau dihapus selalu di posisi terakhir (LIFO =last in first out) yang disebut top. Pada stack terdapat terminologi Push dan Pop, dimana push maksudnya adalah memasukkan elemen data pada stack sedangkan pop adalah mengambil elemen data pada stack. Manfaat Stack adalah sebagai berikut : 1. Pengelolaan struktur yang bersarang (nested) atau yang berisi salinan dirinya sendiri dalam dirinya. Misalnya pengelolaan ekspressi aljabar, himpunan dari himpunan SINAR SINURAT, ST

STMIK BUDIDARMA


2. 3. 4. 5. 6.

Hal : 32

Implementasi algoritma parsing, evaluasi dan backtracking Digunakan oleh sistem operasi untuk memungkinkan prosedur yang nested Digunakan untuk memungkinkan konversi program rekursif menjadi non rekursif Untuk mendukung pushdown automata Untuk mendukung kompiler mengkonversi infix menjadi postfix dan kemudian mengevaluasi postfix menjadi atomik (assembly) command. Perhatikan diagram berikut : misalkan terdapat deretan input : A, B, C New stack Push A

A top

Push B

B A

Push C

top

C B A

Pop C

Pop B

Pop A

top B top A

A

top

Gambar 5.2. Operasi Stack Perhatikan implementasi algoritma berikut : Const sentinel = ‘#’; Type stackpointer = ^stacknode; Stacknode = Record Data : char; Next : stackpointer; End; Var top : stackpointer; Nextchar : char; Function emptystack(top : stackpointer) : boolean; Begin Emptystack := top = nil End; Procedure push(nextchar : char; var top : stackpointer); Var temp : stackpointer; Begin New(temp); Temp^.data := nextchar; Temp^,next := top; Top := temp; End;

SINAR SINURAT, ST

Procedure pop(var item : char; var top : stackpointer); Var temp : stackpointer; Begin If emptystack(top) then Writeln(‘Stack kosong’) else Begin Item := top^.data; Top := top^.next; End; End; Begin { program utama } Top := nil; Readln(nextchar); While nextchar = sentinel do Begin Push (nextchar); Readln(nextchar) End; While not emptystack (top) do Begin Writeln(nextchar); Pop(nextchar,top) End End.

STMIK BUDIDARMA


Hal : 33

V.4. QUEUE Suatu queue (antrian) juga bagian dari linked list yang digunakan untuk memodelkan sesuatu, seperti barisan tunggu pada suatu counter dengan model FIFO (first in first out). Operasi-operasi yang digunakan oleh queue antara lain enqueue adalah untuk memasukkan data dalam antrian sedangkan dequeue adalah untuk mengeluarkan data dari queue. Manfaat queue sebagai berikut : 1. Digunakan oleh sistem operasi untuk mengatur eksekusi task dalam suatu sistem untuk mencapai perlakuan “adil” (waiting line) 2. Untuk mail box dalam komunikasi antar proses 3. Untuk buffer dalam mekanisme print spooler komunikasi data 4. Untuk simulasi dan modelling, misalnya simulasi sistem pengendali lalu lintas udara dalam memprediksi performansi. Untuk lebih jelasnya perhatikan diagram berikut : front

rear Budi

Johan

Wardi

Ekonomi

Komputer

Teknik

2

1

1

(4) temp

(2)

Dulman Fisika

Hapus list

(1)

Sisip list 2 (3)

Gambar 5.3. Diagram Antrian Berikut akan disajikan bagaimana proses enqueue dan dequeue dalam queue seperti diagram dibawah ini : Emptyqueue() Size = 0

back

Front back enqueue(a) Size = 1

a front back

enqueue(b) Size = 2

a

b

Front

Gambar 5.4. Proses enqueue SINAR SINURAT, ST

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data dequeue() Size = 1

Hal : 34 back

b front back

dequeue() Size = 0 Front

Gambar 5.5. Proses dequeue Berikut diberikan implementasi algoritma queue : {untuk mencek apakah queue dalam keadaan kosong atau tidak} function emptyqueue(front : passpointer) : boolean; begin emptyqueue := front = nil end; Procedure enqueue(newpass : passanger; var front, rear : passpointer); Var temp : passpointer; Begin New(temp); temp^.passinfo := newpass; rear^.next := temp; temp^.next := nil; rear := temp; If emptyqueue(front) then front := rear End; Procedure dequeue(var nextpass : passanger; var front, rear : passpointer); Begin If emptyqueue(front) then writeln(‘Queue kosong’) else Begin nextpass := front^.passinfo; front := front^.link; If emptyqueue(front) then front := nil End End;

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 36

BAB VI TREE VI.1. PEMAHAMAN Tree (pohon) didefenisikan sebagai set (himpunan) node-node atau simpul-simpul dengan edge (penghubung node) secara langsung antara dua atau beberapa node. Proses tree tidak memiliki prinsip non rekursif.

Root suatu tree memiliki sifat-sifat antara lain : - Salah satu node sebagai root - Setiap node kecuali root terhubung dengan satu edge terhadap rootnya - Terdapat lintasan unik dari root terhadap node dan sejumlah edge harus dihubungkan dengan panjang lintasan. Perhatikan diagram di bawah ini yang menunjukkan bentuk pohon secara umum dengan ketinggian (heigh) dan kedalaman (depth) tertentu sebagai berikut : Level 0

a

b

f

c

g

d

h

Level 1

e

i

j

k

Level 2

Level 3

Gambar 6.1. Bentuk umum tree Terminologi-terminologi dalam tree sebagai berikut : a. Root / parent adalah subtree yang paling atas pada sebuah pohon b. Child adalah anak-anak dari suatu root, misalnya : b, c, d, e adalah child dari a dan f, g adalah child dari b dan seterusnya c. Sabling adalah node-node yang tergolong dari root yang sama (saudara kandung), misalnya : c, d, e adalah sabling dari b dan seterusnya d. Leaf adalah node-node yang tidak memiliki cabang lagi (tidak punya anak) e. Ancestor adalah nenek moyang (ayah dari nenek/kakek), misalnya : a adalah ancestor dari k f. Descendand adalah keturunan/anak dari cucu, misalnya : k adalah descendand dari a g. Depth adalah kedalaman suatu node (length) yang terhitung dari root, misalnya : Depth f, g, h, I, j adalah 2 ; Depth k adalah 3 Depth b, d, c, e adalah 1 ; Depth a adalah 0 h. Heigh adalah ketinggian (level) dari suatu pohon yang terhitung dari root (path terpanjang), misalnya heigh dari pohon diatas adalah 3 i. Satu node (single node) dapat juga disebut tree dengan heigh = 0 dan depth = 0 Dari pohon di atas dapat dibentuk sub-sub tree untuk membedakannya sebagai berikut : SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 37

Root

T1

T2

T3

……...

Tn

Gambar 6.2. Pohon dengan pola rekursif Pada tree secara otomatis termuat konsep linked list, dimana di antara setiap node diasumsikan sebagai record / list. Perhatikan diagram berikut ini :

F

D

H

C

E

G

J

Gambar 6.3. Subtree dari tree

Dalam pohon dikenal istilah keseimbangan yaitu jika masing-masing node pada subtree kiri dan subtree kanan memiliki perbedaan paling banyak satu. Perhatikan implementasi algoritma berikut : Type ref = ^node; Node = Record Key : integer; Left, right : ref; End; Var n : integer; root : ref;

Function tree(n : integer) : ref; Var newnode = ref; x, nl, nr : integer; SINAR SINURAT, ST

Begin If n = 0 then tree := nil else Begin nl := n div 2; nr := n – nl –1; read (x); new (newnode); with newnode^ do begin key := x; left := tree(nl); right := tree(nr) end; STMIK BUDIDARMA


tree := newnode end end; Procedure printtree(t: ref; h : integer); Var I : integer; Begin If t^ then Begin Printtree(left, h+1); For i:= 1 to h do write(‘ ‘);

Hal : 38

Writeln(key); Printtree(right, h+1) End; End; Begin Write(‘Masukkan banyak data : ‘); Readln (n); Printtree(root, 0); End.

Berikut akan dibuat suatu fragmen program untuk membangun pohon : begin (* deklarasi *) p := dmy; Var i, n, nl, nr, x : integer; repeat Root, p, q, r, dmy : ref; nl := n div 2; nr := n – nl –1; s : array[1..30] of write(‘input banyak data:‘); record n : integer; readln(x); rf : ref; new(q); q^.key := x; {push} end; n := nl; p^.left := q; p := q; Begin until n = 0; Write(‘Masukkan banyak data : ‘); q^.left := nil; Readln(n); r.right := dmy^.left; New(root); new(dmy); end; i:= 1; s[1].n := n; s[1].rf := root; until I = 0; repeat printtree(root^.right,0); n := s[i].n; r:=s[i].rf ; i:=i-1; {pop} end; if (n=0) then r^.right := nil else

fragmen program untuk mencari data dari pohon sebagai berikut : end; Var root : ref; k : integer; Procedure search(x : integer; var p : ref); Begin Procedure printtree (w : ref; l : integer); If p = nil then Var i : integer; begin if w <> nil then Begin with w^ do New(p); begin With p^ do printtree(left, l+1); Begin for i:= 1 to l do key := x; count := 1; write(‘ ‘); Left := nil; right := nil writeln(key); End printtree(right, l+1) End else end SINAR SINURAT, ST

STMIK BUDIDARMA


If x p^.key then search(x, p^.right) Else p^.count := p^.count + 1 end; Begin

Hal : 39

Root := nil; While not eof(input) do Begin Read (k); search(k, root) End; Printtree(root,0) End.

fragmen program untuk menghapus data dari pohon sebagai berikut : Type ref = ^data; Data = Record key : integer; count : integer; left, right : ref; end; Procedure delete(x : integer; var p : ref); Var p,q : ref; Procedure del (var r : ref); Begin If r^.right <> nil then del(r^.right) else Begin q^.key:=r^.key; q^.count:= r^.count; q := r; r := r^.left end end;

Begin If p= nil then writeln(‘Tidak temu’) else If x < p^.key then delete(x,p^.left) else If x > p^.key then delete(x,p^.right) Begin If q^.right = nil then p := q^.left else If q^.left = nil then p := q^.right else Del(q^.left) End End;

VI.2. BINARY TREE Dikatakan suatu binary tree apabila suatu pohon dengan masing-masing node maksimal memiliki dua anak. Perhatikan diagram berikut : R SL = sabling kiri SR = sabling kanan SL

SR

A

B

Gambar 6.4. Bentuk Binary tree Traversal yang digunakan adalah inorder, preorder, dan postorder. Dari gambar 6.4 di atas diperoleh informasi sebagai berikut : Preorder : RAB (kunjungan root sebelum subtree)

SINAR SINURAT, ST

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data Inorder

Hal : 40

: ARB

Postorder : ABR (kunjungan root sesudah subtree)

Contoh suatu ekspressi : inorder

: a + b / c * d – e * f menjadi

Preorder : * + a / b c – d * e f menjadi Postorder : a b c / + d e f * - *

Proses perubahan dari inorder ke preorder dan postorder ditunjukkan pada gambar berikut ini :

1

7

2

3

4

2

1

6

5 preorder

6

1

3

7

5

2

4

postorder

5

3

7

4

6

inorder

Gambar 6.5. Rute kunjungan dengan preorder, postorder, inorder

Sub klas binary tree : -

-

Full binary tree : setiap interval node tepat memiliki 2 cabang Perfect binary tree : semua node leaf berada pada level sama Complete binary tree : 1. Semua node leaf berada pada level terendah, merapat ke sebelah kiri atau membentuk perfect binary tree 2. Jika tinggi = 0 berarti node tunggal 3. Jika tinggi = 1 berarti node hanya dianak kiri 4. Jika tinggi = h yaitu perfect tree adalah root yang memiliki subtree dari root dengan tinggi h-1 adalah perfect binary tree di sebelah kiri dan sebelah kanan 5. Subtree di sebelah kiri root adalah complete binary tree dengan tinggi h-1 dan sub tree dari root adalah complete binary tree di kanan dengan tinggi h-2 Extended binary tree : binary tree dengan penggambaran tree-tree kosong dengan label (legenda) node yang lain.

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 41

Dibawah ini diberikan implementasi algoritma dengan bahasa pascal sebagai berikut : Procedure postorder (t : ref);

Type ref = ^node;

Begin

Node = Record Data : string;

If t <> nil then

Left, right : ref;

Begin Postorder(t^.left);

End;

Postorder(t^.right) Write(t^.data);

Procedure preorder (t : ref);

End

Begin

End; If t <> nil then Procedure inorder (t : ref);

Begin

Begin

Write(t^.data); Preorder(t^.left);

If t <> nil then

Preorder(t^.right)

Begin inorder(t^.left);

End

Write(t^.data);

End;

inorder(t^.right) End End;

VI.3. BINARY SEARCH TREE VI.3.1. KONSEP UMUM BST Binary search tree(BST) adalah suatu tree yang setiap nodenya berisi key-key dalam BST tersebut sebagai berikut : a. b.

Key dari root lebih besar dari key yang ada pada subtree kiri Key dari root kanan lebih besar dari key yang ada pada subtree kiri. Point a) dan b) juga berlaku pada node-node di subtree. BST ini digunakan untuk menyusun data karena fleksibel (mudah digunakan) dan efisien (memiliki probe log n) dan natural (memiliki sifat representasi alami). Probe adalah tempat yang harus dilalui sampai ditemukan data yang diinginkan, perhatikan diagram berikut : A

Jumlah probe = 4

B C

D

Gambar 6.6. Probe dalam pohon SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 42

Bila jumlah data = jumlah level disebut perfect binary tree (pohon seimbang) dengan depth adalah ⎣log N⎦ dan jika tidak seimbang depth = ⎣log N-1⎦, dan untuk lebih jelas perhatikan diagram berikut : A B

C

D

E

F

G

Gambar 6.7. Pohon seimbang

Jika jumlah data = N maka jumlah level (L) : untuk batas bawah ⎣ 2log n ⎦ + 1 dan batas atas ⎡ 2log (n+1) ⎤.

Bila jumlah data untuk tiap level : root = level–1 dan jumlah node pada tiap level ke i = 1 .. 2i-1, lengkapnya perhatikan tabel berikut :

Tabel 6.1. Jumlah data tiap level Level ke – i

Jumlah data

1

1 .. 1

2

1 .. 2

3

1 .. 4

4

1 .. 8

5

1 .. 16

6

1 .. 32

7

1 .. 64

Jika tiap level dari binary tree dengan L level penuh atau maksimum maka jumlah node juga maksimum : L-1

2

1-1

+2

2-1

+2

3-1

+ .. + 2

L-1

0

1

2

= 2 + 2 + 2 + .. + 2

L-1

=

L = 2∑ -12i

i=0

Perhatikan contoh berikut : 1. 2.

N=10 maka Lmin = ⎣ 2log 10 ⎦ + 1 = 3 + 1 = 4 atau Lmax = ⎡ 2log (10+1) ⎤ = 3.0…. ≈ 4 N= 130 maka L = 8 atau Lmin = ⎣ 2log 130 ⎦ + 1 = 7 + 1 = 8

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 43 i

Misalkan sebuah pohon biner memiliki Llevel maka jumlah data adalah L .. 2 -1, dari contoh di atas untuk L = 5 maka jumlah data = 5 .. 25-1 = 5 .. 31. VI.3.2. REPRESENTASI BST DALAM ARRAY Untuk mencek posisi-posisi data dipohon dalam bentuk implementasi array bahwa node root berada pada posisi i, anak kiri menempati posisi 2*i dan anak kanannya menempati posisi 2*i+1 ; i adalah level. Perhatikan bentuk pohon sebagai berikut : Level 0

2 i=1

3 i=2 i=4

Level 1

4

i=5

5

i=3

6

i=6

7

i=7

Level 2 Level 3

8

a. BST dalam pohon

Selanjutnya juga dalam bentuk implementasi array, perhatikan diagram berikut ini :

1

2

3

4

5

6

7

8

9

10

11

12

2

3

4

-

-

5

6

-

-

-

-

-

13 14 -

7

15 8

b. BST dalam array Item data

Posisi

2

1

3

2*1=2

4

2*1+1=3

5

2*3=6

6

2*3+1=7

7

2*7=14

Gambar 6.8. Representasi BST dalam array

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 44

VI.3.3. OPERASI SISIP, HAPUS DALAM BST A. Operasi SISIP Dapat digambarkan untuk setiap keadaan sebagai berikut : Root left right

Q

Sisip(3,Q)

3

• •

3

•

Q Sisip(5,Q)

5

• •

5

• •

2

• •

Q Sisip(2,Q)

3

Q

Sisip(4,Q)

3

2

• •

5

•

4

• •

Gambar 6.9. Operasi sisip node dengan BST B. Operasi HAPUS Dapat digambarkan untuk setiap keadaan sebagai berikut :

a. Hapus node 2 dan node 4 3 2

5 4

b. Hapus node 3 5 2

3 Q := Q^.kiri Dispose(Q^.kiri)

5 4

2

4

Q^.kiri

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 45

c.Hapus node 3 3

5

2

5

Terdapat 3 kemungkinan hasilnya

2

4 4

2

2 5

5

4

4

Gambar 6.10. Operasi hapus node dengan BST

Berikut diberikan implementasi algoritma BST : Type data = record ….. : ….; end; BST = record node : tipe_data; left, right : ^BST; end; T = ^BST;

Function makenull(P : T) : T;

Write(‘duplikat’); End;

Begin P := nil; makenull := p;

Function cari (x : tipe_data, p : T) : boolean;

End;

Begin Procedure sisip(x : tipe_data ; var p : T);

If p=nil then cari := false else

Begin

If x=p^.data.key then

If p = nil then

cari := true else

Begin

If x
New(p); P^.data := x; p^.left := nil; P^.right := nil;

Cari := cari(x^.right) End;

End else If x.key p^.data.key then sisip(x, p^right) else

SINAR SINURAT, ST

Function cek_kosong(p:T) : boolean; Begin If p=nil then kosong := true else Kosong := false

STMIK BUDIDARMA


Hal : 46

End; Procedure hapus(x : tipe_data; var p :T); Function cari_min(a:T) : T; Begin If a^.left=nil then

Begin If p <> nil then If x
begin cari_min := a^.node;

If x>p^.data.key then Hapus(x, p^.right) else

a := a^.right; end else

If (p^.left=nil) and (p^.right=nil) then p := nil else

cari_min := cari_min(a^.left); End;

If p^.left=nil then p := p^.right else If p^.right=nil then p := p^.left else P^.node := cari_min(p^.right); End;

VI.4. AVL-TREE AVL (Adelson-Velski-Landis) tree adalah merupakan salah satu subset BST yang selalu memperhatikan keseimbangan (balance) pohon. AVL tree sering disebut dengan balanced Binary tree. Keseimbangan berguna untuk menjamin bahwa depth algoritmik dalam worst case atau perubahanperubahan yang relatif kecil.

Hal-hal yang perlu diperhatikan antara lain : -

Jika data yang disisip adalah acak maka akan menghasilkan Binary tree yang mendekati ideal (mendekati O(log n)) Jika data yang disusun terurut maka akan menghasilkan binary tree yang memiliki struktur linier (mendekati O(log n) dan O(n)) Terminologi yang digunakan antara lain :

-

Successor adalah penghapusan suatu node dimana posisi-posisi nilai node sesudahnya akan dipindahkan ke rootnya Predecessor adalah melihat apakah ada nilai node (child) di sebelah kiri dimasukkan ke root dan di sebelah kanan tetap Balanced value / vector adalah suatu proses penambahan node untuk melakukan keseimbangan. Proses AVL tree dengan BST dimana setiap internal node (node dalam) adalah maksimum jumlah record kiri (ketinggian sub tree) dan jumlah record kanan (ketinggian subtree kanan) berbeda maksimum 1 (0, 1). Faktor kesetimbangan yang diterima (kiri, root, kanan) adalah (-1,0,1). Faktor kesetimbangan dapat dilakukan dengan rotasi, yang pada dasarnya penyeimbangan kembali dilakukan dengan merotasikan node-node tertentu dalam subtree tersebut berdasarkan harga-harga faktor ketimbangan tingkat node-node atas dalam subtree.

Ada 4 jenis rotasi :

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 47

1.

Rotasi kiri tunggal Bila N adalah subtree dimana terjadi penyisipan ( atau N adalah node baru di sisipan itu sendiri) dan N adalah ancestor paling bawah yang mendapatkan faktor keseimbangan menjadi –2, sementara P anak kiri dari R yang mana N adalah anak kiri dari P dengan faktor kesetimbangan P=-1. Rotasi dilakukan sehingga P menjadi ayah dari N dan R yang masing-masing anak kiri dan kanan dari P sementara jika ada subtree kanan dari P dengan x sebagai root maka akan menjadi subtree kiri dari R. Faktor kesetimbangan dari R dan P keduanya menjadi 0.

2.

Rotasi kanan tunggal Bila N adalah subtree dimana terjadi penyisipan ( atau N adalah node baru di sisipan itu sendiri) dan N adalah ancestor paling bawah yang mendapatkan faktor keseimbangan menjadi +2, sementara P anak kanan dari R yang mana N adalah anak kanan dari P dengan faktor kesetimbangan P=+1. Rotasi dilakukan sehingga P menjadi ayah dari N dan R yang masing-masing anak kiri dan kanan dari P sementara jika ada subtree kanan dari P dengan x sebagai root maka akan menjadi subtree kanan dari R. Faktor kesetimbangan dari R dan P keduanya menjadi 0.

3.

Rotasi kiri ganda Bila N adalah subtree dimana terjadi penyisipan ( atau N adalah node baru di sisipan itu sendiri) dan R adalah ancestor paling bawah yang mendapatkan faktor keseimbangan menjadi –2, sementara P anak kiri dari R yang mana N adalah anak kanan dari P dengan faktor kesetimbangan P=-1. Rotasi dilakukan 2 kali pertama dalam subtree P yang menghasilkan P sebagai anak kiri dari N. Jika N memiliki subtree kanan maka subtree ini menjadi subtree kiri dari R dan juga jika N memiliki subtree kiri maka subtree ini menjadi subtree kanan dari P. Faktor kesetimbangan menjadi 0. Faktor kesetimbangan N dan R tergantung faktor kesetimbangan N semula. Jika faktor kesetimbangan N=0 maka faktor kesetimbangan P dan R keduanya menjadi 0. Jika faktor kesetimbangan =-1 maka faktor kesetimbangan menjadi 0 dan R = +1. Jika faktor kesetimbangan N = +1 maka faktor kesetimbangan P = -1 dan faktor kesetimbangan R = 0.

4.

Rotasi kanan ganda Bila N adalah subtree dimana terjadi penyisipan (atau N adalah node baru di sisipan itu sendiri) dan R adalah ancestor paling bawah yang mendapatkan faktor keseimbangan menjadi +2, sementara P anak kanan dari R yang mana N adalah anak kiri dari P dengan faktor kesetimbangan P=-1. Rotasi dilakukan 2 kali pertama dalam subtree P yang menghasilkan P sebagai anak kanan dari N. Jika N memiliki subtree kiri maka subtree ini menjadi subtree kanan dari R dan juga jika N memiliki subtree kanan maka subtree ini menjadi subtree kiri dari P. Faktor kesetimbangan menjadi 0. Faktor kesetimbangan N dan R tergantung faktor kesetimbangan N semula. Jika faktor kesetimbangan N=0 maka faktor kesetimbangan P dan R keduanya menjadi 0. Jika faktor kesetimbangan =-1 maka faktor kesetimbangan menjadi 0 dan R = +1. Jika faktor kesetimbangan N = +1 maka faktor kesetimbangan P = -1 dan faktor kesetimbangan R = 0.

Algoritma Menyeimbangkan kembali pada penyisisipan -

-

-

Jika faktor kesetimbangan P semula adalah –1 (atau +1) dan sekarang menjadi 0 maka proses selesai Jika faktor kesetimbangan semula adalah 0 dan sekarang menjadi +1 (atau –1) maka faktor kesetimbangan (ayah dari P) berkurang 1 dan jika P anak kiri dari R atau faktor kesetimbangan (ayah dari P) bertambah 1 jika P anak kanan dari R Bila faktor kesetimbangan R menjadi 0 maka selesai (Berarti faktor kesetimbangan R menjadi –1 atau +1) Periksa secara rekursif ayah dari R (jika ada) sebagai R sekarang, R semula menjadi P, P semula menjadi N sampai dengan R = root atau selesai akibat kasus-kasus point sebelumnya (Berarti faktor kesetimbangan R semula adalah +1 menjadi +2 atau semula –1 menjadi –2). Periksa faktor kesetimbangan R dan P : 1. Kasus faktor kesetimbangan P = -1 atau 0 dan faktor kesetimbangan R = -2. Lakukan rotasi kiri tunggal dan selesai 2. Kasus faktor kesetimbangan P = +1 dan faktor kesetimbangan R = -2. Lakukan rotasi kanan ganda dan selesai 3. Kasus faktor kesetimbangan P = +1 atau 0 dan faktor kesetimbangan R = +2. Lakukan rotasi kiri tunggal dan selesai

SINAR SINURAT, ST

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data 4.

Hal : 48

Kasus faktor kesetimbangan P = -1 dan faktor kesetimbangan R = +2. Lakukan rotasi kanan ganda dan selesai

Algoritma Menyeimbangkan kembali pada penghapusan -

Tahap pertama penghapusan suatu node pada AVL tree adalah melakukan penghapusan sebagai yang dilakukan BST dan dilanjutkan dengan menyeimbangkan kembali Misalkan suatu node yang dihapus adalah D, setiap ancestor R mulai dari ayah D ke atas dilakukan pemeriksaan apakah terjadi perubahan faktor kesetimbangan Jika D adalah suatu anak (keturunan) kanan dari R dan faktor kesetimbangan R semula adalah 0 (yang menjadi –1 maka subtree R tetap seimbang serta tidak terjadi pemendekan R sehingga proses selesai Jika D adalah suatu anak (keturunan) kiri dari R dan faktor kesetimbangan R semula adalah 0 (yang menjadi +1 maka subtree R tetap seimbang serta tidak terjadi pemendekan R sehingga proses selesai Jika faktor keseimbangan R semula adalah +1 atau –1 dan menjadi 0 maka terjadi pemendekan subtree R dan proses pemeriksaan dilanjutkan ke ayah dari R sebagai R sekarang Jika faktor keseimbangan R semula adalah –1 menjadi –2 (catatan : D adalah keturunan/anak kanan dari R) maka dengan anak kiri R disebut P dari anak kanan R disebut N 1. Jika faktor keseimbangan P = 0 maka lakukan rotasi kanan tunggal dan selesai karena tidak terjadi pemendekan subtree R 2. Jika faktor keseimbangan P = -1 maka lakukan rotasi kanan tunggal namun karena terjadi pemendekan subtree R pemeriksaan untuk penyeimbangan kembali dilanjutkan pada ayah R sebagai R sekarang 3. (Berarti faktor keseimbangan = +1) dilakukan rotasi kanan ganda dan karena terjadi pemendekan R dan proses penyeimbangan kembali dilakukan pada ayah R sebagai R sekarang Faktor keseimbangan R semula adalah +1 dan menjadi +2 (catatan D adalah keturunan/anak kiri dari R) maka anak kanan R disebut P dan anak kiri R disebut N : 1. Jika faktor keseimbangan P = 0 maka dilakukan rotasi kanan tunggal dan selesai karena tidak terjadi pemendekan subtree R 2. Jika faktor keseimbangan P = +1 maka dilakukan rotasi kanan tunggal namun karena terjadi pemendekan subtree R pemeriksaan untuk penyeimbangan kembali dilanjutkan pada ayah R sebagai R sekarang 3. (Berarti faktor keseimbangan = -1) dilakukan rotasi kiri ganda dan karena terjadi pemendekan R dan proses penyeimbangan kembali dilakukan pada ayah R sebagai R sekarang

-

-

Contoh 1:AVL tidak seimbang dengan rotasi tunggal sehingga AVL seimbang 10

7 12

10

7

5 3

6

8

5

12

9

15

11

3

9

6

11

8

15

14

14

Gambar 6.11. Rotasi tunggal pada AVL tidak seimbang

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 49

Contoh 2:

AVL tidak seimbang dengan rotasi ganda sehingga AVL seimbang 6

6 8

4

A: 3 1

5

11

7

B:

3 1

11

8

4

13

A 9

13

2

2

7

12

9

14

14

12

10

5

10

B

Gambar 6.12. Rotasi ganda pada AVL tidak seimbang

Contoh 3 : Diberikan data sebagai berikut : 35, 40, 10, 12, 16, 17 Bentuklah BST dan tahap-tahap AVL tree dari data ini. 36

40 10

12

16

17

Gambar 6.13. Pohon bentukan BST

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 50

Tahap-tahap pembentukan AVL tree :

Sisip 35

Sisip 40

Sisip 10

0

1 35

1

35

35 0 0

0 40

Sisip 12

10

40

Sisip 16 (tidak balance) menjadi -1

35

0

1 10

-1

35

0

2

40

10

0

0

40

12

1

0 12

-1

35

40

0

12

0

10

16

0 12

Sisip 17 (tidak AVL), dilakukan rotasi sehingga : -2

35 1

0

12

-1

40

0

12

1

0 10

0

16

35

0

16

10

0

0 17

40

0 17

Gambar 6.14. AVL tree

Berikut dibawah ini disajikan implementasi algoritma : Algoritma sisip dapat diambil dari yang sebelumnya dengan melakukan search dan kemudian insert sebagai berikut :

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 51 begin (double rotasi}

Type ref =^node;

p2 := p1^.right;

Node = Record Key

p1^.right := p2^.left

: integer;

Count : integer;

p2^.left := p1;

Left, right : ref;

p^.left := p2^.right;

Bal : -1 .. 1

p2^.right := p; if p2^.bal = -1 then

End;

p^.bal := 1 else p^.bal := 0;

Procedure search (x : integer; var p : ref; var h : boolean;

if p2^.bal := 1 then

Var p1, p2 : ref; { h := false }

p1^.bal := -1 else

Begin

p1^.bal :=0; p := p2;

If p = nil then

end;

Begin

p^.bal := 0; h:=false

New (p); h := true; With P^ do begin Key := x; count :=1; left := nil; right := nil; Bal := 0

end end; end else if x>p^.key then begin

End

search(x, p^.right, h);

End else

if h then

If x
Case p^.bal of 1 : begin

Search(x,p^.left,h); If h then

p^.bal := 0; h:= false; end;

Case p^.bal of 1 : begin

0 : p^.bal := 1; -1 : begin {rebalanced}

p^.bal:=0; h:= false; end; 0 : p^.bal := -1; -1 : begin

p1 := p^.right; if p1^.bal := 1 then begin

p1 := p^.left; if p1^.bal := -1 then begin {single rotasi kiri } p^.left := p1^.right; p1^.right := p; p^.bal := 0; p:=p1; end else

SINAR SINURAT, ST

{single rotasi kanan } p^.right := p1^.left; p1^.left := p; p^.bal := 0; p:=p1; end else begin (double rotasi} p2 := p1^.left;

STMIK BUDIDARMA


Hal : 52 p^.right := p1.left;

p1^.left := p2^.right

p1.left:= p;

p2^.right := p1;

if b1 = 0 then

p^.right := p2^.left;

begin

p2^.left := p;

p^.bal := 1;

if p2^.bal = 1 then

p1^.bal := -1; h:=false

p^.bal := -1 else p^.bal := 0;

end else

if p2^.bal := -1 then

begin p^.bal := 0; p1^.bal :=0;

p1^.bal := 1 else

end;

p1^.bal :=0; p := p2;

p := p1;

end;

end else

p^.bal := 0; h:=false end

begin{ rotasi ganda } p2 := p1^.left;

end else

b2 := p2^.bal;

begin

p1^.left := p2^.right;

p^.count := p^.count + 1;

p2^.right := p1;

h:=false

p^.right := p2^.left;

end

p2^.left := p;

end;

if b2 = 1 then p^.bal := -1 else p^.bal := 0;

Procedure delete(x : integer; var p : ref; var h : boolean);

if b2 = -1 then

Var q, ref; {h := false}

p1^.bal := +1

Procedure balance1(var p : ref; var h : boolean);

else p1^.bal := 0; p := p2; p2^.bal := 0;

Var p1, p2 : ref; b1,b2 :-1..1;

end; end;

begin case p^.bal of -1 : p^.bal := 0;

end; end;

0 : begin p^.bal := 1; h := false; end; 1 : begin p1 := p1^right; b1 := p1^.bal; if b1 >=0 then begin { single rotasi kiri }

SINAR SINURAT, ST

Procedure balance2(var p : ref; var h : boolean); Var p1, p2 : ref; B1, b2 : -1 .. 1; Begin Case p^.bal of 1 : p^.bal := 0; 0 : begin p^.bal := -1; h:=fasle; end;

STMIK BUDIDARMA


Hal : 53 Del(r^.right, h);

-1 : begin { rebalance }

If h then balance2(r,h)

p1 := p^.left; b1 := p1^.bal; if b1 <= 0 then

End else

begin ( single rotasi kiri }

Begin

p^.left := p1^right;

q^.key := r^.key;

p1^.right := p;

q^.count := r^.count;

if b1 = 0 then

r := r^.left; h:= true

begin p^.bal := -1; p1^.bal := 1;

end end;

h:= false end else begin p^.bal := 0; p1^.bal := 0

Begin { Utama } If p = nil then Begin

end;

Writeln(‘Key tidak ada dalam tree’);

p := p1

H:= false

end else

End else

begin{ double rotasi }

If p^.key then

p2 := p1^.right;

Begin

b2 := p2^.bal;

Delete(x, p^.left, h);

p1^.right := p2^.left;

If h then balance1(p,h)

p2^.left := p1;

End else

p^.left := p2^.right;

If x > p^.key then

p2^.right := p;

Begin

if b2 = -1 then p^.bal := 1 else p^.bal := 0;

Delete(x,p^.right,h); If h then balance2(p,h)

if b2 = 1 then p1^.bal := -1

End else

else p1^.bal := 0;

Begin

p := p2; p2^.bal:= 0;

q := p; if q^.right = nil then

end;

begin

end;

p := q^.left; h:= true

end;

end else

end;

if q^.left = nil then Procedure del (var r : ref; var h : boolean); Begin { h := false } If r^.right <> nil then Begin

SINAR SINURAT, ST

begin p := q^.right; h:= true end else begin del(q^.left, h);

STMIK BUDIDARMA


Hal : 54

if h then balance1(p,h)

end

end

end;

VI.5. B-TREE B-Tree adalah struktur data yang sangat populer untuk pencarian disk bound. Sifat-sifat B-Tree adalah : 1. 2. 3. 4. 5.

Item data disimpan pada leaves Node-node non leaf data sampai ke key M-1 yang merujuk pencarian key I yang merepresentasi key yang paling kecil dalam subtree i+1 Root adalah juga suatu leaf atau yang memiliki anak antara 2 sampai dengan M Semua node non leaf (kecuali root) memiliki anak antara ⎡M/2⎤ dan M Semua leaves dengan depth yang sama memiliki anak anatara ⎡L/2⎤ dan L untuk setiap L Perhatikan diagram berikut :

P0 K1 P1K2 …. Pm-1Km-1PmKm

Gambar 6.14. B-Tree dengan M key

Misalnya dibawah ini ditunjukkan suatu B-Tree dengan order 2 dan 3 level, semua frame berisi 2, 3 atau 4 kecuali root diijinkan item tunggal.

25

30 40

10 20

2 5 7 8

13 14 15 18

22 24

26

27 28

32

41 42 45 46

35 38

Gambar 6.15. B-Tree untuk Order 2

Jika pencarian tidak berhasil kita berada dalam salah satu situasi berikut : 1. 2.

Ki < X < Ki+1 untuk 1 <= i < m lanjutkan pencarian pada frame pi selanjutnya Km < X Pencarian berlanjut pada frame Pm selanjutnya

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 55

X < K1 Pencarian berlanjut pada frame P0 selanjutnya Perhatikan proses penyisipan data baru pada sebuan B-Tree berikut : Sisip key 22 dalam B-Tree di order 2, ikuti langkah berikut :

1. 2. 3.

Key 22 tidak ada dalam frame, sisip di frame C, ini tidak memungkinkan sebab frame C penuh Frame C dipecah menjadi 2 frame, misalnya frame baru D dialokasi Key m+1 adalah sama diletakkan pada C dan D key tengah pindah ke atas 1 level kedalam ancestor frame A.

Untuk melihat keadaan penyisipan, perhatikan diagram berikut :

A

7

20

10

15 18

C

A

10

30 35 40

B

Menjadi :

7

26

15 18

20

30

22

26

B

35

40

C

D

Gambar 6.16. B-Tree dengan sisipan data

Contoh 1: Buatlah B-Tree dengan sikuensi data sebagai berikut : 20; 40 10 30 15 ; 35 7 26 18 22 ; 5 ; 42 13 46 27 8 32 ; 38 24 45 25 ; Catatan : tanda ; adalah batas frame.

a. Sisip 20

20

20

b. Sisip 40 10 30 15

10

15

30

SINAR SINURAT, ST

c. Sisip 35 7 26 18 22

40

STMIK BUDIDARMA 20

30


Hal : 56

e. Sisip 42 13 46 27 8 32 10

5

7

8

13 15 18

20 30 40

22 26 27

32

35

42

46

f. Sisip 38 24 45 25 25

10

5

7

8

20

13 15 18

30

22 24

40

26 27

32 35 38

42 45 46

Gambar 6.17. Keadaan B-Tree setelah proses penyisipan data Contoh 2: Buatlah B-Tree dengan sikuensi data yang akan dihapus sebagai berikut : 25; 45 24 ; 38 32 ; 8 27 46 13 42 ; 5 22 18 26 ; 7 35 15 ;

a. Hapus 25 sebagai root 25

10

5

7

8

20

13 15 18

30

22 24

40

26 27

32 35 38

42 45 46

32 35 38

42 45 46

Hapus 45 24 10

5

7

8

13 15 18

SINAR SINURAT, ST

20 30 40

22 24

26 27

STMIK BUDIDARMA


Hal : 57

b. Hapus 38 32 10

5

7

8

13

22 30 40

15 18 20

26 27

32 35 38

42

46

c. Hapus 8 27 46 13 42 10

5

7

8

13

22 30

15 18 20

26 27

35 40

42 46

d. Hapus 5 22 18 26 10

5

7

8

15

22

18 20

26

30 35 40

20

30 35 40

e. Hapus 7 35 15 15

7

f. Data terakhir

10

10

20 30 40

Gambar 6.18. Keadaan B-Tree setelah penghapusan data

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 58

Berikut perhatikan implementasi algoritma dengan bahasa pemrograman Pascal : if r = n then v := n else

Const n = 2;

begin

nn = 4; { page size }

v := e[n];

type ref = ^frame;

for i:=n downto r+2 do

item = record

e[i] := e[i-1];

key : integer; p

e[r+1] := u;

: ref;

end else

count : integer end;

begin

frame = record m : 0 .. nn;

r := r-n; v:=e[n+1];

po : ref;

for i:= 1 to r-1 do b^.e[i] := a^.e[i+n+1];

e : array[1..nn] of item

b^.e[i] := u;

end;

for i:= r+1 to n do

var root, q : ref;

b^.e[i] := a^.e[i+n];

x

: integer;

h

: boolean;

end;

u

: item;

m := n; b^.m := n; b^.p0 := v.p; v.p := b;

Procedure search(x : integer; a : ref; var h : boolean; var v : item); Var k,l, r : integer; q : ref; u: item;

end; end; end;

Procedure insert; Var I : integer; b: ref; Begin

begin { search } if a = nil then

With a^ do Begin

begin h := true;

If n < nn then Begin

with v do begin

Inc(m); h:=false; For i:= m downto r+2 do e[i]:=e[i-1]; e[r+1] := u end else begin new(b); if r<=n then begin

SINAR SINURAT, ST

key := x; count := 1; p:= nil end else with a^ do begin l := 1; r:= m; repeat k := (l+r) div 2; if x<e[k].key then r := k-1;

STMIK BUDIDARMA


Hal : 59 b^.m := mb; a^.m := n-1+k;

if x >= e[k].key then l := k+1;

h:= false;

until r < l ; if l-r > 1 then

end else

begin

begin for i:= 1 to n do

e[k].count := e[k].count + 1;

a^.e[i+n] := b^.e[i];

h:= false

for i:= s to mc-1 do

end else

c^.e[i] := c^.e[i+1];

begin if r=0 then q:=p0

a^.m := nn;

else q := e[r].p;

h := c^.m < n

search(x,q,h,u);

end

If h then insert

end else

c^.m := mc –1;

begin

End

if s=1 then b:= c^.p0

End;

else b:=c^.e[s-1].p;

End;

mb := b^.m + 1; k := (mb-n) div 2; Procedure delete (x : integer; a : ref; var h : boolean);

if k>0 then Begin

Var i, k, l, r : integer; q : ref;

For i:= n-1 downto 1 do

Procedure underflow (c,a : ref; s : integer; var h : boolean); Var b : ref; i, k, mb, mc : integer;

a^.e[i+k] := a^.e[i]; a^.e[k] := c^.e[s]; a^.e[k].p := a^.p0; mb := mb – k;

Begin mc := c^.m;

For i:= k-1 downto 1 do a^.e[i] := b^.e[i+mb];

if s < mc then

a^.p0 := b^.e[mb].p;

begin s := s+1; b:= c^.e[s].p;

c^.e[s] := b^.e[mb]; c^.e[s].p := a; b^.m := mb-1;

mb := b^.m ; k:= (mb-n+1) div 2;

a^.m := n-1+k; h:= false

a^.e[n] := c^.e[s]; a^.e[n].p := b^.p0; if k>0 then

end else begin b^.e[mb] := c^.e[s];

begin

b^.e[mb].p a^.p0;

for i:= 1 to k-1 do

for i:= 1 to n-1 do

a^.e[i+n] := b^.e[i];

b^.e[i+mb] := a^.e[i];

c^.e[s] := b^.e[k]; c^.e[s].p := b;

b^.m := nn; c^.m := me-1;

b^.p0 := b^.e[k].p; mb:=mb – k;

h:= c^.m
for i:= 1 to mb do b^.e[i] := b^.e[i+k];

end end

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 60 begin

end;

dec(m); h:= m
procedure del(p: ref; var h : boolean);

e[i] := e[i+1]

var a: ref;

end else

begin

begin

with p6 do

del(q,h);

begin

if h then underflow(a,q,r,h)

q := e[m].p;

end

if q <> nil then

end else

begin

begin

del (q,h);

delete(x,q,h);

if h then underflow(p.q.m,h)

if h then underflow(a,q,r,h)

end else

end

begin p^.e[m].p := a^.e[k].p; a^.e[k] := p^.e[m];

end; end;

m := m-1; h:= m
Procedure printtree(p : ref; l : integer); Var I : integer;

end

Begin

end

If p<> nil then With p^ do

begin if a = nil then

Begin For i:= 1 to l do write(‘ ‘);

begin

For i:= 1 to m do

writeln(‘key tidak ada dalam tree’)

write(a[i].key:4);

end else with a^ do

Writeln;

begin

Printtree(p0,l+1);

l := 1; r := m;

For i:= 1 to m do

repeat

Printtree(e[i].p, l+1);

k := (l+r) div 2; if x <= e[k].key then r := k-1;

End; End;

if x >= e[k].key then l := k+1; until l > r;

Begin

if r = 0 then q:= p0 else q:= e[r].p;

Root := nil;

if l-r > 1 then

While x <> 0 do

begin

Begin

if q = nil then

SINAR SINURAT, ST

Writeln(‘Cari key’,x);

STMIK BUDIDARMA


Hal : 61

Search(x,root,h,u);

end

If h then

end;

Begin

printtree(root,1);

q := root; new(root);

read(x)

with root^ do

end

begin

End.

m := 1; p0 := q; e[1] := u

VI.6. BINARY B-TREE Binary B-Tree (BB-Tree) adalah B-Tree khusus dimana order pertama B-Tree (n=1) yang mengaproksimasi setengah frame-frame hanya akan berisi item tunggal untuk disimpan (store) yang berada pada satu level. B-Tree berisi node-node (frame) dengan 1 atau 2 item lainnya, kemudian 1 page / frame berisi 2 atau 3 pointer (terhadap sabling) yang akan mengindikasikan 2 sampai dengan 3 tahap pohon. Berdasarkan B-Tree bahwa semua node/frame leaf berada pada level yang sama, dan semua frame (keturunan) non leaf yang kedua 2 atau ketiga termasuk root. Alternatif dari suatu alokasi linked yang masing-masing berisi masing-masing node terdapat linked list dengan panjang item 1 atau 2. Perhatikan diagram di bawah ini untuk lebih memperjelas pemahaman akan BB-Tree sebagai berikut :

a

b

a

b

c

Gambar 6.19. Representasi node dalam BB-Tree

Proses pencarian pohon menjamin panjang path maksimum P = 2 ⎡ log N ⎤

Saat melakukan penyisipan ada 4 kemungkinan yang perlu diperhatikan antara lain : 1.

Pada saat subtree kanan dibuat dan A merupakan key pada frame tersebut, kemudian keturunan B menjadi sabling (saudara) A, misalnya pointer vertikal menjadi horijontal pointer A

A

a

a

B b

SINAR SINURAT, ST

B b

c

c

STMIK BUDIDARMA


Tentukan frame berikut dengan 3 node dengan memecah dan merotasinya. A

B

a

b

A

B

a

C c

3.

Hal : 62

C

b

B

c

d

A

d

a

c

b

d

Bila subtree B diproses pada ketinggian tertentu maka pointer A akan merepresentasi keturunan, kemudian keturunan subtree A diijinkan menjadi saudara B. Dengan demikian frame mempunyai anggota 3 node sebagai berikut : B A

A

C

c

A

a

a

4.

C

a

c

b

B c

b

b

Dengan adanya pemotongan tanpa memperhatikan seperti langkah kedua, maka akan diperoleh sebagai berikut :

B c

A a

C

b

A d

a

B b

C c

B d

A a

C b

c

d

Gambar 6.20. Penyisipan node dalam BB-Tree

Pencarian dengan cara seperti diatas menunjukkan perbedaan (tidak efektif) apakah proses sepanjang horijontal dan vertikal (kasus langkah ketiga). Untuk menangani hal tersebut subtree kiri dan kanan diselesaikan secara intuisi yaitu “fisky” dengan membuang yang asimetris, sehingga dinamakan Symetric Binary B-Tree (SBB-Tree).

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 63

Pencarian yang lebih efektif, untuk mencapai rata-rata, tetapi proses sisip dan hapus akan lebih kompleks dimana masing-masing nodc butuh 2 bit (variabel boolean lh dan rh) untuk mengindikasi 2 pointer secara alami. Berikut dibawah ini terdapat 4 kasus penyisipan dalam SBB-Tree, semuanya akan merepleksikan kejadian frame yang overflow dan pemisahan sub sikuensi frame.

(LL)

B

C

A

B

C

B

A

A

A

C

A

B

C

C

B

(LR) B

A

A

B

(RR)

A

B

C

B

B

A

B

A

A

B

C

C

B

(RL)

C

B

A

C

Gambar 6.21. Penyisipan node dalam SBB-Tre Contoh : Deretan data (; adalah tanda pemisah frame (sanpshot)) dimana semua node tersebut berada dalam 1 level disebut hedge. (1) 1 2 ; 3 ; 4 5 6 ; 7 ; (2) 5 4 ; 3 ; 1 2 7 6 ; (3) 6 2 ; 4 ; 1 7 3 5 ; (4) 4 2 6 ; 1 7 ; 3 5 ;

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 64

(1) 1

2

2

2

1

3

4

1

4

3

5

6

1

3

3

(2)

4

5

4

2

3

2

5

6

3

2

1

(4)

2

1

5

6

5

5

7

4

3

4

1

3

6

4

(3)

2

4

5

6

4

5

3

2

7

1

7

6

6

3

4

5

7

Gambar 6.22. Pengembangan Hedge Tree pada proses sisip

Hal-hal yang perlu diperhatikan sebagai berikut : 1. 2. 3.

Jika h=0 maka subtree P tidak meminta pertukaran struktur pohon Jika h=1 maka node P mempunyai sabling (saudara tertentu) Jika h=2 maka subtree P memiliki pertambahan dalam ketinggian.

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 65

Implementasi algoritma dengan bahasa pemrograman pascal sebagai berikut :

p^.left:= p2^.right;

Procedure search(x : integer; var p : ref; var h : integer); Var p1, p2 : ref; Begin

p2^.right := p; p:=p2; end end else

If p = nil then Begin

begin h:= h-1;

New(p); h := 2;

if h<> 0 then

With p^ do Begin

p^.lh :=true end;

Key := x; count := 1; Left := nil; right := nil; Lh := false; rh := false End

end else If x < p^.key then Begin Search(x, p^.right, h);

End else

If h <> 0 then

If x < p^.key then Begin

If p^.rh then Begin

Search(x, p^.left, h); If h <> 0 then If p^.lh then

P1 := p^.left ; h:=2; p^.rh := false;

Begin

If p1^.rh then

P1 := p^.left ;

Begin

h:=2;

P^.right := p1^.left; p^.lh := false;

P1^.left := p;

If p1^.lh then Begin

p1^.rh := false; p:= p1

P^.left := p1^.right;

End else

P1^.right := p;

If p1^.lh then

p1^.lh := false; p:= p1

begin P2 := p1^.left;

End else

p1^.lh := false;

If p1^.rh then

P1^.left := p2^.right;

begin P2 := p1^.right; p1^.rh := false; P1^.right := p2^.left; p2^.left := p1;

SINAR SINURAT, ST

p2^.right := p1; p^.right:= p2^.left; p2^.left := p; p:=p2; end

STMIK BUDIDARMA


Hal : 66

end else begin h:= h-1; if h<> 0 then p^.rh :=true end; end else begin p^.count := p^.count+1 ; h:= 0; end end;

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 65

BAB VII HASHING DAN KOMPRESI VII.1. KONSEP HASH Tabel hashing digunakan untuk mengimplementasikan kamus dalam waktu konstan per operasi. Tabel hash mendukung pemanggilan dan penghapusan pada beberapa item yang telah dinamai sebelumnya. Untuk mengimplementasikan hash dapat mempergunakan array, dimana array tersebut akan diinisialisasi dengan indeks-indeks tertentu untuk melaksanakan proses penyisipan data dengan memetakan item-item ke dalam indeks dikenal fungsi. Fungsi hash digunakan untuk mengkonversi suatu item yang bernilai integer dengan indeks array dimana item tersimpan. Jika fungsi hash satu ke satu, kita dapat mengakses item dengan indeks arraynya sendiri sedangkan yang lainnya sebagian item mengambil beberapa indeks yang sama dan akan mengakibatkan tabrakan (collision). Misalnya suatu fungsi polinomial : A3x3 + A2x2 + A1x1 + A0x0 dapat dievaluasi sebagai (((A3)x + A2)x + A1)x + A0 Metode pemilihan key adalah : 1. Metode pembagian modulus (mod) yaitu menggunakan sisa dari setiap item data, dimana f(key) = h(key) = k mod b ; dimana k adalah key dan b adalah jumlah blok yang tersedia (biasanya bilangan prima). 2. Metode midsquare yaitu masing-masing item-item data yang akan disimpan dikwadratkan, kemudian memilih blok (bucket) penampung sesuai dengan nilai digit yang di tengah dari hasil data yang dikuadratkan tersebut. Misalnya jumlah blok (bucket) = 13

K

3

13 23

K2

9

169 529 225 256 676 729 1369 2209 2500

F(K) 4

0

5

15

4

16

9

26 27

0

37

1

4

47

12

50

4

collision collision

Gambar 7.1. Metode midsquare 3.

Metode penjumlahan digit yaitu setiap digit dari suatu bilangan dijumlah dan kemudian data tersebut disimpan pada blok yang sesuai

Contoh : SINAR SINURAT, ST

STMIK BUDIDARMA


169 f(K)= 1+6+9 = 16

529 5+2+9 16

225 2+2+5 9

Hal : 66

256 2+5+6 13

Collision

Jenis-jenis hashing : 1. Open hashing (hashing terbuka) Open hash (external hash) adalah suatu table dimana proses pertukaran item data dengan pointer masing-masing (tidak terpisahkan) tidak terbatas 2. Close hashing (hashing tertutup) Proses pemetaan data dalam tabel dengan indeks masing-masing, dimana kelemahannya sering terjadi collision. Untuk mengatasi collision terdapat beberapa cara : 1. Metode separate chaining Bahwa tabel hash T[0], T[1], T[2], … , T[n] akan berisi header list yang merujuk list dengan nilai f(K). Setiap lokasi berisi header list pada elemen data f(key) = i. Metode ini membutuhkan temporary space (tempat tambahan) 2. Metode closed chaining Merupakan modifikasi separate chaining dimana setiap item data ditambahkan link[i] yang merujuk item data selanjutnya. Proses ini akan selalu mencari tempat yang kosong untuk memetakan data, sedang pencarian biasanya dilakukan mulai dari posisi N sampai dengan posisi 1 dengan catatan tidak ditemukan collision. 3. Linier probing dan quadratic probing (open addressing) Merupakan metode chaining yang secara sekuensial yang tidak menggunakan space untuk link item data. Probe adalah suatu proses perbandingan nilai data pertama dengan data lain. Probe minimum (terbaik) = 1 berarti kompleksitasnya O(N) = 1 dan probe maksimum (terburuk) = N berarti kompleksitasnya O(N) = N (terurut) dan probe rata-rata = (1 + n)/2 berarti kompleksitasnya O(1+N)/2 = (1 + N)/2 dan probe kegagalan adalah O(N) = 0. Perhatikan contoh berikut : Diberikan deretan data adalah : 3, 13, 23, 15, 16, 26, 27, 37, 47, 50 data-data ini akan dipetakan ke dalam 13 blok (bucket) untuk menyimpan item-item data sebagai berikut : - f(3) = 3 mod 13 = 3 - f(13) = 13 mod 13 = 0 Collision - f(23) = 23 mod 13 = 10 - f(15) = 15 mod 13 = 2 Collision - f(16) = 16 mod 13 = 3 - f(23) = 26 mod 13 = 0 - f(27) = 27 mod 13 = 1 - f(37) = 37 mod 13 = 11 Collision - f(47) = 47 mod 13 = 8 - f(50) = 50 mod 13 = 11

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 67

VII.2. LINIER PROBING Merupakan pencarian secara sekuensial dalam array, pencarian dilakukan nulai dari posisi awal sampai dengan akhir tabel. Jika collision pada suatu alamat maka akan dicari alamat kosong kemudian kembali ke awal pengalamatan. Data : 3 13 23 15 16 26 27 37 47 50 F(key) : 3 0 10 2 3 0 1 11 8 11 Maka : 0

1

13

2

3

15

3

4

5

6

7

8

9

10 11 12

( 13 blok/bucket ) Langkah 1 .. 4

23

f(16)=3 terjadi collision (ada data dalam blok tersebut sebelumnya maka dilakukan dengan linier probing dengan fI(key) = (fI-1(key))+1) mod b f(16) = (3+1) mod 13 = 4

0

1

13

2

3

4

15

3

16

5

6

7

8

9

10 11 12

( 13 blok/bucket Langkah 1 .. 5

23

F(26)=0 terjadi collision maka f(26)=0+1 mod 13 = 1

0

1

2

3

4

13

26

15

3

16

5

6

7

8

9

10 11 12


23

F(27) = 1 terjadi collision maka = 1+1 mod 13 = 2 (collision) = 2+1 mod 13 = 3 (collision) = 3+1 mod 13 = 4 (collision) = 4+1 mod 13 = 5

0

1

2

3

4

5

13

26

15

3

16 27

6

7

8

9

47

10 11 12


23 37

F(50)=11 terjadi collision maka = 11+1 mod 13 = 12

0

1

2

3

4

5

13

26

15

3

16 27

6

7

8 47

9

10 11 12 23 37

( 13 blok/bucket

50

Gambar 7.2. Proses linier probing

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 68

Jadi melihat proses pemetaan data ke dalam array maka dapat kita lihat berapa kali proses probing, seperti diperlihatkan pada tabel berikut di bawah ini : Tabel 7.1. Proses probing Key Fungsi 3 f(3)=3 13 f(13)=0 23 f(23)=10 15 f(15)=2 16 f(16)=3 f(16)=4 26 f(26)=0 f(26)=1 27 f(27)=1 f(27)=2 f(27)=3 f(27)=4 f(27)=5 37 f(37)=11 47 f(47)=8 50 f(50)=11 f(50)=12 Total

Probe (kali) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 17

Jumlah probe Rata-rata probe = ----------------Jumlah data = 17/10 = 1,7 ≈ 2 kali

VII.3. QUADRATIC PROBING Proses mengkwadratkan posisi-posisi elemen data, kemudian membagi (mod) setiap elemen data, misalnya x = 5 bila B = 100 maka alamat hash (x) = 52 mod 100 = 25 untuk menghindari collision digunakan quadratic probing. Misalnya h(x) = y maka h2(x) = (y2 + y) mod B atau hi(x) = (hi-1(x) + P) mod B ; dimana p = 1,2,3… Hash function mengevaluasi H kemudian mencoba H2+12 ; H2+22 ;H2+32; …; H2+n2 ; dengan qwadratic probing dapat diselesaikan dilakukan dengan 2 cara : Cara I : 0

1

2

3

4

5

6

7

2

3

5

7

11 13 17 19

8

9

23 29

Terdapat 10 blok/bucket Primer 7 blok/bucket Averflow 3 blok/bucket

Maka h(x) x mod 7 dengan demikian :

h(2) = 2 mod 7 = 2 h(3) = 3 mod 7 = 3 SINAR h(5) SINURAT, = 5 mod 7 ST =5 h(7) = 7 mod 7 = 0 h(11) = 11 mod 7 = 4 h(13) = 13 mod 7 = 6 h(17) = 17 mod 7 = 3

collision collision collision

7 29 2 3 11 5 13

0 1 2 3 4 5 6

Langsung home address

STMIK BUDIDARMA


Hal : 69

Berarti : Key

: 2

3

Probe (kali) : 1

1

5 1

7

11 13 17 19

23 29

1

4

1

1

2

3

1

Total probe = 16 kali

Rata-rata probe = 16/10 = 1,6 ≈ 2 kali Collision terjadi sebanyak 6 kali Cara II : 0

1

2

3

4

5

6

7

2

3

5

7

11 13 17 19

8

9

Terdapat 10 blok/bucket

23 29

Tabel 7.2. Proses infinitive probing Indeks Key Modulo Address Probe Collision 2 1 1 H(2) 2 %10 3 1 2 H(3) 2 %10 5 1 3 H(5) 5 %10 7 1 4 H(7) 7 %10 1 1 5 H(11) 11 %10 3 1 1 6 H(13) 13 %10 4 1 H(13) (13+12) %10 7 1 1 7 H(17) 17 % 10 8 1 H(17) (17 + 12) %10 9 1 8 H(19) 19 % 10 3 1 1 9 H(23) 23 % 10 2 4 1 1 H(23) (23+1 )%10 7 1 1 H(23) (23+22)%10 2 2 1 1 H(23) (23+3 )%10 …… …… …. …… ….. Sehingga untuk sikuensi data diatas apabila diselesaikan dengan quadratic probing akan terjadi collision yang tidak terbatas (infinity) seperti pada item data 23 (tabel 7.2) 0

1

2

3

4

5

11

2

3

13

5

6

7

8

9

7

17

19

Gambar 7. 4. Infinitive Probing Kasus : Selesaikan dengan quadratic probing kasus berikut : Diberikan key-key yang akan diinput dalam tabel hash “satu”, “dua”, “tiga”, “empat”, “lima”, “enam”, “tujuh”, “delapan”, “sembilan”, “sepuluh”. SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 70

Spesifikasi : - Jumlah blok/bucket (ukuran hash) = 17 (indeks 0 sampai dengan 16) - Fungsi hash H(x) berdasarkan metode perkalian dengan A = 0.618 - Fungsi ordinal () total bilangan alpabetik dari huruf-huruf pada key (“a”=1, “b”=2, “c”=3, ..., “z”=26) - Coallision dipecahkan dengan cara rehashing dengan fungsi h2(x,i)=-i * ((ord*(x)%5)+1) sehingga penempatan probing ke i adalah hi(x) = h1(x) + h2(x) dengan i =1,2,3, … Tunjukkan urutan penempatan key-key tersebut dalam tabel dan berapa jumlah collision yang terjadi pada masing-masing penempatan key. Jawab : Tabel 7.3. Konversi alpabetik dengan fungsi ordinal Ord() Ordinal * A Fractional (AK) Ord(satu) = 19+1+20+21 = 61 61 * 0.618 = 32,698 0.698 Ord(dua) = 4 + 21 + 1 = 26 26 * 0.618 = 16.068 0.068 Ord(tiga) = 20 + 9 + 7 + 1 = 37 22.866 0.866 Ord(empat) = 5 + 13 + 16 + 1 + 20 = 55 33.990 0.990 Ord(lima) = 12 + 9 + 13 + 1 = 35 22.630 0.630 Ord(enam) = 5 + 14 + 1 + 13 = 33 20.394 0.394 Ord(tujuh) = 20 + 21 + 10 + 21 + 8 = 80 49.440 0.440 Ord(delapan) = 4+5+12+1+16+1+14=53 32.754 0.754 Ord(sembilan) = 19+5+13+2+9+12+1+14=75 46.350 0.350 Ord(sepuluh) = 19+5+16+21+12+21+8=102 63.036 0.036 Sebelum melakukan fungsi rehashing terhadap keseluruhan hasil ordinal huruf-huruf dari masing-masing item data diatas maka dapat dilakukan dengan fungsi floor (pendekatan pembulatan nilai ke bawah) pada fungsi hash H(x), seperti pada tabel berikut : Tabel 7.4. Fungsi rehashing Fungsi hash Rehashing H2(x,i) = -i * ((ord(x) % 5) + 1) H(x) = ⎣m.frac(AK)⎦ H(satu) = ⎣17 * 0.698 ⎦ = 11 H2(x,1) = -1 * (61 % 5 + 1) = -2 H(dua) = ⎣17 * 0.068 ⎦ = 1 H2(x,2) = -1 * (26 % 5 + 1) = -4 H(tiga) = ⎣17 * 0.866 ⎦ = 14 H2(x,3) = -1 * (37 % 5 + 1) = -9 H(empat) = ⎣17 * 0.990 ⎦ = 16 H2(x,4) = -1 * (55 % 5 + 1) = -4 H(lima) = ⎣17 * 0.630 ⎦ = 10 H2(x,5) = -1 * (35 % 5 + 1) = -5 H(enam) = ⎣17 * 0.394 ⎦ = 6 H2(x,6) = -1 * (33 % 5 + 1) = -24 H(tujuh) = ⎣17 * 0.440 ⎦ = 7 H2(x,7) = -1 * (80 % 5 + 1) = -7 H(delapan) = ⎣17 * 0.754 ⎦ = 12 H2(x,8) = -1 * (53 % 5 + 1) = -32 H(sembilan) = ⎣17 * 0.350 ⎦ = 5 H2(x,9) = -1 * (75 % 5 + 1) = -9 H(sepuluh) = ⎣17 * 0.036 ⎦ = 0 H2(x,10) = -1 * (102 % 5 + 1) = -30 Tabel ini tidak menunjukkan adanya collision.

SINAR SINURAT, ST

STMIK BUDIDARMA


Tabel 7.5. Penempatan probing i Key H(x) H2(x) 1 2 3 4 5 6 7 8 9 10

Satu Dua Tiga Empat Lima Enam Tujuh Delapan Sembilan Sepuluh 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

11 2 14 16 10 6 7 12 5 0

-2 -4 -9 -4 -5 -24 -7 -32 -9 -30

Hal : 71

Penempatan probing H’(x) = H(x) + H2*(x,i) 11 1 14 16 10 6 7 12 5 0

Sepuluh Dua

Sembilan Enam Tujuh

Lima Saturday Delapan Tiga empat

Gambar 7.5. Rehashing

Implementasi algoritma dengan bahasa pemrograman Pascal sebagai berikut : count := nhash[x]; const bucket = 100; head := nhash[count] type paket = ^data; new(nhash[count]); data = record nhash[count]^.item := x; item : byte; nhash[count]^.next := head; next : paket; end; end; var hash : array[1..99] of data; function member(x : byte; var nhash : count : byte; hash): boolean; head,current : paket; begin before, bil : hash; count := x mod bucket; if (count = bucket-1) then {prosedur untuk memasukkan data member := -1 else dalam hash} if nhash[count] = x then procedure insert(x : byte; var nhash : member := true else hash); member := member(count+1); begin SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 72

before := nhash[count]; current := nhash[count]^.next; while (before^.lagi <> nil ) and (not selesai) do begin if current^.isi = x then begin before^.lagi := current^.lagi; dispose(current); selesai := true end else begin before := current; current := current^.next end end

end; {prosedur untuk mencari data dalam hash} procedure search(x : byte; var nhash : hash); begin count := 0; if not member(x,bil) then writeln(‘data tidak ada dalam hash’) else writeln(‘data pada posisi : ’, count); end; { prosedur menghapus data dari hash } procedure delete(x : byte; var nhash : hash); var selesai : boolean; begin selesai := true; count := nhash(x); if nhash[count]^.isi = x then begin current := nhash[count]; nhash[count] := nhash[count]^.next; dispose(current) end else begin

end end; procedure hapus(x : byte; nhash : hash); begin if member(x, bil) then begin delete(x, bil); writeln(‘data telah dihapus’) end else writeln(‘data telah dihapus’); end;

VII.4. KOMPRESI Kompresi adalah suatu metode penghematan penyimpanan file dalam suatu media simpan. Dalam mengkompresi suatu file ada banyak metode-metode yang dapat digunakan dan salah satu yang akan dibahas adalah Algoritma Huffman. Algoritma Huffman dipakai untuk mengkonstruksi kode prefix yang optimal, yang memiliki proses penggabungan yang berulang-ulang terhadap bobot dua item data yang terendah. Misalnya w1 dan w2 dua buah data yang berbobot paling kecil diantara w1, w2, w3, …, wn maka akan dibentuk tree w1+w2, w3, w4, …, wn sehingga w1+w2 akan membentuk subtree sebagai berikut :

W1

W2

Gambar 7.6. Pembentukan subtree pohon Huffman

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 73

Dengan cara yang sama untuk semua data dapat dibentuk sub-sub tree sampai akhirnya membentuk sebuah pohon Huffman. Contoh : Tabel 7.6. Data pohon Huffman Karakter Frekwensi

Total Bit a e i s t sp nl

10 15 12 3 4 13 1

30 30 24 15 16 26 5

Langkah-langkah pembentukan pohon Huffman sebagai berikut : 1) 10

a

15

e

12

i

3

13

4

s

1

sp

t

nl

2) dipilih 2 buah elemen data yang terkecil yaitu s dan nl dengan jumlah 4 dengan membentuk subtree T1 4

T1 10

a

15

e

13

4

12

i

3

1

s

sp

t

nl

3) Kemudian dua buah elemen data lainnya dibandingkan untuk membentuk subtree berikutnya yaitu T1 dan t 8 T2 4

4

t

T1 10

a

15

e

SINAR SINURAT, ST

13

12

i

sp

3

s

1 nl

STMIK BUDIDARMA


4)

Hal : 74

Demikian seterusnya sampai terbentuk pohon Huffman yang komplit 18 T3 10

8

a

T2 4

4

t

T1 15

13

12

e

3

i

1

s

sp

nl

5) Perhatikan bahwa e=15, I=12, sp=13, dan t3=18 maka yang digabung adalah I dan sp 18 T3 10

8

a

T2

15

12

13

i

t

T1

T4

e

4

4

25

3

1

s

sp

nl

6) Menggabung e dengan T3 sebagai berikut : 33 T5 15

18

e

T3 10

8

a

T2

12

SINAR SINURAT, ST

13 sp

t

T1

T4

i

4

4

25

3

s

1 nl

STMIK BUDIDARMA


Hal : 75

7) Akhirnya diperoleh bentuk komplit pohon Huffman sebagai berikut : 58 T4 0

1

33

25

T5 0

T4 1

18

e

T3 0

1

8

1

4

i

13

sp

10

4

t

T1 0

1

12

a

T2 0

0

15

1

3

s

1 nl

Gambar 7.7. Proses pembentukan pohon Huffman Syarat pemberian nilai digit pada cabang kiri bernilai 0 dan cabang kanan bernilai 1 Berdasarkan pohon Huffman yang terbentuk (Gambar 7.7) maka dapat dicatat coding untuk masing-masing karakter, sebagai berikut : Tabel 7.7. Kode Karakter Karakter Code a 001 e 01 i 10 s 00000 t 0001 sp 11 nl 00001 Kemudian fase untuk decoding dapat dibentuk seperti diperlihatkan pada tabel berikut ini Tabel 7.8. Proses Decoding indeks

Char 0 1 2 3 4 5 6 7 8

Bobot

a e i s t sp nl T1 T2

SINAR SINURAT, ST

10 15 12 3 4 13 1 4 8

Parent (ayah) 9 11 10 7 8 10 7 8 9

Tipe anak 1 1 0 0 1 1 1 0 0 STMIK BUDIDARMA


9 10 11 12

T3 T4 T5 T6

18 25 33 58

Hal : 76

11 12 12 0

0 1 0 -

Berikut implementasi algoritma dengan bahasa pemrograman pascal : uses crt, printer, dos; const N = 4096; F = 18; limit = 2; nul = N; bufsize =1024; inbufptr : word = bufsize; inbufsize : word = bufsize; outbufsize : word = 0; outbufsize : word = 0; var infile, outfile : file; height, posmatch, lengthmatch, lengthend : word; textbuf : array [0..n + F –2] of byte; left, mom : array[0..n] of word; right : array[0..n+256] of word; codebuf : array[0..16] of byte; beof, press : boolean; h1, h2, m1, m2, s1, s2, c1, c2 : word; (* fungsi untuk membaca karakter *) function readchar : byte; begin readchar := 0; if inbufptr >= inbufsize then begin blockread(infile, inbuf, bufsize, inbufsize); inbufptr := 0 end; if inbufsize = 0 then beof := true else begin beof := false; readchar := inbuf[inbufptr]; inc(inbufptr); end end; (* prosedur menulis buffer ke file output *) procedure printfile; var actual : word; begin blockwrite(outfile, outbuf, outbufptr, actual) end; (* prosedur menulis karakter ke buffer output *) procedure printchar(nchar : byte); begin outbuf[outbufptr] := nchar; inc(outbufptr); if outbufptr >= bufsize then

SINAR SINURAT, ST

begin outbufptr := bufsize; printfile; outbufptr := 0 end end; (* prosedur inisialisasi BST *) procedure inittree; var i : word; begin i := N +1; repeat right[i] := nul; inc(i); until (i>N+256); i := 0; repeat mom[i] := nul; inc(i); until (i=n) end; (* prosedur menggeser posisi node keatas *) prosedur shifted(me : word); var ancestor, grdmtr, mother, child, brother : word; bexit : boolean; begin bexit := false; repeat mother := mom[me]; (* jika ibu bukan spesial node *) if mother <= nul then begin grdmtr := mom[mother]; (* jika ibu bukan spesial node *) if grdmtr <= nul then begin ancestor := mom[grdmtr]; (* jika aku anak kiri dari ibu *) if left[mother] = me then begin (* jika ibu anak kiri dari nenek *) if left[grdmtr] = mother then begin brother := right[mother]; left[grdmtr] := brother; mom[brother] := grdmtr;

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data child := right[me]; left[mother] := child; mom[child] := mother; right[mother] := grdmtr; right[me] := mother; mom[grdmtr] := mother; mom[mother] := me end else (* ibu anak kanan dari nenek *) begin child := left[me]; right[grdmtr] := child; mom[child] := grdmtr; child := right[me]; left[mother] := child; mom[child] := mother; left[me] := grdmtr; right[me] := mother; mom[mother] := me; mom[grdmtr] := me end end else (* aku anak kanan dari ibu *) begin (* ibu anak kiri dari nenek *) if left[grdmtr] = mother then begin child := right[me]; left[grdmtr] := child; mom[child] := grdmtr; child := left[me]; right[mother] := child; mom[child] := mother; right[me] := grdmtr; left[me] := mother; mom[mother] := me; mom[grdmtr] := me end else (* ibu anak kanan dari nenek *) begin brother := left[mother]; right[grdmtr] := brother; mom[brother] := grdmtr; child := left[me]; right[mother] := child; mom[child] := mother; left[mother] := grdmtr; left[me] := mother; mom[mother] := me; mom[grdmtr] := mother end end; if (ancestor > nul) or (right[ancestor] = grdmtr) then right[ancestor] := me else left[ancestor] := me; mom[me] := ancestor

SINAR SINURAT, ST

Hal : 77 end else (* jika nenek spesial node *) begin (* apakah aku merupakan anak kiri *) if left[mother] = me then begin child := right[me]; left[mother] := child; right[me] := mother end else begin child := left[me]; right[mother] := child; left[me] := mother end; right[grdmtr] := me; mom[child] := mother; mom[me] := grdmtr; mom[mother] := child; bexit := true end end else bexit := true; until bexit; end; (* prosedur untuk menambah node baru *) procedure addnode(position : word0; var preposition, templen, child : word; trigg : integer; bexit : boolean; begin trigg := 1; lengthmatch := 0; height := 0; preposition := textbuf[position] + n + 1; right[position] := nul; left[position] := nul; bexit := false; repeat inc(height); if trigg > 0 then (* untuk node dikanan *) begin if right[preposition] = nul then (* ditambah jika node sebelum kosong *) begin right[preposition] := position; mom[position] := preposition; bexit := true end else preposition := right[preposition] end else (* tambah node di kiri *) begin if left[preposition] = nul then (* tambah, jika node sebelumnya null *)

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data begin left[preposition] := position; mom[position] := preposition; bexit := true end else preposition := left[preposition] end; if not bexit then begin templen := 1; repeat trigg := textbuf[position + templen] – textbuf[preposition + templen]; if trigg = 0 then inc(templen) until (trigg <> 0) or (templen >= F); if templen > lengthmatch then begin posmatch := preposition; lengthmatch := templen; if templen .= f then begin mom[position] := mom[preposition]; child := left[preposition]; left[position] := child; mom[child] := position; child := right[preposition]; right[position] := child; mom[child] := position; (* jika preposisi anak kanan ibunya *) if right[mom[preposition]] = preposition then right[mom[preposition]] := position else left[mom[preposition]] := position; mom[preposition] := nul; bexit := true end; end; end; until bexit; if height >=30 then shifted(position) end; (* prosedur untuk menghapus node *) procedure erasenode(me : word); var mother, child, descend : word; begin mother := mom[me]; if mother <> nul then begin if right[me] <> nul then begin child := left[me]; if left[me] <> nul then begin descend := right[child]; if descend <> nul then

SINAR SINURAT, ST

Hal : 78 begin while right[descend] <> nul do descend := right[descend]; right[mom[descend]] := left[descend]; mom[left[descend]] := mom[descend]; left[descend] := left[me]; mom[left[me]] := descend; child := descend end; right[child] := right[me]; mom[right[me]] := child end else child := right[me]; end else child := left[me]; mom[child] := mother; if right[mother] = me then right[mother] = child else left[mother] := child; mom[me] := nul end end; (* prosedur untuk mengkoding file *) procedure encode; var temp, ptrcodebuf, cycleencode. Nchar, totread : byte; ptrinsert, ptrencode : word; bexit : boolean; begin inittree; temp := 0; codebuf[0] := 0; ptrcodebuf := 1; cycleencode := 1; ptrinsert := 0; ptrencode := N – F; bexit := false; repeat nchar := readchar; if not beof then begin textbuf[ptrencode + temp] := nchar; inc(temp) end; until (temp >= f) or (beof); if temp > 0 then begin totread := temp; addnode(ptrencode); repeat if lengthmatch > totread then lengthmatch := totread; if lengthmatch <= limit then begin lengthmatch := 1; codebuf[0] := codebuf[0] or cycleencode; codebuf[ptrcodebuf] := textbuf[ptrencode]; inc(ptrcodebuf]

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data end else begin codebuf[ptrcodebuf] := posmatch and 255; inc(ptrcodebuf) codebuf[ptrcodebuf] := (posmatch and 65280) shr 4 + lengthmatch – (limit + 1); inc(ptrcodebuf) end; cycleencode := cycleencode shl 1; if cycleencode = 0 then begin temp := 0; repeat printchar(codebuf[temp]); inc(temp) until temp >= ptrcodebuf; ptrcodebuf := 1; cycleencode := 1; codebuf[ 0] := 0 end; temp := 0; lengthakhit := lengthmatch; repeat nchar := readchar; if not beof then begin erasenode(ptrinsert); textbuf[ptrinsert] := nchar; if ptrinsert < (F-1) then textbuf[ptrinsert + N] := nchar; inc(ptrinsert); ptrinsert := ptrinsert and (N-1); inc(ptrencode); ptrencode := ptrencode and (N-1); addnode(ptrencode); inc(temp) end until (temp >= lengthend) or (beof); while temp < lengthend do begin inc(temp); erasenode(ptrinsert); inc(ptrinsert); ptrinsert := ptrinsert and (N-1); inc(ptrencode); ptrencode := ptrencode and (N-1); dec(totread); if totread > 0 then addnode(ptrencode0 end; if totread <= 0 then begin if ptrcodebuf >= 1 then begin temp := 0; repeat printchar(codebuf[temp]);

SINAR SINURAT, ST

Hal : 79 inc(temp) until temp >= ptrcodebuf end; bexit := true end until bexit end end; (* prosedur mendekoding *) procedure decode; var temp, headerbyte, nchar, cycledecode, prefixbit : byte; ptrtextbuf : word; bexit : boolean; begin cycledecode := 0; ptrtextbuf := N - F; bexit := false; repeat cycledecode := cycledecode shr 1; if cycledecode = then then begin nchar := readchar; if beof then bexit := true else begin cycledecode := 255; headerbyte := nchar end end if not bexit then begin prefixbit := headerbyte and 1; headerbyte := headerbyte shr 1; if prefixbit = 1 then begin nchar := readchar; if beof then bexit := true else begin textbuf[ptrtextbuf] := nchar; inc(ptrtextbuf); ptrtextbuf := ptrtextbuf and (N-1); printchar(nchar) end end else begin nchar := readchar; if beof() then bexit := true else begin temp := nchar; nchar := readchar; if beof then bexit := true else begin posmatch := nchar shr 4; posmatch := (posmatch shl 8 ) or temp; lengthmatch := nchar and 15) + limit = 1;

STMIK BUDIDARMA

Diktat : KBMI3305 - Struktur Data repeat posmatch := posmatch and (N-1); nchar := texbuf[posmatch]; textbuf [ptrtextbuf] := nchar; inc(ptrtextbuf); ptrtextbuf := ptrtextbuf and (N-1); printchar(nchar); inc(posmatch); dec(lengthmatch); until lengthmatch = 0 end end end end until bexit end; procedure kompresi; begin inbufptr := bufsize; inbufsize := bufsize; outbufptr := 0; height := 0; posmatch := 0; lengthmatch := 0; lengthend := 0; fillchar(textbuf, sizeof(textbuf),0); fillchar(left, sizeof(left),0); fillchar(mom, sizeof(mom),0); fillchar(right, sizeof(right),0); fillchar(codebuf, sizeof(codebuf),0); encode; printfile end; procedure dekompresi; begin inbufptr := bufsize; inbufsize := bufsize; outbufptr := 0; fillchar(textbuf, sizeof(textbuf),0); decode; printfile end; procedure statistik; var cprocess : string[10]; processtime : word; begin processtime := (h2 * 3600 + m2 * 60 + s2) – (h1 * 3600 + m1 * 60 + s1); if press then cprocess := ‘Kompresi’ else cprocess := ‘Dekompresi’; writeln(‘Proses = ‘, cprocess); writeln(‘Input : ‘, paramstr(1):11, ‘ ‘:10, filesize(infile)’); writeln(‘output : ‘, paramstr(2):11, ‘ ‘:10, filesize(outfile)’);

SINAR SINURAT, ST

Hal : 80 writeln(‘Waktu proses = ‘,processtime,’Detik’); end; (* program utama *) begin clrscr; if (paramcount < 2) or (paramcount > 4) then begin writeln(‘ Sintak : ‘, paramstr(0), ‘ Input file outfile[dekompresi]’); halt; end; if paramstr(1) = paramstr(2) then begin writeln(‘Nama file harus beda’); halt end; assign(infile, paramstr(1)); {$I--} reset(infile, 1); if ioresult <> 0 then begin writeln(‘Salah input file ‘,paramstr(1)); halt end; assign(outfile, paramstr(2)); rewrite(outfile, 1); {$I+} if ioresult <> 0 then begin writeln(‘Salah output file ‘,paramstr(2)); halt end; gettime(h1, m1, s1, c10; if paramcount <> 3 then begin press := true; kompresi end else begin press := false; dekompresi end; gettime(h2, m2, s2, c2); statistik; close(outfile); close(infile); readln; end.

STMIK BUDIDARMA


Hal : 1

BAB VIII GRAPH VIII.1. DEFENISI GRAPH Suatu graph G=(V,E) berisi suatu himpunan vertex dan himpunan edge E, masingmasing edge adalah sepasang (v,w) dimana v,w ε V. Vertex sering disebut dengan node dan edge disebut dengan arc. Beberapa himpunan vertex yang terhubung dengan himpunan edge akan membentuk graph. Jika sepasang edge diorder dan graph itu disebut dengan graph directed (digraph). Dalam digraph bahwa vertex w adalah adjacent (bersinggungan) terhadap vertex v jika dan hanya jika (iff) (v,w) ε E. Kadang-kadang edge memiliki komponen ketiga disebut weight (bobot) atau cost (ongkos). Misalkan V = { v0, v1, v2, v3, v4, v5, v6 } dengan 12 edge diperoleh : ⌠ (v0, v1, 2), (v0, v3, 1), (v0, v1, 3), (v1, v4, 10) ⎫ ⎬ E = ⎨ (v3, v4, 2), (v3, v6, 4), (v3, v5, 8), (v3, v2, 2) ⎩ (v2, v0, 4), (v3, v4, 2),(v4, v6, 6), (v6, v5, 1) ⎭

Sehingga diperoleh graph terhubung (digraph) sebagai berikut : 2

V0

3

2

V2

5

V1

1

4

2

V3

4

8 V5

10

1

V4

Indegree v3 = 2 ={v0, v1} Outdegree v3 = 4 = {v2, v4, v5, v6}

6 V6

Gambar 8.1. Graph berarah

Berdasarkan gambar diatas bahwa vertex yang adjacent terhadap v3 adalah v2, v4, v5, v6 dan |V| = 7 dan |E| = 12 dan |S| merepresentasikan size himpunan S Suatu path dalam graph adalah sikuensi dari vertex-vertex : w1, w2, …, wn sedemikian sehingga (wi, wi+1) ε E untuk 1<= i < n Length (panjang) dari suatu path adalah sejumlah node pada suatu path yaitu n-1, dan sering disebut dengan unweigted path length yaitu sejumlah biaya pada edge dalam path. Misalnya : Path v0 sampai v5 adalah v0, v3, v5. Panjang path adalah 2 edge dan weighted path length adalah 9 yang kebetulan path terpendek antara v0 dan v5. Simple path (path sederhana) adalah path yang mana semua vertex-vertex jelas, kecuali awal dan akhir boleh sama. Cycle dalam suatu digraph adalah suatu path dengan panjang paling sedikit 1 sedemikian sehingga w1 = wn; Suatu directed acycle graph (DAG) kadang-kadang didasarkan pada suatu penggabungan, dengan asumsi bahwa dalam directed graph (digraph = graph berarah) tidak boleh ada cycle. SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 2

VIII.2. SHORTEST PATH PROBLEM Shortest path problem (SPP) merupakan proses menemukan path terpendek (diukur dari banyaknya edge) dari vertex ditandai dengan S terhadap semua vertex. Contoh 1: A B A 215 B 215 C 581 420 D 307 181 E 353 413

C D 581 307 420 181 162 162 921 161

A

581

E 353 413 921 161 -

C

420

307

215 353 B

921 162

413 D

181 161

E

Gambar 8.2. Graph berarah SPP SPP dapat diselesaikan dengan Algoritma Djikstra pada graph adjacent diats dari C ke E (undirected = tidak berarah). {C} : {A, B, D, E } ≈ C – A = 581 C – B = 420 C – D = 162 C – E = 921 {C,D} : {A, B, C} ≈ A = min {CA, CDA} = {581, 469} B = min {CB, CDB} = {420, 343} C = min {CE, CDE} = {921, 323}

Minimum {C,D} = 162

Minimum {C,D,E} = 323

Maka path terpendek dengan Algoritma Djikstra adalah {C,D.E} = 323 (total jarak} Contoh 2 : 30

B

C 200

50 40 A

75

5 G

D 20

80

100

E

F

40

60

Gambar 8.3. Graph berarah SPP lain

Cari SPP dari satu vertex ke seluruh vertex lain dengan Algoritma Djikstra, A B E

: inisialisasi A=0 yang lain ke n : semula n dari A : 0 + 50 = 50 ; berarti terpendek ke AB = 50 : semula n

SINAR SINURAT, ST

path terpendek adalah AB STMIK BUDIDARMA


dari A : 0 = 100 ; berarti terpendek ke AE = 100 C : semula n dari B : 50 + 30 = 80 ; berari terpendek ke ABC = 80 D : semula n dari B : 50 + 40 = 90 ; berarti terpendek ke ABD = 90 F : semula n dari E : 100+60 = 160; berarti terpendek ke AEF=160 D : semula 90 dari B dari C = 80 + 5 = 85 tetap melalui E F : semula 160 dari E yaitu AEF = 160 dari D : 85 + 80 = 165 G : semula n dari C = 80 + 200 = 280 melalui F dari F = 160 + 40 = 200 yaitu AEFG = 200 jadi jalur terpendek dari : A – B = 50 ≈ AB A – C = 80 ≈ ABC A – D = 85 ≈ ABCD A – E = 100 ≈ AE A – F = 160 ≈ AEF A – G = 200 ≈ AEFG

Hal : 3

path terpendek adalah ABC

VIII.3. ALGORITMA MINIMAL SPANNING TREE Minimal spanning tree (MST) sering digunakan untuk menyelesaikan suatu proyek, dimana pada algoritma ini mengenal dua metode yaitu PRIMS dan Kruskal. PRIMS adalah proses pengunjungan semua vertex yang dimulai dari salah satu vertex, dimana kunjungan hanya boleh dilakukan sekali terhadap satu node, sedangkan KRUSKAL adalah proses kunjungan dengan prims, hanya syaratnya tidak boleh siklus, dengan memulai dari edge terpendek kemudian dilanjutkan ke edge terpendek kedua dan seterusnya sampai semua vertex/node terkunjungi. Contoh : K L M N P K 215 581 307 353 L 215 420 181 413 M 581 420 162 921 N 307 181 162 161 P 353 413 921 161 -

SINAR SINURAT, ST

STMIK BUDIDARMA


a. PRIMS : K kunjungi = true;

Hal : 4

evaluasi

K – L = 215 K – M = 581 Minimum = 215 K – N = 307 K – P = 353 L kunjungi = true; evaluasi K – M = 581 K – N = 307 K – P = 353 Minimum = 181 L – N = 181 L – P = 413 L – M = 420 N kunjungi = true; evaluasi K – M = 581 K – N = 307 K – P = 353 N – M = 162 Minimum = 161 N – P = 161 L – P = 413 L – M = 420 P kunjungi = true; evaluasi K – M = 581 K – N = 307 K – P = 353 L – P = 413 Minimum = 162 L – M = 420 N – M = 162 P – M = 921 M kunjungi = true; evaluasi Stop karena semua vertex sudah dikunjungi (true) maka total MST PRIMS = 215 + 181 + 161 + 162 = 719 dan Himpunan pencarian adalah = {(K,L), (L,N), (N,P), (N,M)} maka bentuk tree dan graph dari proses MST ini sebagai berikut : K 420

M

215 L

581

M 413 921

181

M

162

353

N 307

M P

161

M

M

a. bentuk pohon PRIMS

b. Graph PRIMS

Gambar 8.4. Algoritma MST PRIMS

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 5

b. KRUSKAL Dari gambar 8.4.b. menunjukkan bahwa : K - L ≠ L – K (N – P) = 161 (N – M) = 162 (N – L) = 181 (L – K) = 215

≈ ≈ ≈ ≈

{ (N,P) } { (N,P), (N,M) } { (N,P), (N,M), (N,L) } { (N,P), (N,M), (N,L), (L,K) }

Iterasi stop, karena setiap penambahan edge akan mengakibatkan proses penelusuran (trace) membentuk suatu siklus (cycle). Jadi total MST Kruskal = (N,P) + (N,M) + (N,L) + (L,K) = 161 + 162 + 181 + 215 = 719 Tree yang terbentuk sebagai berikut : N

N

N

N

N

Gambar 8.5. Algoritma MST Kruskal

SINAR SINURAT, ST

STMIK BUDIDARMA


Hal : 6

KEPUSTAKAAN 1. “Data structures and problem solving using java”; Mark Allen Weiss ; Addison Wesley ; 1998 2. “An Introduction to Data Structures and Algorithm with Java”; Gleen Rowe; Prentice Hall International Edition ; 1998 3. “Data Structures and Program Design” ; Robert L. Kruse ; Prentice Hall of India Privated Limited ; 1991 4. “Data Structures, Algorithms and Program Style Using C” ; James F. Korst; Leonard J. Garrett ; PWS-Kent Publishing Company ; 1988 5. “Data structures, Theory and Problem” ; Seymour Lipschutz ; McGraw Hill Book Company ; 1986 6. “Algorithms + Data Structures = Program” ; Niklaus Wirth ; Prentice Hall of India Private Limited; 1991 7. “Computer Algorithms, Introduction to Design and Analysis, Second Edition”, Sara Baase ; Addition – Wesley Publishing Company ; 1988 8. “Problem Solving and Structured Programming in Pascal, Second Edition”, Iliot B. Koffman ; Addition – Wesley Publishing Company ; 1985 9. “Turbo Pascal , Reference Manual”; Scotts Valley ; Borland International ; 1985 10. “Turbo Pascal , Jilid 1”; Jogianto H.M. ; Andi Offset Yogyakarta ; 1989 11. “Turbo Pascal , Jilid 2”; Jogianto H.M. ; Andi Offset Yogyakarta ; 1989 12. “Dasar-Dasar Pemrograman Pascal, Teori dan Program Terapan” ; Insap P. Santoso, Ir, M.Sc ; Andi Offset Yogyakarta ; 1987 13. “Belajar Sendiri Pemrograman Dengan Turbo Pascal 7.0” ; Ediman Lukito ; Elex Media Komputindo ; 1993 14. “Struktur Data (transparansi)” ; Universitas Bina Nusantara ; Jakarta ; 2001

SINAR SINURAT, ST

STMIK BUDIDARMA

BAB I PENDAHULUAN. Struktur data non abstrak dikelompokkan dalam beberapa bagian yaitu : 1. Set 2. Array 3. Record 4. File 5. Pointer, dan lain-lain

Recommend Documents