b2t3 - Árboles y Estructura de datos Flashcards
Qué es un Tipo Abstracto de Datos (TAD) y en qué se diferencia de una estructura de datos?
Modelo matemático para definir tipos de datos (primitivas = comportamientos)
La estructura de datos es la implementación de un TAD
Qué primitivas tiene el TAD pila (stack)?
Qué otras operaciones se pueden ver?
Qué concepto maneja?
push y pop.
A veces, menos oficialmente se usa peek o top, que es consultar el último campo de la pila, pero sin sacarlo, sólo consulta.
size → Consultar el tamaño
empty → devuelve true si está vacía y false si no
Concepto LIFO
Qué primitivas tiene el TAD cola(queue)?
Qué otras operaciones se pueden ver?
Qué concepto maneja?
queue y dequeue
A veces, menos oficialmente se usa top, que es consultar el último campo de la cola, pero sin sacarlo, sólo consulta.
size → Consultar el tamaño
isEmpty → devuelve true si está vacía y false si no
Concepto FIFO
Qué primitivas tiene el TAD lista ?
insertarDeltante y insertarDetrás,
head → te da el primer elemento
tail → te da todos los elementos menos el head
isEmpty → devuelve true si está vacía y false si no
Qué implementaciones tienen las siguientes TAD? (no demasiado preguntable)
List (secuencia)
set / multiset
Queue / Double queue
Priority Queue (heap)
Tree
Graph
Associative Array (diccionario, mapa) (clave valor)
List (secuencia) → Array, Lista enlazada
set / multiset → Array, Rojo-negro, tabla hash
Queue / Double queue → Array, Lista enlazada / lista doblemente enlazada
Stack → Array, Lista enlazada
Priority Queue (heap) → Montículo (propiedad)
Tree
Graph → Matriz, Array de Listas enlazadas
Associative Array (diccionario, mapa) (clave valor) → Tabla hash
Cómo es la función hash que se usa en las tablas hash para generar la key?
[valor a guardar] mod 250 → Esto da como resultado el resto de dividir el valor / 250.
Qué es el concepto de colisión en una tabla hash?
Cuando se cargan más de 250 elementos en la tabla hash y por tanto varios elementos pueden dar el mismo resultado de” [valor elemento] mod 250” y por tanto la misma key
Qué es un MONTÍCULO?
Estructura basada en árbol, que cumple la propiedad del montículo:
max heap → el nodo raiz es el mayor de todo el árbol. Igualmente, cada nodo es el mayor de sus nodos hijos.
min heap → el nodo raiz es el menor de todo el árbol. Igualmente, cada nodo es el menor de sus nodos hijos.
Si se implementa con un árbol binario se llama montículo binario
Explica los siguientes concetos de los ÁRBOLES
Raíz
Rama
Hoja
Nivel
Profundidad
Altura del árbol
Altura de un nodo
Peso
Orden
Grado
Árbol binario
Árbol binario lleno
Árbol binario perfecto
Raíz → Nodo sin padres
Rama → Los nodos que tienen al menos un hijo y no son la raíz
Hoja → Nodo sin hijos
Nivel → El nivel vertical donde está el nodo, o los saltos desde la raíz. La raíz en casi todos los sitios se dice que es 0 y en otros 1
Peso → Nº de nodos del árbol
Altura del árbol → nº de saltos (aristas) en la trayectoria más larga de la raiz nodo hasta una hoja
Altura de un nodo → la trayectoria más larga del nodo hasta una hoja (ojo, las hojas son altura =0, aunque no sea la hoja a más profunidad!)
Profundidad → Nº de saltos (aristas) desde el nodo hasta la raíz
Orden → Nº máximo teórico de hijos que puede tener un nodo potencialmente, aunque no los tenga. En árbol binario el orden es 2
Grado → Nº de nodos hijos máximo concreto que tiene uno de los nodos del árbol
Árbol binario → Árbol donde el nº máximo de hijos de un nodo es 2, es decir, es de orden 2
Árbol binario lleno → Árbol binario en el que la raíz y todas las ramas tiene 2 hijos. Otra forma de decirlo es que todos los nodos salvo la raíz tiene 2 o 0 hijos
Árbol binario perfecto → Árbol binario donde todas las hojas están al mismo nivel
En los árboles, qué es el FE o Factor de equilibrio?
Factor de equilibrio (FE) → diferencia de altura entre el subárbol izquierdo y el derecho de -1, 0 o +1
Qué tipos de árboles equilibrados o autobalanceables más importantes hay?
AVL (rotación)
AA
Rojo-Negro
Splay
Árbol B
Con qué concepto se consigue el equilibrio en los árboles AVL (balanceables o equilibrados)?
Con la rotación de nodos
Qué tipos de árboles binarios más importantes hay?
Árbol binario de búsqueda → Recorrido In Orden (IRD) → elementos ordenados
Árbol de Fibonacci → caso particular de AVL
Qué tipos de recorridos de árboles en profundidad hay?
RID → Pre Orden
IRD → In Orden
IDR → Post Orden
(La raiz es la que se mueve en las siglas, como truco nemotécnico)
Cuál es la lógica para aplicar los recorridos en profundidad PreOrden, InOrden y PostOrden?
Se visita (escribe) lo que indican las siglas, siempre que no se pueda navegar más. Es decir que cuando al ir a I o D, ese nodo tiene hijos, se aplica de nuevo las siglas del algoritmo a ese nuevo subárbol. “Se aplica el algoritmo recursivamente a cada subárbol”
Cómo se pueden identificar dado un recorrido si es PreOrden, InOrden y PostOrden?
En PreOrden, la raíz es la primera, en Post-Orden es la última. En InOrden quedará ni el primero ni el último
En una pregunta de examen te pueden dar dos recorridos (uno será siempre el InOrden) y tener que sacar el tercero. Cómo es la lógica deductiva?
https://youtu.be/cGlNehp57Y0
- Identificar la raiz: En PreOrden, la raíz es la primera, en Post-Orden es la última. En InOrden quedará ni el primero ni el último.
- Identificar subárbol izquierdo y derecho de esa raíz: En InOrden, todo lo de la izquierda de la R es el subárbol izquierdo y todo lo de la derecha de R es el subárbol derecho
- Volver a identificar la raíz de cada subárbol: del subconjunto de nodos de cada subárbol, la raíz será la primera o la última en el PreOrden o PostOrden respectivamente.
- Volver a identificar los subárboles izquierdo y derecho de cada raíz
- … así recursivamente hasta terminar
En una pregunta de algortimos de pseudocódigo puede ser resolver qué parámetro hay que pasarle a una función recursiva para que salga un resultado determinado.
HACER EJECERCICIO ÚLTIMO EXAMEN PARA PRACTICAR
Para resolverla, hacer la siguiente estrategia:
- Seleccionar una de las posibles respuestas y usarla para probar con ella a ver si da el resultado
- Dibujar el árbol de llamadas, pero sólo una rama hasta el final
- Usar los resultados de las iteraciones de la primera rama cuando se repitan en otras ramas, para ahorrarnos dibujarlos otra vez ya que van a dar lo mismo y ya sabemos el resultado
Para resolverla, hacer la siguiente estrategia:
- Seleccionar una de las posibles respuestas y usarla para probar con ella a ver si da el resultado
- Dibujar el árbol de llamadas, pero sólo una rama hasta el final
- Usar los resultados de las iteraciones de la primera rama cuando se repitan en otras ramas, para ahorrarnos dibujarlos otra vez ya que van a dar lo mismo y ya sabemos el resultado
Cómo funciona el tipo de recorrido en profundidad de árboles Pre-Orden (RID)?
Completar———–
Se visita cada nodo al caer en él
1º Se empieza a navegar por la Raíz, y se
2º Subárbol izquierdo (siempre que se pueda ir a la izquierda, se va)
3º Subárbol derecho
Cómo funciona el tipo de recorrido en profundidad de árboles In-Orden (IRD)?
Se visita (imprime) cada nodo sólo cuando no se puede seguir navegando en esa dirección
1º Cuando no se pueda bajar más, se coge ese subárbol se visita primero I, luego la R de ese árbol, y luego D
2º Se sube un paso arriba, y se coge el siguiente subárbol por arriba. Ahora en este se visita R (porque I ya se ha visitado en el paso 1) y luego R
3º Así sucesivamente
Cómo funciona el tipo de recorrido en profundidad de árboles Post-Orden (IDR)?
Completar
Explicación de recorridos RID, IRD, IDR
https://en.wikipedia.org/wiki/Tree_traversal
https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/
https://en.wikipedia.org/wiki/Tree_traversal
https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/
Qué es un Árbol B?
Un árbol multicamino, en el que en cada nodo, en vez de un dato, hay más de uno.
Cada nodo puede tener n hijos
Qué tipos de un Árbol B hay y en qué consisten?
Árbol B → Árbol multimcamino. Cada nodo puede tener n hijos
Árbol B+ → Los nodos hoja están enlazados entre si y los datos solo están en los nodos hoja (en resto de nodos contiene claves)
Árbol B* → garantiza una ocupación de ⅔
Explica los siguientes concetos de los GRAFOS
Vértice
Arista
Arco
Dirigido / no dirigido
Grafo conexo
Multigrafo
Etiquetado o ponderado
Orden del grafo
Vértice → Nodo
Arista → Línea entre dos nodos
Arco → Relación entre dos nodos, se expresa (nodo a, nodo b)
No dirigido / Dirigido → Si se puede navegar entre dos nodos en los dos sentidos o solo en un sentido
Grafo conexo → Sin ciclos
Multigrafo → más de una arista entre dos vértices (más de un camino entre dos nodos)
Etiquetado o ponderado → Peso numérico en las aristas
Orden del grafo → Nº de vértices
Grado de un vértice → Nª de arcos incidentes
Con qué estructuras de datos se pueden representar los GRAFOS?
- Listas de adyacencia (array de vértices + listas enlazadas)
- Matrices de adyacencia (desperdicia memoria) → Se ponen todos los vértices en los dos ejes de una matriz y se marca en cada cruce con 1/0 si están enlazados o no en cada sentido
