Searching : Binary Search

Binary search (pencarian bagi dua) adalah teknik pencarian yang diterapkan hanya pada elemen array yang telah terurut (sorted).
Prinsip binary search :
1. Mula-mula ambil posisi awal = 1 dan posisi akhir = N.
    Posisi tengah = (posisi awal + posisi akhir) / 2
2. Bandingkan data yang dicari (x) dengan data tengah.
    Jika x < data tengah, proses dilakukan kembali tetapi posisi akhir = posisi tengah - 1.
    Jika x > data tengah, proses dilakukan kembali tetapi posisi awal = posisi tengah + 1.
3. Demikian seterusnya hingga :
    Data tengah = x, yang berarti data ditemukan.
    Posisi awal > Posisi akhir, yang berarti data tidak ditemukan

Data : 3   9   11   12   15   17   20   23   31   35
Misal ingin dicari data 17 :
Posisi awal = 1
Posisi akhir = 10
Posisi tengah = (posisi awal + posisi akhir) / 2 = (1 + 10) / 2 = 5
Data tengah = 15

Karena x > data tengah → 17 > 15, maka proses dilanjutkan dengan :
Posisi awal = posisi tengah + 1 = 5 + 1 = 6
Posisi akhir = 10
Posisi tengah = (6 + 10) / 2 = 8

Karena x < data tengah → 17 < 23, maka proses dilanjutkan dengan :
Posisi awal = 6
Posisi akhir = 8 - 1 = 7
Posisi tengah = (6 + 7) / 2 = 6

Karena x = data tengah → 17 = 17. Maka data ditemukan pada indeks ke-6.

Searching : Hash Search

Beberapa metode searching (pencarian) :
1. Hash Search
2. Binary Search → akan dibahas di postingan berikutnya.

Hash Search :
#  Metode penempatan dan pencarian data secara langsung (direct access)
#  Konversi himpunan key (K) menjadi himpunan alamat (L) => H (K) = L

2 jenis metode hash search :
#  Close hash
ukuran tabel terbatas, jumlah data terbatas.
#  Open hash
ukuran tabel terbatas, jumlah data tidak terbatas.
karena memanfaatkan linked list untuk menempatkan data.

1. Close Hash

#  Index tabel : 0 sampai dengan (N - 1)
H (K) = K mod N
#  Index tabel : 1 sampai dengan N
H (K) = (K mod N) + 1

Contoh :
L = 100 alamat
Simpan data = 10347, 34212
H (10347) = 10347 mod 100 = 47
H (34212) = 34212 mod 100 = 12



Collision Resolution
Solusi untuk mengatasi tabrakan (collision) pada hash.
Tabrakan terjadi apabila terdapat 2 data atau lebih yang berbeda tetapi memiliki alamat hash yang sama.
Strategi collision resolution :
#  Linier resolution
#  Overflow
#  Double hash

2. Open Hash / Penggandengan / Chaining

Open hash : salah satu strategi untuk mengatasi tabrakan (collision).
Bentuk open hash :
#  Modification open hash
Terdiri dari hash luar (tabel alamat hash) dan hash dalam (untuk menyimpan data).
Data yang tersimpan masih terbatas karena ukuran hash dalam terbatas.
#  Linked list open hash
Semua data akan disimpan ke dalam linked list yang ditunjukkan oleh alamat hash.
Data yang dapat disimpan tidak terbatas.

Probe (Rata-rata Pencarian)
Digunakan  untuk menentukan besar efisiensi fungsi hash dengan mengukur banyaknya perbandingan key yang diperlukan untuk mencari alamat data.





Soal 1 (Materi Kuliah Sistem Berkas Ilmu Komputer UNDIP)

Diketahui data dengan key 25, 76, 63, 98, 58, 19.
1. Tempatkan data tersebut ke dalam close hash dengan ukuran tabel = 5 dengan penanganan collision :
a) Linier resolution
b) Overflow dengan ukuran overflow = 3 dan penempatan overflow dengan fungsi hash
c) Double hash
2. Tempatkan data tersebut ke dalam open hash dengan :
a) Modification open hash dengan ukuran hash luar = 3 dan hash dalam = 4. Kemudian sisipkan key 34
b) Linked list open hash dengan ukuran tabel = 3
Kemudian tentukan probe !

Jawaban
1a) Linier resolution
H ( 25 ) = 25 mod 5 = 0
H ( 76 ) = 76 mod 5 = 1
H ( 63 ) = 63 mod 5 = 3
H ( 98 ) = 98 mod 5 = 3
    H'1 ( 98 ) = ( 3 + 1 ) mod 5 = 4
