Jawaban:
1. Binary Search Tree adalah salah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing – masing subpohon tersebut (kiri&kanan) itu sendiri adalah juga binary search tree.
Sebuah bst, pada dasarnya adalah sebuah pohon biner (binary tree), oleh karena itu, kita dapat melakukan traversal pada setiap node dengan metode inorder, preorder maupun postorder, dan jika kita melakukan traversal dengan metode inorder, pada dasarnya kita telah melakukan traversal valuenya secara terurut dari kecil ke besar, jadilah ini sebagai sorting algoritma.
Terdapat 3 operasi yang sangat mendasar dan juga sangat penting pada binary search tree yaitu operasi pencarian, penambahan, dan penghapusan elemen.
ü Operasi Pencarian
Algoritma Cari Simpul (kunci K, pohon P) :
a. Jika pohon P kosong kembalikan nilai NULL (tak terdefinisi)
b. Jika kunci K cocok dengan kunci akar t maka kembalikan simpul P
c. Jika kunci K > kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kanan (P) ) Jika kunci K <= kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kiri (P).
ü Operasi Penambahan Elemen
Algoritma Insert (kunci K, pohon P) :
a. Jika pohon P kosong maka kembalikan pohon baru dengan kunci akar = K <basis 0>
b. Jika kunci akar P = K, kembalikan P (tanpa diubah)
c. Jika kunci K > (kunci akar P,maka Insert (kunci K, upapohon kanan(P) )
d. Jika kunci K < (kunci akar P, maka Insert (kunci K, upapohon kiri(P) )
ü Operasi Penghapusan Elemen
Algoritma DelNode(kunci K, pohon P) :
a. Cari simpul yang mengandung kunci K
b. Jika simpul dengan kunci K ketemu maka :
i. Jika upapohon kiri kosong maka tukar simpul P dengan upapohon kanan P, lalu hapus simpul yang sudah ditukar tersebut
ii. Jika upapohon kanan kosong maka tukar simpul P dengan upapohon kiri P, lalu hapus simpul yang sudah ditukar tersebut
2. Jenis-jenis sorting dan Algoritmanya:
a. Bubble: Suatu metode sorting termudah dengan cara membandingkan element sekarang dengan element berikutnya. Jika element sekarang lebih besar dari element berikutnya maka kedua element tersebut ditukar, jika pengurutan tersebut adalah pengurutan ascending. Jika element sekarang lebih kecil dari element berikutnya, maka kedua element tersebut ditukar, jika pengurutan tersebut merupakan pengurutan descending. Algoritma dalam metode ini seolah-olah menggeser satu persatu element dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
b. Selection: Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
c. Insertion: Merupakan suatu metode pengurutan sederhana, dengan menggunakan perbandingan dimana array (data) diurutkan dalam satu entry yang dibuat dalam satu waktu. Algoritma ini kurang efisien bila digunakan pada data yang besar. Tetapi Insertion sort memberikan beberapa keuntungan seperti:
a. Efisien untuk data kecil
b. Efisien untuk set data yang sudah diurutkan secara substansial
c. Stabil dan tidak mengubah urutan relative dari element dengan tombol yang sama
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
d. Shell: Metode Pertambahan Menurun. Mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan. Pemilihan sekuens dimulai dari N/2. Kemudian dilakukan perulangan dari j=1 – N/2, pada masing-masing pengulangan dilakukan pembandingan antara data yg ke-j dengan data ke-(j+N/2). Bila data ke-j lebih besar dari dataa ke-(j+N/2), maka tukar. Perulangan dilakukan terus smp semua data ke j selalu lebih kecil daripada data ke-(j+N/2). Proses berikutnya sama, gunakan jarak (N/2)/2 atau N/4 dan kemudian N/8 dst, hingga N=1.
e. Merge: Sebuah algoritma sorting yang menggunakan metode perbandingan berbasis. Algoritma ini dalam implementasinya merupakan salah satu algoritma yang stabil, artinya algoritma ini dapat mempertahankan urutan masukan dari element yang sama dalam output yang telah diurutkan. Algoritma tersebut ditemukan oleh John von Neumann pada tahun 1945.
Berikut menjelaskan langkah kerja dari Merge sort :
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)).
f. Quick: Quick Sort adalah sebuah algoritma sortir dari model Divide and Conquer yaitu dengan cara mereduksi tahap demi tahap sehingga menjadi 2 bagian yang lebioh kecil. Langkah – langkahnya yaitu pertama kita harus mengidentifikasi key pada indeks pertama dalam list. Kemudian list dipartisi menjadi 2 bagian dimana list yang sebelah kiri adalah kumpulan dari key-key yang lebih kecil dari key pada indeks pertama dan list yang disebelah kanan adalah kumpulan dari key-key yang lebih besar dari key pada indeks pertama. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array.
g. Heap: Binary heap digunakan sebagai struktur data dalam algoritma Heap-Sort. Sebagaimana diketahui, ketika suatu Heap dibangun maka kunci utamanya adalah node atas selalu mengandung elemen lebih besar dari kedua node dibawahnya. Apabila elemen berikutnya ternyata lebih besar dari elemen root, maka harus di swap dan lakukan proses heapify lagi. Root dari suatu Heap Sort mengandung elemen terbesar dari semua elemen dalam Heap. Proses Heap Sort dapat dijelaskan sebagai berikut:
1. Representasikan Heap dengan n elemen dalam sebuah array A[n]
2. Elemen root tempatkan pada A[1]
3. Elemen A[2i] adalah node kiri dibawah A[i]
4. Elemen A[2i+1] adalah node kanan dibawah A[i]
5. Ambil nilai root (terbesar) A[1..n-1] dan pertukarkan dengan elemen terakhir dalam array, A[n]
6. Bentuk Heap dari (n-1) elemen, dari A[1] hingga A[n-1]
7. Ulangi langkah 5 dimana indeks terakhir berkurang setiap langkah.
h. Bucket: Merupakan algoritma sorting yang bekerja dengan memartisi array menjadi beberapa bagian yang diimplementasikan sebagai beberapa buah ember. Setiap ember diurut satu persatu dengan menggunakan algoritma sorting yang berbeda atau dengan rekursif pada suatu ember.
Algoritma:
a. Membuat suatu array dengan menginisialisasikannya dengan nama “ember”
b. Taruh setiap data pada ember
c. Urutkan setiap ember yang berisi data.
d. Cek ember satu per satu dengan terurut dan taruh seluruh element pada array yang asli
i. Radix: Radix Sorting adalah metode sorting yangajaib yang mana mengatur pengurutan nilai tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Secara harfiah, radix dapat diartikan sebagai posisi dalam angka. Pada sistem desimal, radix adalah digit dalam angka desimal. Seperti contoh, angka “42” mempunyai 2 digit yaitu 4 dan 2. Radix Sort memperoleh namanya dari digit-digit tersebut, karena metode ini pertama kalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, begitu juga seterusnya.
Sorting dilakukan dengan :
ü membagi data set ke sub-sub data set sesuai dengan harga radixnya, kemudian
ü menyatukannya subset subset tersebut menjadi satu set kembail (hanya mekonkatenasi) untuk dilakukan pembagian berikutnya berdasarkan radix yang lebih signifikan.
Setelah radix demi radix dilakukan, mulai dari radix yang paling tidak signifikan ke yang paling signifikan, maka kemudian akan dihasilkan data terurut.
3. Pengertian tentang Sequential Search dengan Binary Search
Ø Sequential Search : merupakan suatu metode pencari nilai data pada suatu daftar, proses dalam metode ini terdiri dari pengecekan setiap element dalam satu waktu sampai data yang diinginkan ditemukan. Metode ini merupakan salah satu algoritma yang paling mudah, karena pada beberapa permasalahan kita juga dapat menggunakan metode brute force dalam algoritma ini.
Diketahui ada data {8,10,6,-2,10,7,1,100} Dan kemudian sub data yang ingin dicari adalah misalnya angka 1. Seperti pada tabel di bawah ini :
| Array | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| DATA | 8 | 10 | 6 | -2 | 10 | 7 | 1 | 100 |
| TARGET | 1 | |||||||
Maka Sesuai dengan permintaan di atas pada bagian Pencarian maka langkah penemuannya adalah :
1. Bandingkan data pada array 0 dengan Target. ternyata 8 != 1, maka lanjutkan ke array selanjutnya.
2. Sekarang data pada array 1 dibandingkan dengan Target. ternyata juga 10 != 1, maka lanjut
Begitu seterusnya sampai berhenti pada Array ke 6. karena nilai array ke 6 = target, maka tampilkan data pada array ke 6.
Ø Binary search : merupakan sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama.
Prinsip pencarian biner adalah :
ü Data diambil dari posisi 1 sampai posisi akhir N
ü Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
ü Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
ü Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
ü Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
ü Jika data sama, berarti ketemu.
Contoh Data:
Misalnya data yang dicari 17
Karena 17 > 15 (data tengah), maka: awal = tengah + 1
Karena 17 < akhir =" tengah">
Karena 17 = 17 (data tengah), maka KETEMU!
4. Pengertian BFS dengan DFS:
v BFS (Breadth First Search) : merupakan suatu algoritma pencari dalam graf yang dimulai pada node root dan menjelajah seluruh node tetangganya. Lalu untuk seluruh node terdekat, mereka akan menjelajah ke node-node tetangga yang belum dijelajah dan seterusnya sampai menemukan tujuan akhirnya. Metode ini bertujuan untuk menjelajah seluruh node dari suatu graf atau kombinasi dari sekuens dengan sistem pencari melewati seluruh solusi. Dengan kata lain, metode ini adalah suatu metode yang cukup boros karena mencari seluruh graf atau sekuens tanpa berpikir tentang hasil akhir. Dari root, seluruh node child didapat dengan menjelajah node lain dengan mengunakan FIFO (first in first out) queue.
Algoritma BFS:
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
v Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya. Berkaitan dengan mesin pencari, DFS ini cenderung mengindeks dokumen berdasarkan suatu link.
Algoritma DFS:
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka Stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian.
4. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2.
5. Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q.
6. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
Contoh :
Sebuah bidak (pion) bergerak di dalam sebuah matriks pada Gambar 6.11. Bidak dapat memasuki elemen matriks mana saja pada baris paling atas. Dari elemen matriks yang berisi 0, bidak dapat bergerak ke bawah jika elemen matriks di bawahnya berisi 0; atau berpindah horizontal (kiri atau kanan) jika elemen di bawahnya berisi 1. Bila bidak berada pada elemen yang berisi 1, ia tidak dapat bergerak kemanapun. Tujuan permainan ini adalah mencapai elemen matriks yang mengandung 0 pada baris paling bawah.
| | 1 | 2 | 3 | 4 |
| 1 | 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 1 | 0 | 0 | 0 |
Gambar 6.11 Matriks bidak
Operator yang digunakan:
DOWN pindahkan bidak satu posisi ke bawah
LEFT pindahkan bidak satu posisi ke kiri
RIGHT pindahkan bidak satu posisi ke kanan
Batas kedalaman maksimum pohon ruang status diandaikan 5.
Tidak ada komentar:
Posting Komentar