Drzewo czwórkowe

Drzewo czwórkowe (ang. quadtree) to w informatyce 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 itd.

Jest używana na przykład w wykrywaniu kolizji w dwóch wymiarach. Umożliwia szybkie odrzucenie dużych przestrzeni – gdy wie się, że któraś ćwiartka nie ma kolizji z jakimś obiektem, jej podćwiartki też nie mają kolizji. Drzewa czwórkowe znalazły również zastosowanie w kompresji bitmap dwukolorowych (czarno-białych) - obraz jest dzielony na mniejsze części dopóki nie będą one jednokolorowe, a wtedy wystarczy zapisać kolor kwadratu (na co potrzeba pojedynczego bitu).

Bitmapa reprezentowana przez drzewo czwórkowe

Trójwymiarowym odpowiednikiem drzew czwórkowych są drzewa ósemkowe.