K-d tree (árvore k-d): o que é e quando usar

Letra

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

← Todos os termos do ABC da IA