H ( 58 ) = 58 mod 5 = 3
    H'1 ( 58 ) = ( 3 + 1 ) mod 5 = 4
    H'2 ( 58 ) = ( 4 + 1 ) mod 5 = 0
    H'3 ( 58 ) = ( 0 + 1 ) mod 5 = 1
    H'4 ( 58 ) = ( 1 + 1 ) mod 5 = 2
H ( 19 ) = 19 mod 5 = 4
    H'1 ( 19 ) = ( 4 + 1 ) mod 5 = 0
    H'2 ( 19 ) = ( 0 + 1 ) mod 5 = 1
    H'3 ( 19 ) = ( 1 + 1 ) mod 5 = 2
    H'4 ( 19 ) = ( 2 + 1 ) mod 5 = 3
    H'5 ( 19 ) = ( 3 + 1 ) mod 5 = 4  {ditolak karena tabel penuh}

25	0
76	1
58	2
63	3
98	4

K	25	76	63	98	58
T	1	1	1	2	5

Probe = ( 1 + 1 + 1 + 2 + 5) / 5 = 2

1b) Overflow
H ( 25 ) = 25 mod 5 = 0
H ( 76 ) = 76 mod 5 = 1
H ( 63 ) = 63 mod 5 = 3
H ( 98 ) = 98 mod 5 = 3 (overflow)
    Ho ( 98 ) = 98 mod 3 = 2
H ( 58 ) = 58 mod 5 = 3 (overflow)
    Ho ( 58 ) = 58 mod 3 = 1
H ( 19 ) = 19 mod 5 = 4
Tabel Utama

25	0
76	1
	2
63	3
19	4

Overflow

	58	98
0	1	2

K	25	76	63	98	58	19
T	1	1	1	2	2	1

Probe = ( 1 + 1 + 1+ 2 + 2 + 1) / 5 = 1,6

1c) Double hash
H ( 25 ) = 25 mod 5 = 0 ( T1 )
H ( 76 ) = 76 mod 5 = 1 ( T1 )
H ( 63 ) = 63 mod 5 = 3 ( T1 )
H ( 98 ) = 98 mod 5 = 3 ( T2 )

H ( 58 ) = 58 mod 5 = 3
    H'1 ( 58 ) = ( 3 + 1 ) mod 5 = 4 ( T1 )
H ( 19 ) = 19 mod 5 = 4 ( T2 )

K	25	76	63	98	58	19
T	1	1	1	1	2	1

Probe = ( 1 + 1 + 1 + 1 + 2 + 1 ) / 5 = 1,4

2a) Modification open hash

Hluar ( 25 ) = 25 mod 3 = 1

    Hdalam ( 25 ) = 25 mod 4 = 1

Hluar ( 76 ) = 76 mod 3 = 1

    Hdalam ( 76 ) = 76 mod 4 = 0

Hluar ( 63 ) = 63 mod 3 = 0

    Hdalam ( 63 ) = 63 mod 4 = 3

Hluar ( 98 ) = 98 mod 3 = 2

    Hdalam ( 98 ) = 98 mod 4 = 2

Hluar ( 58 ) = 58 mod 3 = 1

    Hdalam ( 58 ) = 58 mod 4 = 2

Hluar ( 19 ) = 19 mod 3 = 1

    Hdalam ( 19 ) = 19 mod 4 = 3

Sisipkan key 34 :

Hluar (34) = 34 mod 3 = 1

    Hdalam ( 34 ) = 34 mod 4 = 2

    Hdalam ( 34 ) = ( 2 + 1 ) mod 4 = 3

    Hdalam ( 34 ) = ( 3 + 1 ) mod 4 = 0

    Hdalam ( 34 ) = ( 4 + 1 ) mod 4 = 1

Hluar (34) = ( 1 + 1 ) mod 3 = 2

    Hdalam ( 34 ) = 34 mod 4 = 2

    Hdalam ( 34 ) = ( 2 + 1 ) mod 4 = 3

K	25	76	63	98	58	19	34
T	1	1	1	1	1	1	6

Probe = ( 1 + 1 + 1 + 1 + 1 + 1 + 6 ) / 4 = 3

2b) Linked list open hash

H ( 25 ) = 25 mod 3 = 1
H ( 76 ) = 76 mod 3 = 1
H ( 63 ) = 63 mod 3 = 0
H ( 98 ) = 98 mod 3 = 2
H ( 58 ) = 58 mod 3 = 1
H ( 19 ) = 19 mod 3 = 1

K	25	76	63	98	58	19
T	1	2	1	1	3	4

