Technology Tree
Intermezzo:Kalau kalian pernah bermain game berjenis Real Time Strategy (RTS), mungkin tahu tentang konsep "technology tree". Biasanya Anda akan memainkan satu peradaban yang dimulai dengan teknologi seadanya. Seiring dengan berjalannya waktu, Anda dapat melakukan riset untuk memajukan teknologi dan meningkatkan produktivitas. Ditemukannya suatu teknologi juga memungkinkan pembuatan sejumlah teknologi lain. Contohnya pada game Age of Empires, pembuatan kandang hewan akan memungkinkan dibuatnya cavalry dan pemanah berkuda.Oke cukup dengan cerita game. Pembelajaran struktur data pun dapat digambarkan seperti sebuah technology tree. Mempelajari suatu struktur data memungkinkan Anda untuk belajar sejumlah struktur data lainnya. Berikut adalah gambarannya:
 |
| Klik untuk memperbesar gambar. |
Semuanya dimulai dengan array. Dengan array polos, kita dapat melakukan apa saja walaupun secara kurang efektif. Lalu saya tidak mengikutkan keluarga struktur data linear seperti stack/queue/deque, dan juga keluarga heap.
Anak panah menunjukkan bahwa setelah mempelajari suatu konsep (struktur data/teknik), Anda dapat beranjak ke konsep yang lebih lanjut.
Berikut penjelasan singkat struktur data sesuai nomor pada gambar:
1. Sparse Table
Digunakan untuk mencari menjawab pencarian minimum/maksimum dalam suatu rentang. Idenya adalah membuat tabel DP yang menyimpan nilai minimum/maksimum untuk k elemen yang bersebelahan, dengan k=1, 2, 4, 8, 16, ....
Kompleksitas pembuatan struktur datanya O(N log N), dan kompleksitas menjawab pertanyaannya O(1). Meskipun query-nya sangat cepat, sparse table tidak mendukung operasi update dan kegunaannya cukup terbatas,
Saya mempelajari struktur data ini dari Felik dan Topcoder.
Variasi dari sparse table:
- Untuk menjawab pertanyaan dengan ukuran rentang yang sama.
- Untuk mendapatkan nilai elemen ke-k dalam O(log N)
2. SQRT Decomposition (Segment Array)
Serba bisa untuk menjawab macam-macam pertanyaan. Idenya adalah memecah array N elemen menjadi potongan-potongan array berukuran sqrt(N). Kemudian untuk setiap potongan, dicari nilai agregat dari seluruh elemennya. Struktur data ini relatif mudah untuk diimplementasikan dan konsepnya sangat sederhana.
Kompleksitas pembuatannya O(N) dan kompleksitas menjawab pertanyaannya O(sqrt(N)).
Saya belajar ini dari blog Pak Suhendry tentang segment array.
3. Segment Tree
Struktur data serba bisa yang menjadi dasar ilmu beberapa struktur data lainnya. Rasanya ini yang paling penting untuk dikuasai. Kompleksitas pembuatannya O(N), menjawab pertanyaannya O(log N), dan update elemennya O(log N).
Pelajari segment tree di tulisan saya tentang petunjuk coding segment tree.
Dapat di-upgrade untuk mendukung operasi lazy, menjadi persistent, atau menjadi range tree.
4. Binary Indexed Tree (BIT)
Struktur data yang biasanya digunakan untuk mendukung:
- Range query dari elemen pertama sampai suatu elemen ke-x dalam O(log N)
- Update suatu elemen dalam O(log N)
Kecepatan coding dan running-time-nya membuat struktur data ini penting dalam kompetisi sejenis ICPC.
Saya belajar BIT pada Pelatnas 2 dari Ashar dan Aji.
Ilmunya saya tuliskan di tulisan tentang BIT.
5. Binary Search Tree (BST)
Mendukung operasi insert, delete, dan find dalam O(log N).
Berbeda dengan update, operasi insert/delete bersifat menyisipkan/membuang elemen. Jadi indeks elemen dapat bergeser. Konsep BST diimplementasikan pada STL C++ yang bernama "set" dan "map".
Dalam pemrograman kompetitif, implementasi BST saja tidak cukup. Biasanya ada kasus yang membuat BST menjadi timpang, sehingga kompleksitas operasinya mendekati O(N). Diperlukan algoritma yang dapat menyeimbangkan BST, menjadi BBST (Balanced Binary Search Tree). Keberadaan algoritma itu menghasilkan varian BBST seperti AVL Tree, Red Black Tree, Treap, atau Splay Tree.
Bila Anda ingin tahu tentang BST yang polos, kunjungi Wikipedia.
Dengan sedikit modifikasi, BST dapat digunakan seperti segment tree.
6. Lowest Common Ancestor (LCA)
Ketika data yang diberikan berupa tree, kita dapat mencari leluhur terakhir dari sepasang node dalam O(log N). Implementasinya dapat menggunakan sparse table. Kalau mau repot sedikit, reduksi RMQ dapat membuat kompleksitas pencariannya O(1).
Pengetahuan tentang LCA diperlukan baik untuk tingkat IOI maupun ICPC. Saya belajar LCA lewat Topcoder.
7. MO's Algorithm
Konsep dekomposisi sqrt(N) dapat diterapkan pada query-nya. Kompleksitas akhir per query menjadi amortized O(sqrt(N)). Algoritma ini dapat digunakan ketika nilai agregat yang perlu disimpan dalam segment tree terlalu besar (misal: tabel frekuensi kemunculan seluruh elemen).
Saya baru tahu algoritma ini setelah lulus dari TOKI. Penjelasannya bisa ditemukan di blog Reynaldo.
8. Lazy Segment Tree
Upgrade dari segment tree yang memungkinkan node-nodenya hanya dibuat saat diperlukan.
Efektif digunakan ketika ukuran arraynya sangat besar (mencapai milyaran) tetapi hanya beberapa elemen saja yang akhirnya disentuh. Kalau pertanyaan-pertanyaannya dapat dikumpulkan semua lalu dijawab pada akhir pemrosesan, sebenarnya kita dapat menggunakan grid compression.
Saya bahas tentang lazy segment tree lewat tulisan berikut.
9. Lazy Propagation
Upgrade dari segment tree untuk melayani range update dalam O(log N).
Konsepnya adalah menunda update dan menyimpan informasi penundaan itu pada node. Ketika anak-anak node itu diperlukan, barulah operasi update diturunkan ke anak-anaknya.
Saya membahasnya secara lengkap di tulisan tentang segment tree lazy propagation.
10. Range Tree
Upgrade dari segment tree untuk melayani operasi untuk titik-titik data pada ruang d-dimensi. Setiap operasi dilayani dalam O(logd N).
Saya ada membahas tentang range tree lewat tulisan ini.
11. Persistent Segment Tree
Lagi-lagi upgrade dari segment tree untuk mengingat seluruh kedudukan data setiap sebelum update. Biasanya digunakan untuk melayani pertanyaan "sebelum update yang ke-k, apakah nilai dari elemen ke-a sampai elemen ke-b?".
Konsep persistent segment tree sebenarnya cukup sederhana, yaitu membuat segment tree baru setiap sesudah operasi update. Namun, sebagian besar node-nya menggunakan node-node pada versi sebelumnya. Setiap ada operasi update, perlu ditambahkan O(log N) node. Kompleksitas operasi update/query tetaplah O(log N). Saya membahasnya di sini.
12. Range Update BIT
Walaupun idenya agak rumit, BIT dapat digunakan untuk range update.
Kelebihan dan kekurangannya masih mengikuti BIT secara umum.
Pembahasannya ada di sini.
13. AVL Tree
14. Red-Black Tree
AVL dan Red-Black adalah BBST yang populer untuk digunakan dalam pemrograman kompetitif.
Konsepnya dengan rotasi struktur ketika ketimpangan dideteksi.
Kini operasi insert, delete, dan find dijamin memiliki kompleksitas O(log N).
Saya tidak pernah membahasnya di blog ini, karena kekurangan kedua varian BBST ini memiliki kode yang relatif panjang.
15. Treap
Varian BBST yang lebih saya sukai karena implementasinya relatif pendek.
Konsepnya dengan prioritas yang dibuat secara acak, sehingga struktur datanya bersifat randomized. Prioritas ini membuat kompleksitas insert, delete, dan find memiliki kompleksitas expected O(log N).
Pembahasannya pernah saya tulis di sini.
16. Splay Tree
Varian BBST yang menurut saya pendekatannya cukup radikal.
Terdapat sebuah operasi tambahan bernama "splay". Operasi splay untuk nilai x akan membawa node dengan nilai x (atau yang terdekat dengan x bila tidak ada) ke root BST melalui serangkaian rotasi. Untuk melayani insert/delete/find untuk nilai x, awali dulu dengan splay x. Selanjutnya cukup dilihat apa nilai di root BST.
Dengan perhitungan matematis yang rumit, kompleksitas insert, delete, dan find dibuktikan memiliki kompleksitas amortized O(log N).
Sebenarnya operasi splay yang cukup radikal ini sangat berguna. Membawa sembarang node ke root tanpa merusak struktur urutan BST dapat memudahkan algoritma lainnya. Kemudahan ini dimanfaatkan oleh struktur data link-cut tree.
Saya belum pernah menulis tentang splay tree di blog ini, tapi pernah untuk perkuliahan.
Penjelasannya dapat Anda baca di Wikipedia.
17. Heavy-Light Decomposition (HLD)
Digunakan ketika dihadapkan pada tree yang masing-masing node-nya menyimpan suatu nilai. Kemudian Anda diminta mencari nilai agregat dari path suatu node ke node lainnya.
Pengetahuan tentang LCA dapat diterapkan pada HLD, yang mendekomposisi suatu tree menjadi serangkaian segmen linear. Masing-masing segmen linear ini dapat dijadikan segment tree. Dijamin bahwa untuk setiap pasang node, pathnya hanya terdiri dari O(log N) segmen saja. Jika kita menerapkan operasi segment tree pada masing-masing segmen, berarti kompleksitas akhir sebuah operasinya O(log2 N).
Pelajari konsepnya di sini.
18. Composite Tree
Sebenarnya composite tree mengacu pada tree yang didalamnya diisi tree lainnya. Contohnya BIT yang diisi dengan Treap. Setelah menguasai tentang range tree, Anda dapat meng-upgrade-nya menjadi lebih umum. Treenya kini dapat dibuat dan diisi dengan apa saja.
Baca tulisannya tentang komposisi tree di sini.
19. Fractional Cascading
Merupakan teknik lanjutan untuk mengoptimasi range tree. Kompleksitas operasi untuk data 2 dimensi dapat menjadi O(log N) saja. Penjelasannya dapat dibaca di blog orang ini.
20. Link-Cut Tree
Sepertinya struktur data paling kompleks yang pernah saya jumpai.
Diberikan sebuah kumpulan tree (forest). Struktur data ini mendukung operasi:
- link(u, v): hubungkan node u dan v dengan edge (diketahui u dan v belum terhubung)
- cut(u, v): buang edge u dan v
- find_root(u): cari root node dari subtree yang mengandung u
- aggregate(u, v): cari nilai agregat yang disimpan oleh path dari node u sampai node v
Latihan
Berhubung banyak orang yang tertarik dengan beragam struktur data tersebut, banyak forum-forum yang mengumpulkan daftar soalnya. Berikut apa yang saya temukan dan dapat Anda gunakan untuk berburu soal latihan:- https://codeforces.com/blog/entry/22616
- https://a2oj.com/contest?ID=5254
- http://praveendhinwacoding.blogspot.com/2013/06/700-problems-to-understand-you-complete.html
Penutup
Disarankan untuk menyimpan catatan berupa implementasi struktur data yang pernah Anda buat. Sepengalaman saya, mudah sekali untuk lupa bagaimana cara coding struktur data tertentu. Lagipula, biasanya hanya terdapat sedikit perbedaan pada bagian agregasi data saja. Catatan ini dapat Anda bawa jika Anda ikut kompetisi seperti ICPC.
Semoga tulisan ini membantu Anda untuk tahu arah berlatih struktur data. Semoga sukses!
Semoga tulisan ini membantu Anda untuk tahu arah berlatih struktur data. Semoga sukses!
Tidak ada komentar :
Posting Komentar