Árvore k-d

Árvore k-d
Tipo	BST multidimensional
Ano	1975
Inventado por	Jon Bentley
Complexidade de Tempo em Notação big O

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.

Uma árvore k-d *3-dimensional*. A primeira divisão (o plano vermelho vertical) corta a célula raiz (branco), em duas subcélulas, cada um dos quais é então dividida (pelos planos verdes horizontais) em duas subcélulas. Finalmente, as quatro células são divididas (por quatro planos verticais azuis), em duas subcélulas. Uma vez que não há mais a divisão, as oito células finais são chamados de células folha.

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.^[1]

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

function arvoreKD (lista pointList, int profundidade)
{
    // Selecione o eixo com base na profundidade para que o eixo percorra todos os valores válidos
    var int eixo := profundidade mod k;

    // Ordena a lista de pontos e escolhe a mediana como elemento de pivô
    // Seleciona a mediana usando eixo

    mediana := selectMediana(eixo, pointList);

    // Cria o nó e constrói a subárvore
    node.location := mediana;
    node.filhoEsquerda := arvoreKD(pontos em pointList antes de mediana, profundidade+1);
    node.filhoDireita := arvoreKD(pontos em pointList depois de mediana, profundidade+1);
    return node;
}

O algoritmo acima implementado na linguagem de programação Python seria da seguinte forma:

from collections import namedtuple
from operator import itemgetter
from pprint import pformat

class Node(namedtuple('Node', 'location left_child right_child')):
    def __repr__(self):
        return pformat(tuple(self))

def kdtree(point_list, depth=0):
    try:
        k = len(point_list[0]) # assumes all points have the same dimension
    except IndexError as e: # if not point_list:
        return None
    # Select axis based on depth so that axis cycles through all valid values
    axis = depth % k

    # Sort point list and choose median as pivot element
    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2 # choose median

    # Create node and construct subtrees
    return Node(
        location=point_list[median],
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1:], depth + 1)
    )

def main():
    """Example usage"""
    point_list = [(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]
    tree = kdtree(point_list)
    print(tree)

if __name__ == '__main__':
    main()

O resultado seria:

((7, 2),
 ((5, 4), ((2, 3), None, None), ((4, 7), None, None)),
 ((9, 6), ((8, 1), None, None), None))

A árvore gerada é mostrada a seguir.

Decomposição da árvore k-d para o conjunto de pontos
(2,3), (5,4), (9,6), (4,7), (8,1), (7,2).

A árvore k-d resultante.

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.^[2] 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

Animação da busca VMP com uma árvore k-d em duas dimensões

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² 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 ^[3] 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.

Ver também

Octree, uma estrutura de particionamento do espaço que se divide em três dimensões simultaneamente, de modo que cada nó tem 8 filhos
Árvore R uma estrutura para particionamento de objetos ao invés de pontos, com a sobreposição de regiões
Árvore Vantage-point, uma variante da árvore k-d, que usa hiperesferas em vez de hiperplanos para particionar os dados

Referências

↑ Bentley, J. L. (1975). «Multidimensional binary search trees used for associative searching». Communications of the ACM (em inglês). 18 (9). 509 páginas. doi:10.1145/361002.361007
↑ Chandran, Sharat.
↑ 7. doi:10.1016/S0022-0000(73)80033-9

[1] Bentley, J. L. (1975). «Multidimensional binary search trees used for associative searching». Communications of the ACM (em inglês). 18 (9). 509 páginas. doi:10.1145/361002.361007

[2] Chandran, Sharat.

[blum-3] 7. doi:10.1016/S0022-0000(73)80033-9

[1]

[2]

[3]