Mejor respuesta
Diferencia entre el gráfico y la estructura de datos del árbol:
Gráfico
- En el gráfico puede haber más de una ruta, es decir, el gráfico puede tener rutas unidireccionales o bidireccionales entre los nodos.
- En el gráfico no existe tal concepto de raíz nodo.
- Graph puede tener bucles, circuitos y también puede tener auto-bucles.
- En Graph no existe tal relación padre-hijo.
- Los gráficos son más complejos en comparación con los árboles, ya que pueden tener ciclos, bucles, etc.
- El gráfico está atravesado por DFS : Primero búsqueda en profundidad y en BFS : Algoritmo de búsqueda primero en amplitud.
- El gráfico puede ser cíclico o acíclico.
- Existen principalmente dos tipos de gráficos: gráficos dirigidos y no dirigidos.
- Aplicación de gráficos licaciones: coloración de mapas, algoritmos, coloración de gráficos, programación de trabajos, etc.
- En Graph, no. de los bordes dependen del gráfico.
- El gráfico es un modelo de red.
Árboles
- El árbol es una forma especial de gráfico, es decir, un gráfico mínimamente conectado y que solo tiene una ruta entre dos vértices cualesquiera.
- El árbol es un caso especial de gráfico que no tiene bucles, circuitos ni auto-bucles.
- En el árbol hay exactamente una raíz nodo y cada hijo tiene solo un padre.
- En los árboles, existe una relación padre / hijo, por lo que el flujo puede estar allí con dirección de arriba a abajo o viceversa.
- Los árboles son menos complejos que los gráficos, ya que no tienen ciclos, ni ciclos automáticos y aún están conectados.
- El recorrido del árbol es una especie de caso especial de recorrido de gráfico. El árbol se atraviesa en Pedido anticipado , En pedido y Posterior al pedido (los tres en DFS o en BFS algoritmo)
- Los árboles pertenecen a la categoría de DAG: Los gráficos acíclicos dirigidos son un tipo de gráfico dirigido que no tiene ciclos.
- Los diferentes tipos de árboles son: Binary Tree , Binary Search Tree, AVL tree, Heaps.
- Aplicaciones de árbol : ordenando y buscando como Tree Traversal y Binary Search.
- El árbol siempre tiene n-1 bordes.
- Árbol es un modelo jerárquico.
Respuesta
Entonces, los árboles kd, a primera vista, pueden parecer de naturaleza más teórica que práctica. Pero ese no es realmente el caso.
Los árboles kd contienen una variedad de aplicaciones importantes, algunas de las cuales incluyen:
1 . Búsqueda de vecinos más cercanos
Supongamos que tiene la intención de crear un Social Cop en su teléfono inteligente. Social Cop ayuda a las personas a denunciar delitos en la estación de policía más cercana en tiempo real.
Entonces, ¿qué parece ser un problema aquí?
Sí, lo adivinaste bien. Necesitamos buscar la estación de policía más cercana al lugar del crimen antes de intentar reportar algo.
¿Cómo podríamos hacerlo? rápidamente ?
Parece que los árboles k-d pueden ayudarte a encontrar al vecino más cercano a un punto en un mapa bidimensional de tu ciudad. Todo lo que tienes que hacer es construir un árbol kd bidimensional a partir de las ubicaciones de todas las comisarías de tu ciudad y luego consultar el árbol kd para encontrar la estación de policía más cercana a cualquier lugar de la ciudad.
De acuerdo, entiendo lo que pueden hacer. Pero, ¿cómo lo hacen?
Si ya sabe cómo funcionan los árboles de búsqueda binaria , comprender cómo funcionan los árboles kd no sea nada nuevo. Los árboles k-d ayudan a particionar el espacio del mismo modo que los árboles de búsqueda binarios ayudan a particionar la línea real . Los árboles k-d dividen de forma recursiva una región del espacio, creando una partición de espacio binaria en cada nivel del árbol.
Así es como se ve una región de espacio tridimensional dividida por un árbol kd tridimensional [1]:
Un árbol kd tridimensional. La primera división (roja) corta la célula raíz (blanca) en dos subcélulas, cada una de las cuales luego se divide (verde) en dos subcélulas. Finalmente, cada uno de esos cuatro se divide (azul) en dos subcélulas. Como no hay más división, las ocho últimas se llaman celdas de hojas.
¿Y cómo se construye el árbol?
Para empezar, tiene un conjunto de puntos en un espacio k-dimensional.Démosnos un ejemplo de un árbol kd bidimensional:
Entrada: (2,3), (5,4), (9,6), (4,7), (8, 1), (7,2)
Resultado: Un árbol kd bidimensional [2]:
En el caso de árboles de búsqueda binarios, la partición binaria de la línea real en cada nodo interno está representada por un punto en la línea real. De manera similar, en el caso de un árbol kd bidimensional, la partición binaria del plano cartesiano bidimensional en cada nodo interno está representada por un línea en el plano.
Entonces, en el caso de árboles de búsqueda binaria, el punto representado por el nodo interno sirve como el punto utilizado para dividir la línea real. ¿Cómo elegimos una línea de división en el caso de árboles kd bidimensionales?
Esencialmente , puede elegir cualquier línea que pase por el punto representado por el nodo interno para dividir el plano cartesiano bidimensional.
La salida del árbol kd anterior se ha construido usando un método simple para elegir la línea de partición en cada nodo interno del árbol: –
Nivel 0 : – Elija la línea de partición perpendicular a la primera dimensión ( X en este caso) y pasando por el punto representado por el nodo en cuestión.
Nivel 1 : – Elija la línea de partición perpendicular a la segunda dimensión ( Y en este caso) y pasando por el punto representado por el nodo en cuestión.
: : :
Nivel k-1 : – Elija la línea de partición perpendicular a la kth dimensión y pasando por el punto representado por el nodo en cuestión. Nivel k : – Elija la línea de partición perpendicular a la primera dimensión ( X en este caso) y pasando por el punto representado por el nodo en cuestión.
Entonces, básicamente, en cada nivel alternamos entre las dimensiones X e Y para elegir una línea de partición en cada nodo interno del árbol kd.
Las etiquetas que ve al lado de cada uno de los nodos del árbol kd [2] representan la elección de la dimensión para la línea de partición en los nodos en ese nivel.
Let » Ahora vemos cómo nuestro árbol kd bidimensional divide el plano bidimensional [3]:
Bien, ¿cómo realizo la búsqueda?
No diré que «lo dejaré en tus manos, sino a ti» Tendré que tomar la ayuda de otros recursos para comprenderlo completamente. Sin embargo, puedo decirle que esta partición de espacio mediante un árbol kd puede ayudarlo a encontrar el vecino más cercano a un punto específico en el espacio sin la necesidad de explorar todas las particiones que es lo que necesitábamos, para hacer informes en tiempo real para Social Cop.
Para entender el algoritmo de vecino más cercano en árboles kd, aquí hay un buen recurso: http://www.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
Permítanme guiarlo rápidamente a través de algunas de las otras aplicaciones de los árboles kd, ya que la mayor parte del trasfondo de los árboles kd ya se ha cubierto en la discusión de la primera aplicación.
2. Consultas de base de datos que involucran una clave de búsqueda multidimensional
Una consulta que pregunte por todos los empleados en el grupo de edad de (40, 50) y que ganen un salario en el rango de (15000, 20000) por mes se puede transformar en un problema geométrico donde la edad se representa a lo largo del eje x y el salario se traza a lo largo del eje y [4]
[4] El eje x indica la edad de el empleado en años , y el eje y indica el salario mensual en mil rupias .
Un árbol kd bidimensional en el índice compuesto de (edad, salario) podría ayudarlo a buscar de manera eficiente todos los empleados que se encuentran en la región rectangular del espacio definida por la consulta descrita anteriormente.
3. Problema de n-cuerpos [5]
¿Cómo podemos simular eficazmente los movimientos de una colección de objetos que se mueven bajo atracción gravitacional mutua?
El método ingenuo implicaría calcular la fuerza gravitacional entre un objeto debido a todos los demás objetos con el fin de simular su movimiento bajo atracción gravitacional. Además, tendríamos que hacerlo para cada objeto que tomaría O (n ^ 2) tiempo.
Usando árboles k-d, sin embargo, podemos dividir el espacio y para cada subdivisión del espacio, calcular su efecto total en el resto del espacio. A continuación se muestra el pseudocódigo [6] del algoritmo.
Coloque los objetos en un árbol. Comience en el nivel inferior del árbol. Para cada región a una profundidad d en el árbol: si algunos hijos son hojas, calcule la interacción directamente Calcule el » Expansión multipolar «Convierta esto en una expansión local para el nodo principal y déjelo. Pasa al nivel d-1. Cuando llegamos a la parte superior del árbol, retrocedemos hacia abajo, sumando las expansiones locales.
4. Reducción de color [7]
¿Qué es una forma inteligente de elegir 256 colores para representar una imagen a todo color?
El método ingenuo podría ser elegir los colores que se usan con más frecuencia.
Sin embargo, un método más eficiente podría representar los colores en términos de su valores RGB y construye un árbol kd tridimensional para dividir el espacio que contiene todos los colores de la imagen. La construcción del árbol k-d se detendría cuando el recuento de los nodos de hojas se hiciera igual a 256. El promedio del valor RGB de cada una de las 256 particiones podría usarse para obtener una paleta de 256 colores para la imagen a todo color.
Referencias: [1], [2], [3]: http://en.wikipedia.org/wiki/Kd-tree [4]: Clasificación mediante vecinos más cercanos [5], [6], [7] : árboles kD