O que é um Quadtree?
Um quadtree é uma estrutura em forma de árvore, baseada na capacidade de quatro e usada para organizar arquivos em um banco de dados. Cada nó pai ou inicial tem quatro nós filhos e cada filho possui uma certa quantidade de dados. Quando o limite de dados ultrapassa seu limite, quatro filhos serão criados a partir desse nó. Existem duas estruturas principais de quadtree: a região e a árvore de pontos, cada uma com um design ligeiramente diferente. Enquanto um quadtree é mais frequentemente usado com bancos de dados, também pode ser usado para encontrar pixels em imagens bidimensionais (2D), porque os pixels em uma imagem 2D sempre podem ser separados em quatro partes.
Todas as estruturas semelhantes a árvores são feitas com nós pai ou ramo, nós e filho ou folha. O pai é o ponto de partida e contém dados amplos baseados em categorias, enquanto o filho mantém arquivos e documentos. Em um quadtree, todo pai deve ter quatro filhos. Embora deva haver quatro filhos, nem todos os filhos precisam conter dados; aqueles sem são conhecidos como nós nulos. Esses nós nulos geralmente permanecem estagnados e aguardam dados.
Cada nó filho em um quadtree tem um limite de dados. Esse limite geralmente é definido pelo tamanho geral do banco de dados. Quando há tanta informação que vai além do limite, o nó filho se torna um nó pai essencialmente dando à luz - criando quatro nós filhos que ocupam todos os dados extras. Geralmente, haverá um ou dois nós nulos dessa criação, mas isso depende inteiramente da quantidade de dados no nó.
Existem dois quadríceps principais: região e ponto. O quadtree da região é usado para decompor uma região 2D inteira em partes com base na potência de quatro - como quatro, oito ou 16 partes - e frequentemente usada para representações. Essa estrutura é melhor para imagens ou gráficos de campo de dados. A versão do ponto é como uma árvore binária e é melhor usada com pontos ordenados. Essa variante também é uma árvore verdadeira, porque existe um ponto central a partir do qual todos os nós brotam, diferentemente da versão da região na qual os nós estão espalhados.
O uso mais comum do quadtree é separar e organizar um banco de dados, mas esse não é o seu único uso. Os algoritmos criados para encontrar um pixel específico em uma imagem geralmente usam quadríceps, porque cada pixel em uma imagem pode ser separado em quatro partes iguais. Isso torna os quadríceps adequados exclusivamente para a busca de pixels.