Drzewo czwórkowe
Drzewo czwórkowe (ang. quadtree) – struktura danych będąca drzewem, używana do podziału dwuwymiarowej przestrzeni na mniejsze części, dzieląc ją na cztery równe ćwiartki, a następnie każdą z tych ćwiartek na cztery kolejne itd.
Jest używana na przykład w procesie wykrywania kolizji w dwóch wymiarach. Umożliwia szybkie odrzucenie dużych przestrzeni – gdy zostanie stwierdzone, że któraś ćwiartka nie ma kolizji z danym obiektem, jej podćwiartki też nie mają z nim kolizji. Drzewa czwórkowe znalazły również zastosowanie w kompresji bitmap dwukolorowych (czarno-białych), gdzie obraz dzielony jest na mniejsze części dopóki nie będą one jednokolorowe, a wtedy wystarczy tylko zapisać kolor tego kwadratu, na co wystarcza pojedynczy bit.
Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe.