BII Tema 3 Secc Estructuras De Datos Flashcards
Concepto monticulo
Max heap: el de arriba el mayor de todos
Min heap: el de arriba el menor de todos.
Estructura basada en arbol que se reconstruye muy eficientemente
Complejidad O log N para inserciones y borrados
Arboles equilibrados
ejemplos
Aquellos arboles cuyo factor de equilibrio está entre -1 , 0 , -1
Autobalanceables: si se inserta un nuevo elemento lo reestructura para que siga siendo equilibrado
Ejemplos :
AVL (Rotaciones es como hace el equilibrado)
AA
Rojo-negro
Splay
Árbol B
Arboles multicamino
(Árboles B)
En cada nodo puede tener más de un dato
- Árbol B : cada nodo puede tener más de 2 hijos.dentro de los nodos está la info y la clave
Datos ordenados
- Árbol B+ : nodos internos solo tienen claves y punteros. Los nodos hoja están entrelazados entre si mediante una lista enlazada. Los datos están en las hojas, en los nodos están los punteros y claves
- Árbol B* : garantiza densidad de ocupación (2/3) muy densos
Recorridos en profundidad de un arbol
Preorden (RID)
Inorden (IRD)
Postorden (IDR)
Grado de un nodo
N° de hijos directos que tiene ese nodo
Profundidad de un nodo
N° de aristas de la raíz al nodo
Altura nodo
Camino más largo de ese nodo hasta una hoja
Factor equilibrio de un árbol
Diferencia altura entre el subárbol izquierdo con el subárbol derecho
Peso del arbol
Sumar todos los nodos
Orden del arbol
N° máximo de hijos que puede tener un nodo
Grado arbol
N° máximo de hijos que tiene alguno de sus nodos
Nivel del arbol
Es la altura de la raíz
la altura de la raiz
árbol vacío sería 0. (Ojo según autor)
Grafos
Estructuras que son un red de nodos
Grafo dirigidos y no dirigidos
Grafos dirigidos : tienen un sentido definido
Grafos no dirigidos : no tienen un sentido, va en los 2 sentidos
Multigrafo
Cuando hay más de un camino para llegar entre dos nodos / vertices
Grafo etiquetado/ponderado
Cuando tiene pesos en las aristas
Grafo conexo
Todos los Nodos conectados entre si por al menos un camino
Grafo. Grado de un vértice/nodo
N° de aristas incidentes
Orden de un grafo
N° de vertices
Grafos. manera de representarlos
Lista adyacencia
Matrices adyacencia
TAD.
Tipo abstracto de datos.
Modelo matemático para definir un tipo de dato/info. Esa info se define mediante sus primitivas( operaciones)
Estructura de datos
Concepto más concreto orientado a la implementación
Implementaciones estructura de datos
Lista ( secuencia)
Colas (queue)
Pila ( stack)
Priority queue (heap)
Árbol
Grafo
Array asociativo
Estructura datos
Estáticas y dinamicas
-Estáticas : tienen un tamaño inicial y no pueden crecer mientras se ejecute el programa. El tamaño se define antes
- simples
- compuestas
-Dinamicas: pueden crecer en N elementos
-Arboles, listas enlazadas, tablas hash
- lineales: pila, cola, lista
- no lineales : arboles, grafos
Concepto tabla hash
Gran estructura de datos
Estructura clave valor
- clave : para indexar
- valor: respecto de su clave. El valor que indexamos
Solución colisiones tabla hash
-Direccionamiento cerrado/ hashing abierto/ encadenamiento separado
Cada casilla del array referencia a una lista, aquí mete los registros que colisionan
- direccionamiento abierto / hashing cerrado
Almacenar directamente en el array. Sondeo de array para ver si la casilla está libre. Donde lineal, cuadrático, doble hasheo
