Atualizado em 25/10/2026: verbete refeito: definição curta com fonte, exemplo e termos relacionados; saiu o texto genérico anterior. Como conferimos os dados
A k-d tree (k-dimensional tree, árvore k-dimensional) é uma estrutura de dados em árvore binária que divide o espaço repetidamente ao longo dos eixos dos dados. Serve para encontrar os vizinhos mais próximos de um ponto sem calcular a distância até todos os outros. Foi descrita por J. L. Bentley em 1975.
Por que é rápida
Na busca por força bruta, é preciso medir a distância do ponto consultado até cada ponto dos dados. Com a árvore pronta, segundo a documentação do scikit-learn, o vizinho mais próximo é achado com cerca de log(N) cálculos de distância. E montar a árvore é rápido, porque as divisões seguem os eixos.
Limite
Funciona muito bem com poucas dimensões (a documentação cita menos de 20) e perde eficiência quando o número de dimensões cresce muito: um caso da chamada maldição da dimensionalidade.
Exemplo
Um jogo guarda a posição (x, y) de 100 mil objetos num mapa (2 dimensões). Para achar os 5 mais próximos do personagem, a k-d tree evita medir as 100 mil distâncias. No scikit-learn: KDTree ou algorithm='kd_tree'.
Termos relacionados
Fontes (conferidas em 02/10/2026): scikit-learn: vizinhos mais próximos (K-D Tree) · scikit-learn: KDTree