¿Cómo dependen de la altura h la búsqueda, inserción y eliminación en un BST?

Cuestan O(h). Un árbol equilibrado tiene h = O(log n); una cadena, h = O(n). El coste esperado O(log n) exige hipótesis como un orden de inserción aleatorio.

¿Qué reglas de color mantienen equilibrado un BST rojinegro?

Los nodos son rojos o negros; la raíz y las hojas NIL son negras. Ningún nodo rojo tiene hijos rojos. Todos los caminos de un nodo a una hoja NIL descendiente contienen igual número de nodos negros. Estas reglas acotan la altura a O(log n).

¿Qué hacen find y union en una estructura de conjuntos disjuntos?

find(x) devuelve el representante del conjunto de x. union(x,y) fusiona sus conjuntos si son distintos; si ya pertenecen al mismo, la partición no cambia.

¿Qué es un trie y cuándo cuesta O(L) buscar una clave de L caracteres?

Es un árbol de prefijos que guarda las claves en caminos de caracteres, con marcas de clave completa. La búsqueda cuesta O(L) si cada transición al carácter siguiente cuesta O(1).

¿Por qué el acceso por índice en un array de tamaño fijo cuesta O(1)?

Sus posiciones, de igual tamaño, son contiguas: dirección(i) = base + i·tamaño_posición. Se supone que calcular direcciones cuesta tiempo constante.

Para funciones no negativas f y g, ¿qué significa f(n) ∈ O(g(n))?

Existen constantes c > 0 y n₀ ≥ 0 tales que f(n) ≤ c·g(n) para todo n ≥ n₀.

¿Cómo recorre un árbol binario el recorrido por niveles?

Usa una cola FIFO para visitar un nivel de profundidad cada vez. Encola el hijo izquierdo antes que el derecho para obtener el orden de izquierda a derecha.

¿Cómo funciona una pila y cuándo cuestan O(1) sus operaciones?

LIFO: el último elemento insertado sale primero. En la cabeza de una lista enlazada, insertar, extraer y consultar cuestan O(1); redimensionar un array puede hacer que una inserción cueste O(n).

¿Por qué una lista doblemente enlazada puede eliminar un nodo dado en O(1)?

Sus enlaces anterior y siguiente permiten reconectar directamente los vecinos. Se actualizan cabeza y cola si hace falta; no hay que buscar el predecesor.

¿Cuánto cuesta construir un montículo de abajo arriba con n elementos?

O(n). La mayoría de los nodos están cerca de las hojas y requieren pocos descensos; sumar el trabajo por altura de nodo da un total lineal.

Si la capacidad se duplica, ¿cuánto cuesta amortizadamente añadir al final de un array dinámico?

O(1) por inserción. Redimensionar puede costar O(n), pero n inserciones al final desde un array vacío cuestan O(n) en total.

¿Cuáles son los costes esperados y de peor caso en una tabla hash con encadenamiento separado?

Con carga acotada, hashes bien distribuidos y operaciones sobre claves de coste constante, buscar y borrar cuestan O(1) esperado. Con crecimiento geométrico, insertar cuesta O(1) amortizado esperado. Una cadena de n claves en colisión puede causar O(n).

Compara la inserción al principio y el acceso por índice en una lista simplemente enlazada y un array dinámico.

Lista: inserción inicial O(1), acceso por índice O(n). Array: inserción inicial O(n), acceso por índice O(1); insertar al principio desplaza elementos.

¿Cómo resuelve las colisiones hash el encadenamiento separado?

Cada cubeta contiene una colección de entradas con ese índice, a menudo una lista enlazada. Las claves distintas que comparten cubeta siguen siendo entradas separadas.

¿En qué se diferencian la compresión de caminos, la unión por rango y la unión por tamaño?

La compresión redirige los nodos visitados a la raíz. Por rango, la raíz de menor rango queda bajo la de mayor rango; por tamaño, el conjunto menor queda bajo el mayor. El rango no tiene por qué ser la altura actual.

¿Qué produce el recorrido inorden de un BST con claves distintas?

Todas las claves en orden estrictamente creciente, visitando n nodos en O(n).