Probe = ( 1 + 2 + 1 + 1 + 3 + 4 ) / 6 = 2

Sorting

Sorting (pengurutan) adalah proses yang mengurutkan sekumpulan data baik secara ascending (dari kecil ke besar) maupun descending (dari besar ke kecil).
Teknik Pengurutan :
1. Teknik Penyisipan (Insertion)
2. Teknik Gravitasi / Gelembung (Bubble Sort)
3. Teknik Seleksi
4. Teknik Shell Sort
5. Teknik Quick Sort
6. Teknik Radix Sort

1. Teknik Penyisipan (Insertion Sort)
>> Anggap data pertama sudah memiliki posisi yang tepat.
>> Ambil A[2], bandingkan dengan A[1]. Jika A[2] < A[1], tukar posisi.
>> Ambil A[3], bandingkan dengan A[1] dan A[2]. Jika A[3] > A[1] dan A[2], sisipkan A[3] pada posisi yang sesuai antara A[1] sampai A[2], dan seterusnya.

2. Teknik Gravitasi / Gelembung (Bubble Sort)
>> Bandingkan A[1] dengan A[2]. Jika A[1] > A[2], tukar posisi.
>> Bandingkan A[2] dengan A[3]. Jika A[2] > A[3], tukar posisi. Dan seterusnya.

3. Teknik Seleksi (Selection Sort)
>> Cari data terkecil dari data pertama sampai data terakhir, tukar dengan data pertama.
>> Cari data terkecil dari data kedua sampai data terakhir, tukar dengan data kedua, dan seterusnya.

4. Teknik Shell Sort
Langkah 1.
>> Ambil data pertama, bandingkan dengan data lain pada jarak tertentu.
     Jarak = jumlah data / 2.
>> Bandingkan data kedua dengan data lain yan berjarak sama seperti sebelumnya, dan seterusnya.
Langkah 2.
>> Proses langkah 1 diulang tetapi dengan jarak = jarak langkah 1 / 2.
Langkah 3.
>> Proses langkah 2 diulang tetapi dengan jarak = jarak langkah 2 / 2.
dan seterusnya..

5. Teknik Quick Sort
>> Pilih sembarang data (misal data pertama), tempatkan pada posisi tengah.
>> Tempatkan data yang lebih kecil dari atau sama dengan data tengah di sebelah kirinya, dan yang lebih besar di sebelah kanannya.

6. Teknik Radix Sort
Teknik ini didasarkan pada nilai sesungguhnya dari suatu digit pada bilangan yang akan diurutkan (ribuan, ratusan, puluhan, dan sebagainya).

Fungsi Rekursif & Fungsi Iteratif

A. Fungsi Rekursif

Fungsi rekursif merupakan fungsi yang memanggil dirinya sendiri, prosesnya terjadi secara berulang-ulang. Perulangan rekursif menggunakan if.
Contoh :
f(0) = 3
f(n+1) = 2 f(n) + 3
f(3) ....?
Maka  f(0) = 3

           f(1) → f(n + 1) = 2 f(n) + 3
                        f(0 + 1) = 2 f(0) + 3
                        f(1) = 2.3 + 3 = 9
           f(2) → f(1 + 1) = 2 f(1) + 3
                        f(2) = 2.9 + 3 = 21
           f(3) → f(2 + 1) = 2 f(2) + 3
                        f(2) = 2.21 + 3 = 45

B. Fungsi Iteratif

Fungsi iteratif merupakan perulangan terhadap sekelompok instruksi dimana perulangan akan berhenti jika batasan syarat sudah tidak terpenuhi. Perulangan iteratif menggunakan for, while, do-while.

Kasus :
FPB (Faktor Persekutuan Terbesar)
Misal FPB 228 dan 90 :
228 / 90 = 2 sisa 48
90 / 48   = 1 sisa 42
48 / 42   = 1 sisa 6
42 / 6     = 7 sisa 0
FPB adalah sisa terakhir sebelum sisa = 0, yaitu 6.

Penyelesaian dengan fungsi rekursif 
Ilustrasi FPB rekursif :
FPB(228,90)    m > n
FPB(48,90)      m < n
FPB(90,48)      m > n
FPB(42,48)      m < n
FPB(48,42)      m > n
FPB(6,42)        m < n
FPB(42,6)        m > n
FPB(0,6)          m = 0
FPB 228 dan 90 = 6

int FPB(int m, int n){
       if (m == 0) return n;
       else if (m < n) return FPB(n, m);
       else return FPB(m % n, n);
}

