Estructura de Datos Flashcards
Tipo abstracto de datos vs Estructura de datos
TAD es un modelo matematico (Qué)
EEDD Concepto más concreto orientado a implementación
Nota: Distinguir el tipo abstracto de datos y la estructura de datos de la implementación.
Operaciones del TAD Stack (pila) y como funciona
Funcionamiento LIFO (Last In - First Out)
Push: pone en la cima de la pila
Pop: saca de la pila la cima de la pila
IsEmpty: Booleano que indica si hay elementos
Top: Consulta la cima de la pila pero no saca
Operaciones del TAD Queue (cola) y como funciona
Funcionamiento FIFO (First In - First Out)
Enqueue: Encolas por el final de la cola
Dequeue: Desencolas (sacas) de la cola por el princio
IsEmpty: Booleano que indica si hay elementos
Font: Consulta la cabeza de la cola pero no saca el dato
Operaciones del TAD list (lista) y como funciona
Funcionamiento se puede insertar por delante y detras y coger la ‘cabeza’ y la ‘cola’
- IsEmpty: Booleano que indica si hay elementos
- InsertarDelante: Inserta un elemento por la cabeza de la lista
- InsertarDetras: Inserta un elemento al final de la cola de la lista
- Head: devuelve el primer elemento de la lista.
- Tail: Devuelve la lista de elementos sin el head (primer elemento)
Ej.:
Lista L1 = 7 1 2 6 9 4
Head(L1) = 7
Tail(L1) = 1 2 6 9 4 –> Genera una nueva lista L2
Head( Tail( Tail( L1 ) ) ) –> 2
¿Qué TAD (Tipo abstracto de datos) conoces?
List (lista)
Set / Multiset (Conjunto)
Queue / Double-ended Queue
Strack (pila)
Priority Queue (Heap) *
Tree
Graph
Associative Array (Diccionario, Mapa)
Que es una estructura de datos (EEDD) Tabla Hash
Colección de datos de acceso aleatorio mediante Clave Valor
Un ejemplo para calcular la ‘dirección’ del dato es haciendo el x mod N del key. Se puede producir colisiones que nos dará un acceso más lento pero lo trata internamente la implementación. Cuanto peor esté diseñada la función hash más colisiones tendremos.
Que es una estructura de datos (EEDD) HEAP o Monticulo
Suele tener estructura de árbol. Cada nodo es el mayor/menor de todos los que tiene por debajo.
Dos tipos:
Min Heap: Los nodos que tiene por debajo son mas grandes. El nodo es el menor
Max Heap: Los nodos que tiene por debajo son mas pequeños. El nodo es el mayor
Para insertar una hoja, se intercambian los valores con la raíz hasta que se cumpla la condicion min/max.
Para eliminar la raiz, se sube la última insercion y se intercamiban las raices hasta que se cumpla la condicion min/max.
Entre las posibles implementaciones tenemos arboles binarios o arrays.
¿Qué parametros tienes una EEDD de Árbol?
Orden: Número máximo de hijos que puede tener un nodo
Grado: Número de hijos directos que tiene en un momento dado.
Profundidad: Número de aristas desde la Raíz al nodo. Se pueden contar las aristas desde el nodo hacia arriba. La raíz tendrá profundidad 0
Altura: Número de aristas que hay desde un Nodo hasta la hoja más alejada. Una hoja siempre tendrá Altura 0 y la Raíz tendrá la altura máxima.
Factor de equilibrio: Diferencia de altura entre el subarbol izquierdo y derecho.
Peso de un árbol: Número total de nodos del árbol
¿Qué tipos de recorrido tenemos en un árbol?
Preorden (RID): Raíz Izquierda Derecha
Inorden (IRD): Izquierda Raíz Derecha –> InoRDen
Postorden (IDR): Izquierda Derecha Raíz
¿En que consiste un Árbol Binario de Busqueda?
Es un árbol de orden 2 (binario) donde a la izquierda de cada nodo encontramos valores más pequeños que la raiz y a la derecha valores mayores. Muy eficiente en tareas de búsqueda de ahí su nombre.
¿Que tipos de árboles equilibrados (auto - balanceables) conoces?
El factor de equilibrio de estos arboles (FE) no puede otra que -1 0 1
- AVL (Rotaciones).
- Fibonacci (caso particular de AVL)
- AA
- Rojo- Negro
- Splay
- Arbol B
Recorrido Preorden del árbol dado
PREORDER: RID (Raiz Izquierda Derecha)
A B D H I E C F G
NOTA: La ráiz siempre quedará al principio de la secuencia
Recorrido Inorden del árbol dado
INORDER: IRD (Izquierda Raiz Derecha)
H D I B E A F C G
NOTA: Si el árbol es binario de busqueda BST (ABB) el resultado Inorder quedará ordenado.
Recorrido Postorden del árbol dado
POSTORDER: IDR (Izquierda Derecha Raiz)
H I D E B F G C A
NOTA: La ráiz siempre quedará al final de la secuencia
Dados estos dos recorridos calcular el otro:
- PREORDEN: 13, 8, 6, 16, 15, 17
- INORDEN: 6, 8, 13, 15, 16, 17
Primero vamos a reproducir el árbol con los datos de entrada:
PREORDEN: 13, 8, 6, 16, 15, 17 (RID)
INORDEN: 6, 8, 13, 15, 16, 17 (IRD)
Sabemos que en PREORDEN siempre se empieza con el nodo raíz: 13. Localizamos el nodo en INORDEN para saber que queda a derecha e izquierda de esta manera:
...............13.............. 6, 8 15, 16, 17
Sabemos que en PREORDER siempre se pintan las raices primero con lo que si cogemos el subconjunto despues de la raiz [13, ] ,8,6,16,15,17, el primer numero que aparece es el 8 con lo que sabemos que es un nodo. En el caso del 6 que queda aislado se ve en INORDEN que va a la izquierda del 8: 6 ,8, …. (IRD)
. .............13................. ...........8 15, 16, 17 6
Misma filosofía con la derecha de la raíz (13). Miramos en PREORDEN que número aparece primero de los que nos quedan a la derecha en INORDEN (15, 16, 17) y vemos el 16 (13, 8, 6, [16] , 15, 17), con lo que sabemos que es nodo. Si 16 es nodo nos vamos a INORDEN y lo que quede a izquierdas y derechas serán los siguientes nodos. En este caso ya son hojas y se ve muy claro (15<–16 –>17)
. .............13................. ...........8 .....16.... 6 15 17
Ahora con el árbol hecho recorremos en POSTORDEN (IDR):
6, 8, 15, 17, 16, 13
Dados estos dos recorridos calcular el otro:
- POSTORDEN: 6, 8, 15, 17, 16, 13
- INORDEN: 6, 8, 13, 15, 16, 17
Primero vamos a reproducir el árbol con los datos de entrada:
POSTORDEN: 6, 8, 15, 17, 16, 13 (IDR)
INORDEN: 6, 8, 13, 15, 16, 17 (IRD)
Sabemos que en POSTORDEN siempre se termina con el nodo raíz: 13. Localizamos el nodo en INORDEN para saber que queda a derecha e izquierda de esta manera:
...............13.............. 6, 8 15, 16, 17
Gracias a INORDEN sabemos que va a la Izquierda de la raíz (6, 8 ). Localizamos en POSTORDEN esos nodos ( 6, 8, || 15, 17, 16 || [13]) . Además sabemos que en POSTORDEN siempre se pintan las raices al final con lo que si cogemos el subconjunto (6, 8,) y tenemos en cuenta IDR, sabemos que 8 es raiz. En el caso del 6 que queda aislado se ve en INORDEN que va a la izquierda del 8: 6 ,8, …. (IRD)
. .............13................. ...........8 15, 16, 17 6
Misma filosofía con la derecha de la raíz (13). Miramos en POSTORDEN que número aparece al final del conjunto de los que nos quedan a la derecha en INORDEN (15, 16, 17) y vemos el 16 ( 6, 8, || 15, 17, 16 || [13]) , con lo que sabemos que es nodo. Si 16 es nodo nos vamos a INORDEN y lo que quede a izquierdas y derechas serán los siguientes nodos. En este caso ya son hojas y se ve muy claro (15<–16 –>17)
. .............13................. ...........8 .....16.... 6 15 17
Ahora con el árbol hecho recorremos en PREORDEN (RID):
13, 8, 6, 16, 15, 17
Caracteristicas y tipos de Árboles B
Son un tipo de árbol muy utilizado en BBDD y sistemas de ficheros. Estos árboles están balanceados al igual que los de busqueda.
Arboles B
- Cada nodo puede tener M hijos (Orden M)
- Las inserciones y borrados se realizan en tiempo logaritmico
- Cada nodo (excepto raíz) tiene como mínimo M/2 claves.
Arboles B+
- Los nodos solo tienen claves y punteros.
- Las hojas son las que contienen los datos.
- Los nodos hoja están enlazados entre si de tal manera que la búsqueda transversal sea menos costosa
Arboles B*
- Garantizan densidad de ocupación 2/3 en lugar de 1/2 de los Arboles B
Caracteristicas de Grafos y tipos de Grafos.
- Pueden ser dirigidos o digrafo. El flujo solo puede ir en un sentido entre dos vertices (nodos)
- No dirigidos. El flujo puede ir en ambos sentidos entre dos vertices (nodos)
- Multigrafo. Más de una arista entre dos vértices
- Etiquetado / ponderado: Las aristas tienen un peso numérico. Típicamente el peso indica la dificultad de llegar de un vértice a otro.
- Orden del grafo: numero de vertices (nodos) que tiene el grafo
- Grado de un vertice: número de arcos (aristas) incidentes de un vertice (nodo)
NOTA: no confundir el Orden y el Grado con los de los árboles que son distintos.
¿Cómo sería la representación de un grafo mediante Matriz de Adyacencia?
Ponemos los nodos en la cabecera de las filas y las columnas y marcamos con un ‘1’ si están relacionados.
Mucho desperdicio de espacio en memoria. Los ‘0’ no nos interesan.
No puede crece ya que una matriz es una estructura estatica.
¿Cómo sería la representación de un grafo mediante Lista de Adyacencia?
Ponemos todos los nodos en un array o lista* y apuntamos a una lista con los nodos con los que tenga relación.
Mucho más optimo porque no se desperdicia memoria.
Nótese que la lista enlazada a un nodo no marca la relaciones entre nodos que se relacionan con el.
Ej.: [1] –> 2—> 4. El 4 no se relaciona con el 2 en el grafo pero está almacenado referenciado desde el 2 porque es relación del 1 que son las relaciones que estamos almacenando en esta posición. Para ver las relaciones de 2 o 4 tenemos que ir a su posición correspondiente.
Lista de algoritmos para recorrer Grafos
Muchos de estos algoritmos aparecen en el tema de encaminamiento.
*Importante, distinguir entre Camino Mínimo y Recubrimiento Mínimo
- PRIM (Arbol de recubrimiento mínimo)
- KRUSKAL (Arbol de recubrimiento mínimo)
- DIJKSTRA (Camino mínimo)
- BELLMAN-FORD (Camino mínimo)
- FORD-FULKERSON (caminos para maximizar flujos)
- TARJAN (Encuentra conexión de grafos disconexos)
- FLOYD-WARSHALL (Camino mínimo)
- VITERBI (Camino mínimo)
- JOHNSON (Camino mínimo)
- A* (Camino mínimo)
Algoritmos de Camino Minimo vs Recubrimiento Mínimo
El algorimo de Camino Mínimo encuentra el camino menos costoso para llegar de un nodo a otro.
Recubrimiento Mínimo (minimum spanning tree) es: Un camino que toque a todos los vertices (nodos) y que es el minimo posible que los toca a todos. Puede haber un camino entre nodos que no sea minimo pero el recubrimiento es el minimo que toca a TODOS.
¿Que tipo de accesos existen para ficheros y como funcionan?
- Acceso secuencial: Cintas
- Busqueda desde el inicio
- Borrado lógico. No se puede cortar la cinta
- Se añade sobre el final
- Acceso directo: A los registros
- Clave del registro –> posición en archivo
- Función (claves) –> Posición en archivo
- Acceso Indexado: fichero datos + ficheros de índices
- Se busca la clave sobre el indice ordando = posición
En que consiste el método de Mezcla Directa para ordenar ficheros
De una cinta pasamos a dos de tal manera que vamos cogiendo dato a dato y lo vamos poniendo en cada una de ellas.
6 | 5 | 3 | 1 | 8 | 7 | 2 |4
6 | 3 | 8 | 2
5 | 1 | 7 | 4
Juntamos de nuevo los datos en la cinta inicial pero ordenados de dos en dos cogiendo siempre los primeros de cada cinta:
5 - 6 | 1 - 3 | 7 - 8 | 2 - 4 = 5 | 6 | 1 | 3 | 7 | 8 | 2 | 4
Ahora hacemos lo mismo que al principio, separamos en dos cintas pero volcando de dos en dos:
5 | 6 | 7 | 8
1 | 3 | 2| 4
Y ahora comparamos los dos de una cinta con los de otra y lo metemos en la primera. Siempre cogemos desde el principio, en este caso 1, se nos desbloquea el 3 y lo comparamos con el 5
1 - 3 - 5 - 6 | 2 - 4 - 7 -8 = 1 | 3 | 5 | 6 | 2 | 4 | 7 |8
Mismo proceso pero ahora cogemos de 4 en 4
1 | 3 | 5 | 6
2 | 4 | 7 |8
Y juntamos de la misma manera, ‘desbloqueando’ y comparando
1 - 2 - 3 - 4 - 5 -6 - 7 - 8 = 1 | 2 | 3 | 4 | 5 |6 | 7 | 8
