Apa itu pohon quad?

Pohon quad, kadang-kadang quadtree, Q-tree atau QT, adalah istilah ilmu komputer yang mengacu pada metode pengorganisasian data di empat kuadran.Basis data terkadang menggunakan pohon quad untuk menyimpan dan menemukan catatan mereka.Jenis struktur organisasi ini bekerja sangat baik untuk menemukan bit atau piksel tertentu dalam gambar dua dimensi.

Pohon quad agak mengikuti struktur data pohon yang biasa digunakan dalam ilmu komputer.Struktur data pohon normal terlihat seperti pohon terbalik, di mana node induk di bagian atas pohon memiliki satu atau lebih node anak yang terhubung dengannya.Setiap simpul lain pada pohon memiliki satu node induk dan dapat memiliki sejumlah node anak, termasuk nol.

Tidak seperti struktur data pohon normal, struktur pohon quad mensyaratkan bahwa setiap node internal memiliki tepat empat anak node.Saat mengilustrasikan sebagian besar struktur pohon quad, Anda akan melihat sebuah simpul yang memiliki empat anak node tergantung darinya, dengan garis -garis yang menghubungkan simpul induk dengan node anak -anaknya.Ilustrasi dapat berlanjut, dengan empat anak lagi tergantung dari masing -masing dari empat node anak asli.

Lainnya, ilustrasi pohon quad akan menjadi wilayah atau persegi.Setiap kali wilayah mencapai kapasitas maksimum untuk menyimpan data, ia dibagi menjadi empat kuadran.Biasanya, daerah dan kuadran adalah kotak, meskipun mereka bisa persegi panjang atau bentuk lainnya juga.

Pohon quad adalah struktur data yang baik untuk mengatur piksel dalam foto dan untuk mengatur grafik komputer.Gambar dapat dibagi menjadi kuadran, dan setiap kuadran dapat dibagi menjadi empat lagi.Ini dapat diulang lagi dan lagi sampai Anda mencapai tingkat piksel individu.Jika kuadran berisi piksel yang semuanya memiliki warna yang sama, bagaimanapun, tidak ada alasan untuk membagi kuadran lebih lanjut.

Meskipun data yang disimpan dalam struktur pohon quad dapat memerlukan banyak ruang penyimpanan dibandingkan dengan metode lain untuk mengatur data untuk grafik komputer, struktur pohon quad memiliki beberapa keunggulan.Pertama, Anda dapat menghapus seluruh foto atau grafik dalam satu langkah dengan membersihkan node root, yang juga membersihkan semua node anak -anaknya.Kedua, Anda dengan cepat dapat mengurangi resolusi dalam sebuah foto dengan hanya membersihkan tingkat akhir dari node anak -anak.Dengan demikian ini akan mengurangi jumlah ruang penyimpanan yang dibutuhkan.Akhirnya, menemukan area tertentu dari foto untuk manipulasi gambar lebih mudah dengan struktur pohon quad.

Pohon quad digunakan dalam beberapa situasi lain, juga, termasuk pengindeksan spasial.Meskipun pohon quad terbatas pada gambar dua dimensi, mewakili gambar tiga dimensi dapat mengikuti struktur yang sama, yang disebut octree, yang merupakan subdivisi kubus menjadi delapan anak.