Quad tree, joskus quadtree, Q-tree tai QT, on tietojenkäsittelytieteen termi, joka viittaa menetelmään tietojen järjestämiseksi neljässä neljänneksessä. Tietokannat käyttävät joskus nelipuita tallentaakseen ja löytääkseen tietueensa. Tämäntyyppinen organisaatiorakenne toimii erityisen hyvin löytääkseen tietyn bitin tai pikselin kaksiulotteisesta kuvasta.
Nelipuu seuraa jonkin verran tietotekniikassa yleisesti käytettyä puurakennetta. Normaali puun tietorakenne näyttää ylösalaisin olevasta puusta, jossa puun yläosassa olevassa vanhemmassa solmussa on yksi tai useampi alisolmu kytketty siihen. Kaikilla muilla puun solmuilla on yksi vanhempi solmu ja niillä voi olla mikä tahansa määrä alisolmuja, mukaan lukien nolla.
Toisin kuin tavallinen puun tietorakenne, nelipuurakenne edellyttää, että jokaisella sisäisellä solmulla on täsmälleen neljä alisolmua. Kun havainnollistat useimpia nelipuurakenteita, näet solmun, jossa on neljä alisolmua riippuvaa, ja viivat, jotka yhdistävät vanhemman solmun sen alisolmuihin. Kuva voi jatkua, ja neljä muuta lapsisolmua roikkuu kustakin alkuperäisestä neljästä lapsisolmusta.
Muina aikoina nelipuun kuva on alue tai neliö. Aina kun alue saavuttaa suurimman kapasiteetin tietojen tallentamiseen, se jaetaan neljään neljännekseen. Normaalisti alueet ja kvadrantit ovat neliöitä, vaikka ne voivat olla myös suorakulmioita tai muita muotoja.
Nelipuu on hyvä tietorakenne pikselien järjestämiseen valokuvaan ja tietokonegrafiikan järjestämiseen. Kuva voidaan jakaa neljänneksiin ja jokainen neljännes neljään. Tämä voidaan toistaa uudestaan ja uudestaan, kunnes saavutat yksittäisten pikselien tason. Jos kvadrantti sisältää pikseleitä, jotka ovat kaikki samanvärisiä, ei kuitenkaan ole syytä jakaa kvadranttia edelleen.
Vaikka nelipuurakenteeseen tallennetut tiedot voivat vaatia paljon tallennustilaa verrattuna muihin menetelmiin tietojen järjestämiseksi tietokonegrafiikkaa varten, nelipuurakenteella on useita etuja. Ensinnäkin voit poistaa koko valokuvan tai grafiikan yhdessä vaiheessa tyhjentämällä juurisolmun, joka tyhjentää myös kaikki sen alisolmut. Toiseksi voit nopeasti pienentää valokuvan resoluutiota yksinkertaisesti tyhjentämällä lapsen solmujen lopullisen tason. Tämä vähentää tarvittavan tallennustilan määrää. Lopuksi tietyn alueen löytäminen valokuvasta kuvankäsittelyä varten on helpompaa nelipuurakenteella.
Nelospuita käytetään myös muutamissa muissa tilanteissa, mukaan lukien paikkatietoindeksointi. Vaikka nelipuut rajoittuvat kaksiulotteisiin kuviin, kolmiulotteisen kuvan esittäminen voi noudattaa samanlaista rakennetta, jota kutsutaan oktreeksi, joka on kuution osa kahdeksaan lapseen.