Mis on Quad Tree?

Nelikpuu, mõnikord neljapuu, Q-puu või QT, on arvutiteaduse termin, mis viitab andmete korraldamise meetodile neljas kvadrandis. Andmebaasid kasutavad mõnikord oma kirjete salvestamiseks ja leidmiseks neljapuid. Seda tüüpi organisatsiooniline struktuur töötab eriti hästi konkreetse biti või piksli leidmiseks kahemõõtmeliselt pildilt.

Nelikpuu järgib mõnevõrra arvutiteaduses tavaliselt kasutatavat puu andmestruktuuri. Tavaline puu andmestruktuur näeb välja nagu tagurpidi puu, kus puu ülaosas asuva emasõlmega on ühendatud üks või mitu alamsõlme. Puu igal teisel sõlmel on üks ülemsõlm ja sellel võib olla suvaline arv alamsõlme, sealhulgas null.

Erinevalt tavalisest puu andmestruktuurist nõuab neljapuustruktuur, et igal sisemisel sõlmel oleks täpselt neli alamsõlme. Enamiku neljapuustruktuuride illustreerimisel näete sõlme, millel on neli alamsõlme, mille küljes on rippuvad jooned, mis ühendavad emasõlme ja selle alamsõlme. Illustratsiooni võib jätkata, kusjuures iga algse nelja alamsõlme küljes ripub veel neli alamsõlme.

Muul ajal on quad puu illustratsiooniks piirkond või ruut. Kui piirkond saavutab maksimaalse andmete salvestamise mahu, jagatakse see neljaks kvadrandiks. Tavaliselt on piirkonnad ja kvadrandid ruudud, kuigi need võivad olla ka ristkülikud või muud kujundid.

Nelikpuu on hea andmestruktuur fotol pikslite korrastamiseks ja arvutigraafika korrastamiseks. Pildi saab jagada kvadrantideks ja iga kvadrandi saab jagada veel neljaks. Seda saab korrata ikka ja jälle, kuni jõuate üksikute pikslite tasemeni. Kui kvadrand sisaldab piksleid, mis on kõik sama värvi, ei ole põhjust seda kvadrandit edasi jagada.

Kuigi neljapuustruktuuris salvestatud andmed võivad nõuda palju salvestusruumi võrreldes muude arvutigraafika andmete korraldamise meetoditega, on neljapuustruktuuril mitmeid eeliseid. Esiteks saate kustutada kogu foto või graafika ühe sammuga, tühjendades juursõlme, mis kustutab ka kõik selle alamsõlmed. Teiseks saate kiiresti vähendada foto eraldusvõimet, eemaldades lihtsalt laste sõlmede lõpptaseme. See vähendab seega vajaliku salvestusruumi hulka. Lõpuks on neljapuustruktuuri abil lihtsam leida fotol teatud ala pilditöötluseks.
Quad puid kasutatakse ka mõnes muus olukorras, sealhulgas ruumilise indekseerimise puhul. Kuigi neljamõõtmelised puud on piiratud kahemõõtmeliste kujutistega, võib kolmemõõtmelise kujutise kujutamine järgida sarnast struktuuri, mida nimetatakse oktpuuks, mis on kuubiku jagamine kaheksaks lapseks.