Struktur DataMenengahFase D–FE1E5

Quadtree (Pembagian Ruang)

Quadtree adalah struktur data pohon yang membagi ruang 2D menjadi empat kuadran secara rekursif setiap kali sebuah wilayah memuat lebih dari satu titik. Proses subdivisi berhenti ketika tiap sel hanya berisi paling banyak satu titik. Visualisasi menunjukkan kotak yang terus terbelah menjadi empat bagian lebih kecil seiring titik-titik memaksa wilayah tersebut dipecah, beserta kedalaman (depth) pohon.

Contoh kasus

Deteksi tabrakan (collision detection) pada game 2D dengan mempartisi objek ke wilayah spasial agar pengecekan lebih efisien.

Silabus

Pohon yang membagi ruang 2D jadi empat kuadran berulang kali, memecah wilayah hanya saat memuat lebih dari satu titik.

Tujuan Belajar

·Memahami pembagian ruang 2D menjadi empat kuadran
·Menjelaskan kapan sebuah sel perlu dipecah lagi
·Menerapkan quadtree untuk mempercepat pengecekan spasial

Cara Kerja

·Mulai dari satu kotak besar yang meliputi seluruh ruang
·Bila sebuah wilayah memuat lebih dari satu titik, pecah jadi empat
·Tiap kuadran bisa dipecah lagi secara rekursif
·Subdivisi berhenti saat tiap sel berisi paling banyak satu titik
·Kedalaman pohon menunjukkan seberapa padat titik di area itu

Prasyarat

·Pohon
·Koordinat 2D
·Rekursi

Contoh Nyata

·Deteksi tabrakan di game 2D agar cek antar objek lebih hemat
·Peta digital yang memuat titik lokasi sesuai tingkat zoom

Kompleksitas O(log n) rata-rata per query