Penyelesaian dengan fungsi iteratif 
m = 228, n = 90
do{
       r = m % n;
       if (r != 0){
              m = n;
              n = r;
       }
} while (r !=  0);

Graph

Graph (graf) merupakan struktur data yang terdiri atas kumpulan vertex (V) dan edge (E).
G = (V, E)
V : himpunan tidak kosong dari simpul-simpul
E : himpunan sisi (edge) yang menghubungkan sepasang simpul

Terdapat 2 kategori graf :
1. Directed graph (Graf berarah), seperti G3.
2. Undirected graph (Graf tidak berarah), seperti G1 dan G2.

Pada graf tersebut dapat didefinisikan himpunan vertex dan himpunan edge sebagai berikut:
V(G1) = {1, 2, 3, 4}                E(G1) = {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
V(G2) = {1, 2, 3, 4, 5, 6, 7}    E(G2) = {(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)}
V(G3) = {1, 2, 3}                    E(G3) = {(1,2), (2,1), (2,3)}

Terminologi Graf

1. Adjacent (Ketetanggaan)
Dua simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau G1 : Simpul 1 bertetangga dengan simpul 2 dan 3
                   Simpul 1 tidak bertetangga dengan simpul 4

2. Incidency (Bersisian)
Tinjau G1 : Sisi (2,3) bersisian dengan simpul 2 dan simpul 3
                   Sisi (2,4) bersisian dengan simpul 2 dan simpul 4
                   Sisi (1,2) tidak bersisian dengan simpul 4

3. Isolated Vertex (Simpul Terpencil)
Tinjau G3 : Simpul 5 adalah simpul terpencil

4. Degree (Derajat)
Degree suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Tinjau G1 : d(1) = d(4) = 2
                   d(2) = d(3) = 3
Tinjau G2 : d(1) = 3 → bersisian dengan sisi ganda
                   d(4) = 1 → bersisian dengan sisi gelang (loop)
Tinjau G3 : d(5) = 0 → simpul terpencil

                   d(4) = 1 → simpul anting-anting (pendant vertex)

Minimum Spanning Tree

Pada graf tak berbobot, minimum spanning tree adalah jalur dengan jumlah edge minimum sehingga semua vertex bisa dicapai.

Pada graf ABCDE terdapat 10 jaring yang menghubungkan kelima vertex, namun sebenarnya dibutuhkan hanya 4 jaring untuk mengunjungi setiap vertex yang ada pada graf tersebut, yaitu AB BC CD DE. Jalur minimum inilah yang disebut sebagai minimum spanning tree.
E = V - 1
Sehingga bila ada 5 vertex maka hanya dibutuhkan 4 edge untuk menghubungkan semua vertex tersebut.

Algoritma Djikstra

Algoritma djikstra adalah algoritma untuk mencari jalur terpendek dari vertex awal ke vertex akhir.

Jalur terpendek : A - B - F - C - H dengan jarak 60.

AVL Tree

AVL Tree adalah binary search tree yang memiliki selisih tingkat antara subtree kiri dan subtree kanan maksimal 1. AVL tree bertujuan untuk menyeimbangkan binary search tree.
Untuk menyeimbangkan tree dilakukan rotasi berikut :
1. Single rotation (Jika letak subtree Left- Left atau Right-Right)
2. Double Rotation (Jika letak subtree Left-Right atau Right-Left)

Binary Tree

Syarat Binary Tree (Pohon Biner)

#  Setiap node hanya boleh memiliki maksimal 2 subtree, kedua subtree harus terpisah

#  Setiap node hanya boleh memiliki paling banyak 2 child

Jumlah maksimum node pada setiap tingkat = 2 ^{n - 1}

Jumlah maksimum node pada binary tree = 2 ⁿ - 1

n : tingkat

Contoh pada gambar disamping :
Jumlah maksimum node tingkat 1 = 2^{n - 1} = 2^{1 – 1} = 1

Jumlah maksimum node tingkat 2 = 2^{n - 1} = 2^{2 – 1} = 2

Jumlah maksimum node tingkat 3 = 2^{n - 1} = 2^{3 – 1} = 4

Jumlah maksimum node binary tree dengan 3 tingkat
= 2ⁿ – 1 = 2³ – 1 = 7

Operasi-operasi Tree

1. Insert

Menambah node ke dalam tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan. Jika data yang akan dimasukkan lebih kecil daripada elemen root, maka akan diletakkan di node sebelah kiri.

2. Find

Mencari node di dalam tree secara rekursif sampai node ditemukan. Syaratnya tree tidak boleh kosong.

3. Traverse

Kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.

4. Count

Menghitung jumlah node dalam tree.

5. Height

Mengetahui kedalaman sebuah tree.

6. Find Min dan Find Max

Mencari nilai terkecil dan terbesar pada tree.

7. Child

Mengetahui anak dari sebuah node (Jika punya).

Ilustrasi Insert

Soal 1
Buatlah sebuah pohon dari urutan node berikut :
8  9  11  15  19  20  21  7  3  2  1  5  6  4  13  14  10  12  17  16  18

Jenis Traverse (Kunjungan)
1. PreOrder
Cetak node yang dikunjungi, kunjungi left, kunjungi right.



















2. InOrder
Kunjungi left, cetak node yang dikunjungi, kunjungi right.

3. PostOrder
Kunjungi left, kunjungi riht, cetak node yang dikunjungi.

Contoh Implementasi :

\











Soal 2
Tentukan notasi prefix, infix, dan postfix dari ekspresi berikut :

Jawaban :
Prefix   : ^ - * + ABC - DE + FG
Infix     : ((A + B) * C - (D - E)) ^ (F + G)
Postfix : AB + C * DE - - FG + ^

Soal 3
Tentukan notasi prefix, infix, dan postfix dari ekspresi berikut :

Jawaban :

Prefix   : - ^ / - * 4 A B C D * / 1/2 ^ - E F 2
Infix     : ((((4 * A) - B) / (C * D)) ^ 1/2) - ((E - F) ^ 2)
Postfix : 4 A * B - C D * / 1/2 ^ E F - 2 ^ -

Soal 4 (UAS Struktur Data 2013/2014 Informatika UNDIP)
Diketahui A = 7, B = 4, C = 3, D = -2, E = 5
Hitung ekspresi prefix berikut :
a) * + A B - C D
b) / + * A B C - D E

