Preguntas sobre un tipo especial de gráficos, a saber, los conectados y sin ciclo.
Un árbol indexado binario tiene muy poca o relativamente poca literatura en comparación con otras estructuras de datos. El único lugar donde se enseña es el tutorial de topcoder . Aunque el tutorial está completo en todas las explicaciones, ¿no puedo entender la intuición detrás de tal árbol? ¿Cómo...
Estos dos parecen muy similares y tienen una estructura casi idéntica. ¿Cual es la diferencia? ¿Cuáles son las complejidades de tiempo para las diferentes operaciones de cada
Parece que donde quiera que mire, las estructuras de datos se están implementando utilizando árboles rojo-negros ( std::seten C ++, SortedDictionaryen C #, etc.) Después de haber cubierto los árboles (a, b), rojo-negro y AVL en mi clase de algoritmos, esto es lo que obtuve (también de preguntar a...
¿Cuál es la diferencia entre el algoritmo de árbol de expansión mínimo y un algoritmo de ruta más corta? En mi clase de estructuras de datos cubrimos dos algoritmos de árbol de expansión mínimo (Prim y Kruskal) y un algoritmo de ruta más corta (Dijkstra). El árbol de expansión mínimo es un árbol...
Existe este algoritmo estándar para encontrar la ruta más larga en árboles no dirigidos utilizando dos búsquedas de profundidad: Inicie DFS desde un vértice aleatorio y encuentre el vértice más alejado de él; di que es v ′ .vvvv′v′v' Ahora comience un DFS desde para encontrar el vértice más...
Supongamos la siguiente definición de un árbol rojo-negro: Es un árbol de búsqueda binario. Cada nodo es de color rojo o negro. La raíz es negra. Dos nodos conectados por un borde no pueden ser rojos al mismo tiempo. Aquí debería haber una buena definición de una hoja NIL, como en wiki. La hoja...
Estoy aprendiendo sobre los árboles radix (también conocidos como intentos comprimidos) y Patricia intenta, pero encuentro información contradictoria sobre si realmente son lo mismo o no. Se puede obtener un árbol de raíz de un trie normal (sin comprimir) fusionando nodos con sus padres cuando los...
Intuitivamente, los "árboles equilibrados" deben ser árboles donde los subárboles izquierdo y derecho en cada nodo deben tener "aproximadamente el mismo" número de nodos. Por supuesto, cuando hablamos de que los árboles rojo-negros * (ver definición al final) están equilibrados, en realidad...
Al implementar un diccionario ('Quiero buscar datos de clientes por sus ID de cliente'), las estructuras de datos típicas utilizadas son tablas hash y árboles de búsqueda binarios. Sé, por ejemplo, que la biblioteca C ++ STL implementa diccionarios (los llaman mapas) usando árboles de búsqueda...
Sabemos post-orden, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] y pre-orden pre L(x) => [x] pre N(x,l,r) => [x] ++ (pre l) ++ (pre r) y transversales en orden resp. secuencialización in L(x) => [x] in N(x,l,r) => (in l) ++ [x] ++ (in r) Se puede ver...
Este enlace proporciona un algoritmo para encontrar el diámetro de un árbol no dirigido usando BFS / DFS . Resumiendo: Ejecute BFS en cualquier nodo del gráfico, recordando el nodo que descubrió por última vez. Ejecute BFS desde que recuerda el nodo v descubierto por última vez. d (u, v) es el...
(Soy un estudiante con algunos conocimientos matemáticos y me gustaría saber cómo contar el número de un tipo específico de árboles binarios). Mirando la página de Wikipedia para árboles binarios , noté esta afirmación de que el número de árboles binarios enraizados de tamaño sería este número...
Wikipedia, así como otras fuentes que he encontrado, enumeran el voidtipo de C como un tipo de unidad en lugar de un tipo vacío. Esto me parece confuso, ya que me parece que se voidajusta mejor a la definición de un tipo vacío / inferior. No habito valores void, por lo que puedo decir. Una...
He visto dos definiciones de árboles binarios equilibrados, que me parecen diferentes. Un árbol binario se equilibra si para cada nodo mantiene que el número de nodos internos en el subárbol izquierdo y el número de nodos internos en el subárbol derecho difieren en como máximo 1. Un árbol binario...
He encontrado varias herramientas de programación visual de código abierto como Blockly y sus amigos, y otros proyectos alojados en Github, pero no pude encontrar ninguno que funcione directamente con el árbol de sintaxis abstracta. ¿Porqué es eso? Lo pregunto porque una vez que descubrí que cada...
No entiendo bien por qué la rotación en la estructura de datos del árbol de separación está teniendo en cuenta no solo al padre del nodo de calificación, sino también al abuelo (operación zig-zag y zig-zig). ¿Por qué no funcionaría lo siguiente? A medida que insertamos, por ejemplo, un nuevo nodo...
Intenté algunos casos y descubrí que dos árboles de expansión de un gráfico simple tienen algunos bordes comunes. Quiero decir que no pude encontrar ningún contraejemplo hasta ahora. Pero tampoco pude probar o refutar esto. ¿Cómo probar o refutar esta
En una pregunta anterior , había una definición de árboles con peso equilibrado y una pregunta sobre árboles rojo-negros. Esta pregunta es para hacer la misma pregunta, pero para los árboles AVL . La pregunta es, dada la definición de árboles balanceados como en la otra pregunta,μμ\mu ¿Hay...
Dado un gráfico ponderado y no dirigido G: ¿Qué condiciones deben ser ciertas para que haya múltiples árboles de expansión mínima para G? Sé que el MST es único cuando todos los pesos son distintos, pero no puede revertir esta afirmación. Si hay varias aristas con el mismo peso en el gráfico,...
Si un gráfico ponderado tiene dos árboles de expansión mínima diferentes y , entonces es cierto que para cualquier borde enT 1 = ( V 1 , E 1 ) T 2 = ( V 2 , E 2 ) e E 1 E 1 e e E 2 eGGGT1=(V1,E1)T1=(V1,E1)T_1 = (V_1, E_1)T2=(V2,E2)T2=(V2,E2)T_2 = (V_2, E_2)eeeE1E1E_1 , el número de bordes en con el...