¿Qué propiedades debe tener una función hash para buscar en una tabla?

Debe ser determinista y distribuir bien las claves esperadas. Calcular el hash de claves de tamaño fijo puede costar O(1); el de una cadena nueva de L caracteres suele costar O(L).

¿Qué invariante de orden define un árbol binario de búsqueda (BST) con claves distintas?

En cada nodo, todas las claves del subárbol izquierdo son menores y todas las del derecho son mayores. La regla se aplica recursivamente.

¿Qué respuestas puede dar un filtro de Bloom que solo permite inserciones?

Un resultado negativo indica que el elemento no se insertó; uno positivo, que puede haberse insertado. Los hashes activan bits en un array: puede haber falsos positivos, pero no falsos negativos si el estado está intacto.

¿Cómo evita una cola circular en un array desplazar elementos al extraer?

Los índices inicial y final avanzan módulo la capacidad. Extraer adelanta el índice inicial, permitiendo reutilizar posiciones libres sin mover los demás elementos.

¿Cuál es la condición de equilibrio AVL?

En cada nodo, altura(izquierda) − altura(derecha) ∈ {−1, 0, 1}. El árbol también cumple el invariante de orden de un BST.

¿Cuáles son los órdenes de recorrido preorden, inorden y postorden de un árbol binario?

Preorden: nodo → izquierda → derecha. Inorden: izquierda → nodo → derecha. Postorden: izquierda → derecha → nodo.

¿Dónde están el padre y los hijos del nodo i en un array de montículo de longitud n e índices desde cero?

Padre: ⌊(i−1)/2⌋ si i>0. Hijos: 2i+1 y 2i+2, solo si esos índices son menores que n. El índice 0 no tiene padre.

¿Qué dos propiedades definen un montículo binario mínimo?

Es un árbol binario completo y la clave de cada padre no supera las de sus hijos. Por tanto, la raíz contiene un mínimo.

¿Qué es el factor de carga de una tabla hash y por qué puede redimensionarse?

α = n/m: n entradas almacenadas y m cubetas o posiciones. Superar el umbral de la implementación puede provocar una ampliación y redistribución mediante hash; 0,75 no es universal.

¿Cómo se corrige un desequilibrio izquierda-derecha causado por una inserción AVL?

Primero se rota el hijo izquierdo hacia la izquierda; después, el nodo desequilibrado hacia la derecha.

¿En qué se diferencian O, Ω y Θ?

Expresan cotas asintóticas superior, inferior y ajustada, respectivamente. Describen una función de coste especificada; O no significa por sí misma «peor caso».

¿Cuál es el coste amortizado de union/find con compresión de caminos y unión por rango?

O(α(n)) por operación, donde α es la inversa de Ackermann y n el número de elementos. Inicializar cuesta O(n); la cota describe una secuencia, no un coste constante de peor caso para cada llamada.

¿Cuánto cuestan insertar, eliminar la raíz y consultar la raíz en un montículo binario?

O(log n), O(log n) y O(1), respectivamente, si no hace falta redimensionar el array. Redimensionarlo puede costar O(n).

Ordena de menor a mayor crecimiento cuando n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.

Asintóticamente: 1 < log n < n < n log n < n² < 2ⁿ < n!.

¿Qué orden de acceso usa una cola y cuánto suelen costar sus operaciones?

FIFO: se añade por detrás y se extrae por delante. Ambas operaciones cuestan O(1) con enlaces a cabeza y cola o un búfer circular de capacidad fija; desplazar un array hace que extraer cueste O(n).

¿En qué se diferencian el sondeo lineal y el cuadrático en direccionamiento abierto?

Las entradas permanecen en el array. Con tamaño m e índice inicial h, se prueban (h+i) mod m y (h+c₁i+c₂i²) mod m, respectivamente. El sondeo cuadrático requiere parámetros adecuados.

Estructuras de Datos, Análisis de Complejidad (Big-O) y Algoritmos Clave

Repaso universitario que requiere programación básica: 32 tarjetas sobre arrays, listas, hashing, árboles, montículos, tries, Union–Find, filtros de Bloom y complejidad.

