Melhor resposta
Diferença entre a estrutura de dados do gráfico e da árvore:
Gráfico
- No gráfico, pode haver mais de um caminho, ou seja, o gráfico pode ter caminhos unidirecionais ou bidirecionais entre os nós.
- No gráfico não existe tal conceito de raiz nó.
- O gráfico pode ter loops, circuitos e também pode ter auto-loops.
- No gráfico não existe tal relação pai-filho.
- Os gráficos são mais complexos em comparação com as árvores, pois podem ter ciclos, loops, etc.
- O gráfico é percorrido por DFS : Primeira pesquisa de profundidade e em BFS : algoritmo de primeira pesquisa em amplitude.
- O gráfico pode ser cíclico ou acíclico.
- Existem principalmente dois tipos de gráficos: gráficos direcionados e não direcionados.
- Aplicativo gráfico lications: Coloração de mapas, algoritmos, coloração de gráfico, agendamento de trabalho etc. das arestas dependem do gráfico.
- O gráfico é um modelo de rede.
Árvores
- Árvore é uma forma especial de gráfico, ou seja, gráfico minimamente conectado e tendo apenas um caminho entre dois vértices.
- Árvore é um caso especial de gráfico sem loops, circuitos e sem loops automáticos.
- Na árvore há exatamente uma raiz nó e cada filho tem apenas um pai.
- Nas árvores, há relacionamento pai-filho para que o fluxo possa estar presente com direção de cima para baixo ou vice-versa.
- As árvores são menos complexas do que os gráficos, pois não têm ciclos, nem loops automáticos e ainda estão conectados.
- A travessia da árvore é um tipo de caso especial de travessia do gráfico. A árvore é percorrida em Pré-encomenda , Em ordem e Pós-pedido (todos os três em DFS ou em BFS algoritmo)
- Árvores vêm na categoria de DAG: Gráficos acíclicos direcionados são um tipo de gráfico direcionado que não tem ciclos.
- Diferentes tipos de árvores são: Árvore binária , Árvore de pesquisa binária, árvore AVL, Heaps.
- Aplicativos de árvore : classificando e pesquisando como Tree Traversal & Binary Search.
- Árvore sempre tem n-1 arestas.
- Árvore é um modelo hierárquico.
Resposta
Portanto, as árvores kd, à primeira vista, podem parecer mais teóricas do que práticas. Mas esse não é realmente o caso.
As árvores kd contêm uma variedade de aplicativos importantes, alguns dos quais incluem:
1 . Pesquisa do vizinho mais próximo
Digamos que você pretenda construir um Social Cop em seu smartphone. O Polícia Social ajuda as pessoas a relatar crimes para a delegacia de polícia mais próxima em tempo real.
Então, o que parece ser um problema aqui?
Sim, você adivinhou certo. Precisamos procurar a delegacia de polícia mais próxima do local do crime antes de tentar denunciar qualquer coisa.
Como poderíamos fazer isso rapidamente ?
Parece que árvores k-d podem ajudá-lo a encontrar o vizinho mais próximo de um ponto em um mapa bidimensional de sua cidade. Tudo o que você precisa fazer é construir uma árvore kd bidimensional a partir da localização de todas as delegacias de polícia em sua cidade e, em seguida, consultar a árvore kd para encontrar a delegacia de polícia mais próxima de qualquer local da cidade.
Ok, entendi o que eles podem fazer. Mas como eles fazem isso?
Se você já sabe como funcionam as árvores binárias de pesquisa , entender como as árvores kd funcionam não seja nada novo. As árvores k-d ajudam no particionamento do espaço, assim como as árvores binárias de pesquisa ajudam no particionamento da linha real . As árvores k-d particionam recursivamente uma região do espaço, criando uma partição de espaço binário em cada nível da árvore.
Isto é o que uma região tridimensional do espaço particionada por uma árvore kd tridimensional se parece [1]:
Uma árvore kd tridimensional. A primeira divisão (vermelha) corta a célula raiz (branca) em duas subcélulas, cada uma das quais é então dividida (verde) em duas subcélulas. Finalmente, cada uma dessas quatro é dividida (azul) em duas subcélulas. Já que não há mais divisão, as oito últimas são chamadas de células-folha.
E como a árvore é construída?
Para começar, você tem um conjunto de pontos em um espaço k-dimensional.Vamos nos dar um exemplo de uma árvore kd bidimensional:
Entrada: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Resultado: Uma árvore kd bidimensional [2]:
No caso de árvores de pesquisa binárias, a partição binária da linha real em cada nó interno é representada por um ponto na linha real. Da mesma forma, no caso de uma árvore kd bidimensional, a partição binária do plano cartesiano bidimensional em cada nó interno é representada por um linha no plano.
Portanto, no caso de árvores de pesquisa binárias, o ponto representado pelo nó interno serve como o ponto usado para particionar a linha real. Como podemos escolher uma linha de particionamento no caso de árvores kd bidimensionais?
Essencialmente , você pode escolher qualquer linha passando pelo ponto representado pelo nó interno para particionar o plano cartesiano bidimensional.
A saída da árvore kd acima foi construída usando um método simples para escolher a linha de particionamento em cada nó interno da árvore: –
Nível 0 : – Escolha a linha de particionamento perpendicular à primeira dimensão ( X neste caso) e passando pelo ponto representado pelo nó em questão.
Nível 1 : – Escolha a linha de particionamento perpendicular à segunda dimensão ( Y neste caso) e passando pelo ponto representado por o nó em questão.
: : :
Nível k-1 : – Escolha a linha de particionamento perpendicular ao k-ésima dimensão e passando pelo ponto representado pelo nó em questão. Nível k : – Escolha a linha de particionamento perpendicular à primeira dimensão ( X neste caso) e passando pelo ponto representado pelo nó em questão.
Então, basicamente, em cada nível, alternamos entre as dimensões X e Y para escolher uma linha de particionamento em cada nó interno da árvore kd.
Os rótulos que você vê ao lado de cada um dos nós da árvore kd [2] representam a escolha da dimensão para a linha de particionamento nos nós naquele nível.
Vamos ” Agora veja como nossa árvore kd bidimensional particiona o plano bidimensional [3]:
Tudo bem, como faço a pesquisa?
Não direi que deixarei isso com você, mas com você ” Vou precisar de ajuda de alguns outros recursos para entendê-lo completamente. Posso, no entanto, dizer que esse particionamento de espaço por uma árvore kd pode ajudá-lo a encontrar o vizinho mais próximo de um ponto específico no espaço sem a necessidade de explorar todas as partições que é o que precisávamos, para fazer relatórios em em tempo real para Social Cop.
Para entender o algoritmo do vizinho mais próximo nas árvores kd, aqui está um bom recurso: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Deixe-me guiá-lo rapidamente por alguns dos outros aplicativos das árvores kd, visto que a maior parte do plano de fundo das árvores kd já foi abordada na discussão do primeiro aplicativo.
2. Consultas de banco de dados envolvendo uma chave de pesquisa multidimensional
Uma consulta solicitando todos os funcionários na faixa etária de (40, 50) e ganhando um salário na faixa de (15.000, 20.000) por mês pode ser transformada em um problema geométrico em que a idade é plotada ao longo do eixo x e o salário é plotado ao longo do eixo y [4]
[4] O eixo x denota a idade de o funcionário em anos , e o eixo y denota o salário mensal em mil rupias .
Uma árvore kd bidimensional no índice composto de (idade, salário) pode ajudá-lo a pesquisar com eficiência todos os funcionários que se enquadram na região retangular do espaço definida pela consulta descrita acima.
3. Problema de n-corpos [5]
Como podemos simular com eficiência os movimentos de uma coleção de objetos movendo-se sob atração gravacional mútua?
O método ingênuo envolveria computar a força gravitacional entre um objeto devido a todos os outros objetos, a fim de simular seu movimento sob atração gravitacional. Além disso, teríamos que fazer isso para cada objeto que levasse O (n ^ 2) tempo.
Usando árvores k-d, no entanto, podemos particionar o espaço e para cada subdivisão do espaço, descobrir seu efeito total no resto do espaço. Abaixo está o pseudocódigo [6] do algoritmo.
Coloque os objetos em uma árvore. Comece no nível inferior da árvore, para cada região em uma profundidade d na árvore: Se algum filho for folhas, calcule a interação diretamente Calcule o ” Expansão multipolar “Converta isso em uma expansão local para o nó pai e passe adiante. Passe para o nível d-1. Quando chegarmos ao topo da árvore, percorra novamente a árvore, somando as expansões locais.
4. Redução de cor [7]
O que é uma maneira inteligente de escolher 256 cores para representar uma imagem colorida?
O método ingênuo pode ser escolher as cores que são usadas com mais frequência.
Um método mais eficiente, no entanto, pode representar as cores em termos de RGB valores e construa uma árvore kd tridimensional para dividir o espaço contendo todas as cores da imagem. A construção da árvore k-d pararia quando a contagem dos nós folha se tornasse igual a 256. A média do valor RGB de cada uma das 256 partições poderia então ser usada para obter uma paleta de 256 cores para a imagem colorida.
Referências: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Classificação usando vizinhos mais próximos [5], [6], [7] : Árvores kD