O que é um quadtree?
Um quadtree é uma estrutura semelhante a uma árvore com base no poder de quatro e usada para organizar arquivos em um banco de dados. Cada pai, ou nó de partida, ou inicial, possui quatro nós filhos e cada criança possui uma certa quantidade de dados. Quando o limite de dados derrama sobre seu limite, quatro crianças serão feitas a partir desse nó. Existem duas estruturas principais quadtree: a região e a árvore de pontos, cada uma ligeiramente diferente em design. Enquanto um quadtree é mais frequentemente usado com bancos de dados, ele 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. O pai é o ponto de partida e contém dados amplos baseados em categoria, enquanto a criança possui arquivos e documentos. Em um quadtree, todos os pais devem ter quatro filhos. Embora deva haver quatro filhos, nem todas as crianças precisam conter dados; Aqueles sem são conhecidos como nós nulos. Esses nós nulos geralmente permanecemestagnado e aguarde dados.
Cada nó infantil 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 ele vai além do limite, o nó infantil se torna um nó pai, dando à luz - criando quatro nós filhos que ocupam todos os dados extras. Geralmente haverá um ou dois nós nulos desta criação, mas isso depende inteiramente de quanta dados havia no nó.
Existem dois quadtres principais: região e ponto. O quadtree da região é usado para decompor uma região 2D inteira em peças com base no poder de quatro - como quatro, oito ou 16 partes - e frequentemente usado para representações. Essa estrutura é melhor para imagens ou gráficos de campo de dados. A versão Point é como uma árvore binária e é melhor usada com pontos ordenados. Esta variante também é uma árvore verdadeira, porque há um ponto central deque todos os nós mudam, ao contrário 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 feitos para encontrar um pixel específico em uma imagem geralmente usam quadtrees, porque cada pixel em uma imagem pode ser separado em quatro partes iguais. Isso faz com que os Quadtrees sejam adequados para pesquisar pixels.