Level: basic
Languages: es → es
Cards: 32
Markdown: Estructuras de Datos, Análisis de Complejidad (Big-O) y Algoritmos Clave (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	¿Cómo dependen de la altura h la búsqueda, inserción y eliminación en un BST?	Cuestan O(h). Un árbol equilibrado tiene h = O(log n); una cadena, h = O(n). El coste esperado O(log n) exige hipótesis como un orden de inserción aleatorio.
2	¿Qué reglas de color mantienen equilibrado un BST rojinegro?	Los nodos son rojos o negros; la raíz y las hojas NIL son negras. Ningún nodo rojo tiene hijos rojos. Todos los caminos de un nodo a una hoja NIL descendiente contienen igual número de nodos negros. Estas reglas acotan la altura a O(log n).
3	¿Qué hacen find y union en una estructura de conjuntos disjuntos?	find(x) devuelve el representante del conjunto de x. union(x,y) fusiona sus conjuntos si son distintos; si ya pertenecen al mismo, la partición no cambia.
4	¿Qué es un trie y cuándo cuesta O(L) buscar una clave de L caracteres?	Es un árbol de prefijos que guarda las claves en caminos de caracteres, con marcas de clave completa. La búsqueda cuesta O(L) si cada transición al carácter siguiente cuesta O(1).
5	¿Por qué el acceso por índice en un array de tamaño fijo cuesta O(1)?	Sus posiciones, de igual tamaño, son contiguas: dirección(i) = base + i·tamaño_posición. Se supone que calcular direcciones cuesta tiempo constante.
6	Para funciones no negativas f y g, ¿qué significa f(n) ∈ O(g(n))?	Existen constantes c > 0 y n₀ ≥ 0 tales que f(n) ≤ c·g(n) para todo n ≥ n₀.
7	¿Cómo recorre un árbol binario el recorrido por niveles?	Usa una cola FIFO para visitar un nivel de profundidad cada vez. Encola el hijo izquierdo antes que el derecho para obtener el orden de izquierda a derecha.
8	¿Cómo funciona una pila y cuándo cuestan O(1) sus operaciones?	LIFO: el último elemento insertado sale primero. En la cabeza de una lista enlazada, insertar, extraer y consultar cuestan O(1); redimensionar un array puede hacer que una inserción cueste O(n).
9	¿Por qué una lista doblemente enlazada puede eliminar un nodo dado en O(1)?	Sus enlaces anterior y siguiente permiten reconectar directamente los vecinos. Se actualizan cabeza y cola si hace falta; no hay que buscar el predecesor.
10	¿Cuánto cuesta construir un montículo de abajo arriba con n elementos?	O(n). La mayoría de los nodos están cerca de las hojas y requieren pocos descensos; sumar el trabajo por altura de nodo da un total lineal.
11	Si la capacidad se duplica, ¿cuánto cuesta amortizadamente añadir al final de un array dinámico?	O(1) por inserción. Redimensionar puede costar O(n), pero n inserciones al final desde un array vacío cuestan O(n) en total.
12	¿Cuáles son los costes esperados y de peor caso en una tabla hash con encadenamiento separado?	Con carga acotada, hashes bien distribuidos y operaciones sobre claves de coste constante, buscar y borrar cuestan O(1) esperado. Con crecimiento geométrico, insertar cuesta O(1) amortizado esperado. Una cadena de n claves en colisión puede causar O(n).
13	Compara la inserción al principio y el acceso por índice en una lista simplemente enlazada y un array dinámico.	Lista: inserción inicial O(1), acceso por índice O(n). Array: inserción inicial O(n), acceso por índice O(1); insertar al principio desplaza elementos.
14	¿Cómo resuelve las colisiones hash el encadenamiento separado?	Cada cubeta contiene una colección de entradas con ese índice, a menudo una lista enlazada. Las claves distintas que comparten cubeta siguen siendo entradas separadas.
15	¿En qué se diferencian la compresión de caminos, la unión por rango y la unión por tamaño?	La compresión redirige los nodos visitados a la raíz. Por rango, la raíz de menor rango queda bajo la de mayor rango; por tamaño, el conjunto menor queda bajo el mayor. El rango no tiene por qué ser la altura actual.
16	¿Qué produce el recorrido inorden de un BST con claves distintas?	Todas las claves en orden estrictamente creciente, visitando n nodos en O(n).
17	¿Qué propiedades debe tener una función hash para buscar en una tabla?	Debe ser determinista y distribuir bien las claves esperadas. Calcular el hash de claves de tamaño fijo puede costar O(1); el de una cadena nueva de L caracteres suele costar O(L).
18	¿Qué invariante de orden define un árbol binario de búsqueda (BST) con claves distintas?	En cada nodo, todas las claves del subárbol izquierdo son menores y todas las del derecho son mayores. La regla se aplica recursivamente.
19	¿Qué respuestas puede dar un filtro de Bloom que solo permite inserciones?	Un resultado negativo indica que el elemento no se insertó; uno positivo, que puede haberse insertado. Los hashes activan bits en un array: puede haber falsos positivos, pero no falsos negativos si el estado está intacto.
20	¿Cómo evita una cola circular en un array desplazar elementos al extraer?	Los índices inicial y final avanzan módulo la capacidad. Extraer adelanta el índice inicial, permitiendo reutilizar posiciones libres sin mover los demás elementos.
21	¿Cuál es la condición de equilibrio AVL?	En cada nodo, altura(izquierda) − altura(derecha) ∈ {−1, 0, 1}. El árbol también cumple el invariante de orden de un BST.
22	¿Cuáles son los órdenes de recorrido preorden, inorden y postorden de un árbol binario?	Preorden: nodo → izquierda → derecha. Inorden: izquierda → nodo → derecha. Postorden: izquierda → derecha → nodo.
23	¿Dónde están el padre y los hijos del nodo i en un array de montículo de longitud n e índices desde cero?	Padre: ⌊(i−1)/2⌋ si i>0. Hijos: 2i+1 y 2i+2, solo si esos índices son menores que n. El índice 0 no tiene padre.
24	¿Qué dos propiedades definen un montículo binario mínimo?	Es un árbol binario completo y la clave de cada padre no supera las de sus hijos. Por tanto, la raíz contiene un mínimo.
25	¿Qué es el factor de carga de una tabla hash y por qué puede redimensionarse?	α = n/m: n entradas almacenadas y m cubetas o posiciones. Superar el umbral de la implementación puede provocar una ampliación y redistribución mediante hash; 0,75 no es universal.
26	¿Cómo se corrige un desequilibrio izquierda-derecha causado por una inserción AVL?	Primero se rota el hijo izquierdo hacia la izquierda; después, el nodo desequilibrado hacia la derecha.
27	¿En qué se diferencian O, Ω y Θ?	Expresan cotas asintóticas superior, inferior y ajustada, respectivamente. Describen una función de coste especificada; O no significa por sí misma «peor caso».
28	¿Cuál es el coste amortizado de union/find con compresión de caminos y unión por rango?	O(α(n)) por operación, donde α es la inversa de Ackermann y n el número de elementos. Inicializar cuesta O(n); la cota describe una secuencia, no un coste constante de peor caso para cada llamada.
29	¿Cuánto cuestan insertar, eliminar la raíz y consultar la raíz en un montículo binario?	O(log n), O(log n) y O(1), respectivamente, si no hace falta redimensionar el array. Redimensionarlo puede costar O(n).
30	Ordena de menor a mayor crecimiento cuando n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.	Asintóticamente: 1 < log n < n < n log n < n² < 2ⁿ < n!.
31	¿Qué orden de acceso usa una cola y cuánto suelen costar sus operaciones?	FIFO: se añade por detrás y se extrae por delante. Ambas operaciones cuestan O(1) con enlaces a cabeza y cola o un búfer circular de capacidad fija; desplazar un array hace que extraer cueste O(n).
32	¿En qué se diferencian el sondeo lineal y el cuadrático en direccionamiento abierto?	Las entradas permanecen en el array. Con tamaño m e índice inicial h, se prueban (h+i) mod m y (h+c₁i+c₂i²) mod m, respectivamente. El sondeo cuadrático requiere parámetros adecuados.