3_Estructura de datos Flashcards
(21 cards)
modelo matematico para definir tipos de datos (primitivas)
TAD (tipo abstracto de datos)
concepto mas concreto orientado a la implementacion
Estructura de datos
TAD (PRIMITIVAS)
Stack
push,pop,isEmpty,top =
LIFO
TAD (PRIMITIVAS)
QUEUE
Enqueue,
Dequeue,
IsEmpty
Top
FIFO
TAD (PRIMITIVAS)
LISTA
isEmpty
insertarDelante
insertarDetras
head
tail
buenas complejidades
==> 0 (log (n) ) xa inserciones/borrados
Monticulo
el valor de raiz tiene que ser mayor que todos los que tiene debajo
grado de un nodo
Nº de hijos directos
profundidad de nodo
nº aristas desde la raiz al nodo (nodo raiz =0)
altura de un nodo
trayectoria mas larga desde ese nodo a una hoja
factor de equilibrio
(FE)
diferencia altura entre subarbol izq y derecho
Recorridos en profundidad
Preorden (RID)
Inorden(IRD)
Postorden(IDR)
arboles equilabrados (auto-balanceables)
AVL(rotaciones)
AA
rojo-negro
splay
arbol b
tipo de arbol:
-mantiene los datos ordenados
-inserciones y borrados en tiempo log (n)
-cada nodo tiene como maximo M hijos
-cada nodo (excepto la raiz) tiene como minimo M/2 Claves
Arboles B
tipo de arbol:
-nodos internos solo contienen claves y punteros
-los nodos hojas estan enlazados entre si
arbol B+
tipo de arbol:
Garantiza densidad de ocupacion
arbol B*
algoritmo arbol recubridor minimo
PRIM
KRUSKAL
(Para SPT)
Algoritmos camino minimo
(Protocolos de encaminamiento)
DIJKSTRA
BELLMAN-FORD
A*
Floyd warshall (Camino mínimo entre dos vertices)
algoritmos “caminos xa maximizar el flujo”
FORD-FULKERSON
Algoritmo “Grupos Conexos”
TARJAN
ALgoritmo “Camino minimo entre 2 vertices”
FLOYD-WARSHALL
MyISAM
Secuencial + indexado
