Struktur data: latihan soal dengan penjelasan

1Apa itu struktur data

Struktur data adalah cara mengatur data di memori agar operasi tertentu cepat: mencari item, menambah, menghapus.

Tidak ada struktur yang cepat untuk segalanya. Memilih satu berarti memilih operasi mana yang harus murah. Biayanya ditulis dalam Big O, dengan n jumlah item.

Dua blok pembangun dasar adalah larik dan linked list.

Larik menyimpan itemnya dalam satu blok memori, berurutan. Komputer dapat menghitung letak item i, sehingga membaca a[i] memerlukan O(1). Menyisipkan di depan berarti menggeser setiap item: O(n).

Linked list menyimpan setiap item dalam sebuah simpul dengan penunjuk ke simpul berikutnya. Penunjuk terakhir adalah null. Menyisipkan di kepala (h) hanya mengubah satu penunjuk: O(1). Tetapi untuk mencapai item i Anda harus mengikuti i penunjuk: O(n).

Linked list ganda juga memiliki penunjuk ke simpul sebelumnya, sehingga Anda dapat berjalan ke dua arah.

2Tumpukan dan antrean

Tumpukan (stack) seperti setumpuk piring: Anda menambah dan mengambil hanya di atas. Item terakhir yang masuk adalah yang pertama keluar: LIFO.

• push meletakkan item di atas, pop mengambil item teratas, peek membaca item teratas tanpa mengambilnya. Semuanya O(1).
• Kegunaan: fungsi undo pada editor, tumpukan panggilan program, memeriksa keseimbangan tanda kurung, pencarian depth-first.

Antrean (queue) seperti antrean di kasir: Anda bergabung di belakang dan keluar dari depan. Item pertama yang masuk adalah yang pertama keluar: FIFO.

• enqueue menambah di belakang, dequeue mengambil dari depan. Keduanya O(1).
• Kegunaan: pekerjaan cetak, pesan yang menunggu ditangani, pencarian breadth-first.

Deque (antrean berujung dua) memungkinkan penambahan dan pengambilan di kedua ujung. Antrean prioritas selalu mengambil item berprioritas tertinggi lebih dulu; biasanya dibangun sebagai heap.

3Pohon, heap, tabel hash, dan graf

Pohon memiliki satu simpul puncak, yaitu akar. Setiap simpul lain memiliki tepat satu induk. Simpul tanpa anak adalah daun. Pohon dengan n simpul memiliki n − 1 sisi.

Dalam pohon biner setiap simpul memiliki paling banyak dua anak. Pohon pencarian biner (BST) menambahkan aturan: kunci di subpohon kiri lebih kecil dari simpul, kunci di subpohon kanan lebih besar.

Mencari di BST mengikuti satu jalur ke bawah, jadi biayanya O(tinggi). Pohon seimbang (AVL, red-black) menjaga tinggi mendekati log₂ n. Kunci yang disisipkan berurutan membentuk rantai setinggi n.

Heap adalah pohon biner tempat setiap induk lebih kecil dari anak-anaknya (min-heap) atau lebih besar (max-heap). Minimum atau maksimum berada di akar, dan penyisipan serta penghapusan berbiaya O(log n).

Tabel hash menyimpan pasangan kunci–nilai. Sebuah fungsi hash mengubah kunci menjadi indeks, sehingga penyisipan dan pencarian rata-rata O(1). Dua kunci dengan indeks yang sama disebut tabrakan (collision), diatasi dengan chaining (satu list per slot) atau open addressing (mencoba slot lain).

Graf memiliki simpul (vertex) yang dihubungkan oleh sisi, yang dapat memiliki arah atau bobot. Graf disimpan sebagai matriks ketetanggaan, memori O(V²), atau sebagai daftar ketetanggaan, O(V + E).

4Metode ini selangkah demi selangkah

Soal sering menggambarkan sebuah tugas dan menanyakan struktur mana yang cocok, atau menanyakan seperti apa struktur setelah beberapa operasi.

1. Cari operasi yang harus cepat: akses berdasarkan posisi, berdasarkan kunci, item terbaru, item tertua, item terkecil, atau suatu rentang.
2. Cocokkan dengan struktur: indeks → larik, kunci → tabel hash, terbaru → tumpukan, tertua → antrean, terkecil atau terbesar → heap, urutan terurut atau rentang → pohon pencarian seimbang.
3. Periksa biaya operasi lain yang diperlukan tugas itu, dalam Big O.
4. Untuk soal penelusuran, jalankan operasi satu per satu dan tulis keadaan setelah masing-masing.
5. Periksa keadaan akhir terhadap aturan struktur: LIFO, FIFO, urutan BST, atau urutan heap.

5Contoh soal lengkap

Ikuti setiap langkah. Cobalah menebak langkah berikutnya sebelum membukanya.

6Kesalahan umum

• Mencampuradukkan LIFO dan FIFO. Tumpukan mengembalikan item terbaru, antrean item tertua.
• Mengira linked list memberi akses cepat berdasarkan indeks. Ia harus berjalan dari kepala.
• Mengira BST selalu O(log n). Hanya pohon seimbang yang demikian; penyisipan terurut menghasilkan O(n).
• Melupakan tabrakan pada tabel hash. O(1) adalah rata-rata, bukan kasus terburuk.
• Mencampuradukkan penelusuran. Preorder: simpul lebih dulu. In-order: simpul di tengah. Postorder: simpul terakhir.
• Memakai matriks ketetanggaan untuk graf jarang yang besar. Itu memboroskan memori O(V²).

7Seperti apa soal ujiannya

• Mudah: istilah dan fakta kunci. LIFO dan FIFO, apa itu simpul, akar, atau daun, aturan BST, apa yang dilakukan fungsi hash.
• Sedang: menerapkan konsep. Struktur mana yang cocok untuk suatu tugas, hasil push dan pop atau penyisipan BST, penelusuran pohon, tabel hash dengan linear probing, biaya dalam Big O.
• Sulit: kasus dan analisis. Pohon seimbang, heap dalam larik, B-tree, trie, union-find, Bloom filter, dan rancangan seperti LRU cache.

Untuk heap yang disimpan dalam larik dari indeks 0, anak-anak indeks i berada di 2i + 1 dan 2i + 2, dan induknya di ⌊(i − 1) / 2⌋.