QuadTree é uma estrutura de dados utilizada para armazenar dados espaciais, e tem como grande vantagem a compressão de dados (que especificamente iremos explorar aqui). Parece um pouco com a árvore binária, mas ao invés de cada nó ter dois filhos, tem quatro, como o nome sugere, e, enquanto a árvore binária pode mapear uma reta, a QuadTree pode ser usada para mapear um espaço 2D.
Funciona assim: suponha que você tem uma imagem no formato .pnm, que nada mais é do que é uma matriz de lado N com bits 1 ou 0, digamos N = 8.
Se a matriz está totalmente preenchida com 1s, não vale a pena armazenar 8x8 = 64 valores, basta um. Mas se temos uma matriz da forma:
