Un árbol es un tipo especial de gráfico que solo permite un conjunto jerárquico de aristas similar a un árbol. Matemáticamente es en realidad una arborescencia. Los árboles tienen un nodo raíz y nodos hijos. En términos formales se describe como un gráfico conectado acíclico.
Varios problemas de optimización que se sabe que son NP-hard en los gráficos generales se pueden resolver trivialmente en tiempo polinómico (algunos incluso en tiempo lineal) cuando el gráfico de entrada es un árbol. Los ejemplos incluyen cobertura mínima de vértice, conjunto independiente máximo,...
Tengo cierta experiencia en informática científica, y he usado ampliamente kd-trees para aplicaciones BSP (partición de espacio binario). Recientemente me he familiarizado con los octrees, una estructura de datos similar para particionar espacios euclidianos en 3-D, pero que funciona a intervalos...
Definimos un lenguaje de árbol regular como en el libro TATA : es el conjunto de árboles aceptado por un autómata de árbol finito no determinista (Capítulo 1) o, de manera equivalente, el conjunto de árboles generado por una gramática de árbol regular (Capítulo 2). Ambos formalismos se parecen...
Un colega que trabaja en programación genética me hizo la siguiente pregunta. Primero intenté resolverlo basado en un enfoque codicioso, pero en un segundo pensamiento, encontré un contraejemplo al algoritmo codicioso. Entonces, pensé que vale la pena mencionarlo aquí. Considere dos polinomios...
Recientemente leí este resumen de los problemas relacionados con la diferencia entre los árboles y me interesó aprender cuál es el estado del arte para este problema. Además, suponga que entre sus operaciones de edición permitidas se encuentran el nodo tradicional de agregar / eliminar, edite el...
Estoy buscando formas de mantener un árbol de expansión de un gráfico relativamente equilibrado, a medida que agrego nuevos nodos / bordes al gráfico. Tengo un gráfico no dirigido que comienza como un solo nodo, la "raíz". En cada paso, agrego al gráfico un nuevo nodo y un borde que lo conecta al...
¿Es posible probar algorítmicamente si un número computable es racional o entero? En otras palabras, ¿sería posible que una biblioteca que implementa números computables proporcione las funciones isIntegero isRational? Supongo que no es posible, y que esto está relacionado de alguna manera con el...
Estoy buscando un algoritmo para fusionar dos árboles de búsqueda binarios de tamaño y rango arbitrarios. La forma obvia de implementar esto sería encontrar subárboles completos cuyo rango pueda caber en un nodo externo arbitrario en el otro árbol. Sin embargo, el peor tiempo de ejecución para este...
Hace un tiempo hice esta pregunta sobre Stack Overflow: Problema: la venta de Bob . Alguien sugirió publicar la pregunta aquí también. Alguien ya ha hecho una pregunta relacionada con este problema aquí: peso mínimo por debajo del bosque de la cardinalidad dada , pero, por lo que entiendo, no me...
Estaba leyendo un capítulo en LYAH que realmente no tenía sentido para mí. Entiendo que las cremalleras pueden atravesar arbitrariamente una estructura similar a un árbol, pero necesito alguna aclaración al respecto. Además, ¿se pueden generalizar las cremalleras a cualquier estructura de...
El problema de mantenimiento de la orden (o "mantener el orden en una lista") es apoyar las operaciones: singleton: crea una lista con un elemento, le devuelve un puntero insertAfter: dado un puntero a un elemento, inserta un nuevo elemento después de él, devolviendo un puntero al nuevo...
Mientras intentaba corregir un error en una biblioteca, busqué documentos para encontrar subranges en árboles rojos y negros sin éxito. Estoy considerando una solución con cremalleras y algo similar a la operación de adición habitual utilizada en algoritmos de eliminación para estructuras de datos...
Esta pregunta está relacionada con una de mis preguntas anteriores, problemas NP-hard en los árboles . Estoy buscando problemas que sean P-completos en los
Esta pregunta fue motivada por una pregunta hecha en stackoverflow . Supongamos que se le da un árbol enraizado (es decir, hay una raíz y los nodos tienen hijos, etc.) en n nodos (etiquetados 1 , 2 , ... , n ).TTTnortenn1 , 2 , ... , n1,2,…,n1, 2, \dots, n Cada vértice tiene un peso entero no...
Este blog habla de generar "pequeños laberintos retorcidos" usando una computadora y enumerándolos. La enumeración se puede hacer usando el algoritmo de Wilson para obtener el UST , pero no recuerdo la fórmula de cuántos
Los intentos permiten el almacenamiento eficiente de listas de elementos. Los prefijos se comparten, por lo que ahorra espacio. Estoy buscando una forma similar de almacenar árboles de manera eficiente. Me gustaría poder verificar la membresía y agregar elementos, sabiendo si un árbol dado es un...
He leído un poco sobre las siguientes estructuras de datos: El hachís ideal de Bagwell intenta Tablas hash dinámicas de Larson Árboles rojo-negro Arboles patricia ... y estoy seguro de que hay muchos otros por ahí. He visto muy poco en la forma en que cada uno es más adecuado, o por qué...
Deje que sea un árbol binario enraizado. Cada camino desde la raíz de hasta una hoja tiene una longitud . Cada nodo de siempre tiene un nodo hijo izquierdo y uno derecho, pero es posible que sean iguales (por lo que siempre hay rutas posibles). El tamaño de está limitado por . Un nodo con...
Estoy buscando una estructura de datos, que es básicamente un árbol de mapas, donde el mapa en cada nodo contiene algunos elementos nuevos, así como los elementos en el mapa de su nodo padre. Por mapa aquí me refiero a un mapa de programación con claves y valores, como mapa en STL o dict en...
Tengo un gran conjunto de datos de árboles y me gustaría buscarlo especificando un treelet (subgrafo conectado). La consulta debe devolver todas las ocurrencias del treelet en el conjunto de datos. ¿Hay algoritmos eficientes para hacerlo? Estaba pensando en algo así como matrices de sufijos, sin...