EEDD (repe) Flashcards
TAD
Tipo Abstracto de Datos.
Modelo matemático para definir tipos de datos(primitivas). Comportamiento.
Estructura de datos
Concepto más concreto orientado a la implementación
TAD –> Implementaciones
List –> Array, Lista enlazada
Set –> Árbol rojo-negro, tabla Hash
Queue –> Array, Lista [doble] enlazada
Stack –> Array, Lista enlazada
Priority Queue –> Montículo
Tree
Graph –> Matriz, Array de Listas enlazadas
Associative Array –> Tabla Hash
Stack
Lista circular LIFO.
push: añade
pop: lee y retira superior
isEmpty: true/false
top: lee primero sin retirarlo
Queue
Lista circular FIFO
enQueue: añade al final
deQueue: elimina primero
isEmpty: true/false
top: lee primero sin retirarlo
lista
EEDD secuencial. Ordenados de manera consecutiva.
isEmpty
insertarDelante
insertarDetras
head
tail
Tabla Hash
Se añaden elementos sabiendo la posición que ocupa cada dato insertado.
Si está mal diseñado se producen colisiones.
Para resolución de colusiones se puede usar direccionamiento cerrado (hashing abierto) o direccionamiento abierto (hashing cerrado)
Montículo
Estructura basada en árbol que cumple la propiedad del montículo.
Max-heap: raíz –> el valor más alto
Min-heap: raíz –> el valor más bajo
Árboles
Raíz: elemento que no tiene antecesor
Orden: nº máximo de hijos que puede tener un Nodo
Grado de un nodo: nº de descendientes directos que tiene
Grado de un árbol: nº de hijos máximo de un nodo
Rama: arista entre dos nodos
Hoja: nodo que no tiene descendientes
Altura de un nodo: longitud del camino descendente más largo
Profundidad de un nodo: longitud de la ruta a su raíz
Peso: nº de nodos del árbol
Factor de equilibrio: diferencia de altura entre subárbol izquierdo y derecho.
Árboles equilibrados (auto-balanceados)
Cuando la diferencia de alturas entre subárboles es max 1
AVL (rotaciones)
AA
Rojo-negro
Splay
Árbol B
Árboles binarios
Árbol binario de búsqueda (BST)
Árbol binario de Fibonacci
Recorridos
Preorden RID
Inorden IRD
Postorden IDR
Tipos de árboles
B:
Cada nodo puede tener más de 2 hijos (orden M)
Mantiene datos ordenados
Muy usados en BBDD y sistemas de ficheros
Inserciones/borrados en tiempo log(n)
Cada nodo tiene como máximo M hijos
Cada nodo tiene mínimo M/2 claves
B+:
Nodos internos solo contienen claves y punteros
Los nodos hoja enlazados entre sí
B*:
Garantizan densidad de ocupación de 2/3
Evita nodos despoblados y que el árbol crezca hacia abajo
Grafos
Completo: cada par de vértices conectado por una arista
Dirigido: las aristas tienen un sentido definido
No dirigido
Conexo: todos sus vértices están conectados por un camino
Multigrafo: más de una arista entre sus vértices
Etiquetado/ponderado: las aristas tienen un valor o peso asociado
Grado de un grafo (nodo)
nº de aristas incidentes en el vértice (nodo)