Jawaban :
a) * + A B - C D = (A + B) * (C - D) = (7 + 4) * (3 - (-2)) = 55
b) / + * A B C - D E = ((A * B) + C) / (D - E) = ((7 * 4) + 3) / (-2 - 5) = -4,43


Metode Pencarian Node

1. Depth First Search (DFS)
Urutan pencarian : A-B-D-E-C-F-G

2. Breadth First Search (BFS)
Urutan pencarian : A-B-C-D-E-F-G




Penghapusan (Delete) Node
1. Jika yang di delete adalah leaf, maka bisa langsung di delete

2. Jika node yang di delete hanya memiliki satu anak, maka anak tersebut langsung menggantikan posisi parent-nya.

3. Jika yang di delete adalah node dengan 2 anak (subtree), maka node yang menggantikan node yang dihapus adalah :
#  Node yang akan dihapus adalah node (30), berada di sisi kiri.
#  Node yang ada di sisi kanan dari node yang akan dihapus adalah (40).
#  Telusuri sisi kiri, node (35).
    Sisi kiri (35) tidak ada (null), maka (35) menjadi induk dari (40).
#  Sisi kanan dari node (35) adalah (37), maka (37) menjadi sisi kiri dari node (40).
#  Sisi kanan dari node (40) adalah (45), posisinya tetap.

Penyajian Binary Tree Secara Berurutan

Tree

Tree merupakan kumpulan node yang saling terhubung satu sama lain dalam satu kesatuan yang membentuk layaknya struktur sebuah pohon.

A. Representasi Tree

1. Tree dan Tingkatannya

2. Diagram Venn

3. Notasi Tingkat

4. Notasi Kurung
A (B (D , E (I , J)), C ( F , G , H))

B. Terminologi Tree

Istilah	Arti
Predecesor	Node yang berada di atas node tertentu
Successor	Node yang berada di bawah node tertentu
Ancestor	Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama
Descendant	Seluruh node yang terletak setelah node tertentu dan terletak pada jalur yang sama
Parent	Predecesor satu level di atas suatu node
Child	Successor satu level di bawah suatu node
Sibling	Node-node yang memiliki parent yang sama
Subtree	Suatu node beserta descendant-nya
Size	Banyaknya node dalam tree
Height	Banyaknya tingkatan dalam tree
Root	Node khusus yang tidak memiliki predecesor
Leaf	Node-node dalam tree yang tidak memiliki successor
Degree	Banyaknya child dalam suatu node

Penjelasan tentang tree :

   Ancestor (F) = C, A

   Descendant (C) = F, G

   Parent (D) = B

   Child (A) = B, C

   Sibling (F) = G

   Size = 7

   Height = 3

   Root = A

   Leaf = D, E, F, G

   Degree (C) = 2