# Árvore k-d

Em ciência da computação, uma árvore k-d (abreviação para a árvore k-dimensional) é uma estrutura de dados de particionamento do espaço para a organização de pontos em um espaço k-dimensional. Árvores k-d são estruturas úteis para uma série de aplicações, tais como pesquisas envolvendo pesquisa multidimensional de chaves (e.g. busca de abrangência e busca do vizinho mais próximo). Árvores k-d são um caso especial de árvores de particionamento binário de espaço.

## Descrição Informal

Uma árvore k-d é uma árvore binária em que cada nó é um ponto k-dimensional. Cada nó não-folha pode ser considerado implicitamente como um gerador de um hiperplano que divide o espaço em duas partes, conhecido como semiespaço. Os pontos à esquerda do hiperplano são representados pela subárvore esquerda desse nó e pontos à direita do hiperplano são representados pela subárvore direita. A direção do hiperplano é escolhida da seguinte maneira: cada nó na árvore é associado a uma das k-dimensões, com o hiperplano perpendicular a esse eixo dimensional. Assim, por exemplo, se para uma determinada operação de split o eixo "x" é escolhido, todos os pontos da subárvore com um valor "x" menor que o nó irão aparecer na subárvore esquerda e todos os pontos com um valor "x" maior vão estar na subárvore direita. Nesse caso, o hiperplano seria definido pelo valor de x do ponto, e o seu normal seria a unidade do eixo x.

## Operações em árvores k-d
### Construção

Uma vez que existem muitas maneiras possíveis de escolher planos de divisão alinhados com o eixo, existem muitas maneiras diferentes de construir árvores k-d. O método canônico da construção de uma árvore k-d possui as seguintes restrições:
* À medida que se desce pela árvore, ciclos através dos eixos são usados para selecionar os planos de divisão. (Por exemplo, em uma árvore 3-dimensional, a raiz deveria ter um plano alinhado em x, os filhos da raiz teriam ambos os planos alinhados em y, os netos da raiz teriam todos planos alinhados em z, os bisnetos da raiz teriam planos alinhados em x, os trinetos da raiz teriam planos alinhados em y, e assim por diante).
* Em cada etapa, o ponto selecionado para criar o plano de corte será a mediana dos pontos colocados na árvore k-d, o que respeita suas coordenadas no eixo que está sendo usado.
Este método conduz a uma árvore k-d balanceada, em que cada nó folha está aproximadamente a mesma distância da raiz. No entanto, árvores balanceadas não são necessariamente ótimas para todas as aplicações.
Note que não é necessário seleccionar o ponto mediano. No caso dos pontos medianos não serem selecionados, não há nenhuma garantia de que a árvore vai estar balanceada. Para evitar a implementação de um complexo algoritimo de seleção de mediana O(n) ou usar um Heapsort ou Mergesort, O(n log n), para ordenar todos os n pontos, uma prática comum é ordenar um número fixo de pontos aleatoriamente selecionados, e usar a mediana desses pontos, para servir como o plano divisor. Na prática, esta técnica muitas vezes resulta em árvores bem balanceadas.
Dada uma lista de n pontos, o algoritmo a seguir gera uma árvore k-d balanceada contendo estes pontos.
Pseudocódigo
O algoritmo acima implementado na linguagem de programação Python seria da seguinte forma:
O resultado seria:
A árvore gerada é mostrada a seguir.
Este algoritmo cria o invariante que, para qualquer nó, todos os nós da subárvore à esquerda estão em um lado do plano divisor, e todos os nós da subárvore à direita estão do outro lado. Os pontos que se situam no plano divisor podem aparecer em ambos os lados. O plano divisor de um nó passa pelo ponto associado a esse nó (referido no código como node.location).

### Inserção

A adição em uma árvore k-d se é feita da mesma forma que qualquer outra árvore de busca. Primeiro, atravessa-se a árvore a partir da raiz move-se para a o filho à esquerda ou para a direita, dependendo se o ponto a ser inserido deve estar na "esquerda" ou "direita" do plano divisor. Uma vez que você chegar ao nó em que o filho deve estar localizado, adicione o novo ponto como filho à esquerda ou à direita do nó folha, de novo, dependendo de que lado do plano divisor contém o novo nó.

### Remoção

Para remover um ponto em uma árvore k-d tree, uma abordagem é encontrar um substituto para o ponto removido. Primeiro, localize o nó de R que contém o ponto a ser removido. Para o caso base, onde R é um nó folha, a substituição não é necessária, e R pode ser removido. Para o caso geral, encontre um ponto substituto chamado p, a partir de uma subárvore com raiz em R. Substitua o ponto armazenado em R com p. Em seguida, remova recursivamente p.
Para encontrar um ponto substituto x, se R tem um filho à direita, encontre o ponto mínimo x a partir da subárvore da direita. Caso contrário, encontre o ponto máximo de x a partir da subárvore enraizada na esquerda.

### Busca do vizinho mais próximo

O algoritimo de busca do vizinho mais próximo (VMP) visa encontrar o ponto na árvore que está mais próximo de um determinado ponto de entrada. Essa pesquisa pode ser feita de forma eficiente, utilizando as propriedades da árvore para eliminar rapidamente grandes porções do espaço de busca.

## Complexidade

* A construção de uma árvore k-d estática a partir de n pontos, tem as seguintes complexidade no pior-caso:
** O(n log$^2$ n) caso um algoritimo de ordenação O(n log n) como Heapsort ou Mergesort seja usado para encontrar a mediana em cada nível da árvore;
** O(n log n) se uma algoritimo O(n) de mediana-das-medianas for usado para selecionar a mediana em cada nível da árvore;
** O(kn log n) se os n pontos forem pré-ordenados em cada uma das k dimensões usando um algoritimo O(n log n) como Heapsort ou Mergesort antes de construir a árvore k-d.
* A inserção de um novo ponto em uma árvore k-d balanceada leva O(log n) em tempo.
* A remoção de um ponto em uma árvore k-d balanceada leva O(log n) em tempo.
* A procura de 1 vizinho mais próximo em uma árvore k-d balanceada com pontos distribuídas aleatoriamente leva o tempo O(log n), em média.