Sesión 3

Estructura de datos

Lic. Ingeniería en Sistemas y Tecnologías de la Información Sesión 3

INICIAR

Estructura de datos. SESIÓN 3

Bienvenidos a la sesión 3 de nuestra materia Estructura de datos.

Estructura de datos. SESIÓN 3

Para comprender con más detalle los conceptos generales de la asignatura Estructura de datos, es necesario revisar los siguientes temas: 3. Estructuras de Datos No Lineales 3.1. Árboles y sus variantes (binarios, de búsqueda, AVL)3.2. Grafos: algoritmos básicos y representaciones (recorridos, búsqueda de caminos)3.3. Operaciones y algoritmos fundamentales3.4. Análisis de complejidad y optimización de algoritmos en estructuras no lineales

Estructura de datos. SESIÓN 3

Estructuras de Datos No Lineales

Una estructura de datos no lineal es un tipo de estructura de datos donde los elementos no están organizados secuencialmente o en una sola línea. A diferencia de las estructuras de datos lineales (como los arreglos, listas, pilas o colas), donde cada elemento tiene un único predecesor y un único sucesor, en las estructuras no lineales, un elemento puede estar conectado a múltiples elementos, formando relaciones más complejas.Las estructuras de datos no lineales son ideales para representar jerarquías o relaciones más intrincadas entre datos, como la conectividad entre nodos en un grafo o las relaciones entre padres e hijos en un árbol.

NIVEL 0

NIVEL 1

Nivel 2, 3…. , n

Árboles Los árboles son una estructura de datos jerárquica compuesta de nodos, donde cada nodo contiene un valor y referencias a otros nodos denominados "hijos." El nodo superior es conocido como el "nodo raíz", y los nodos que no tienen hijos se llaman "hojas." Los árboles permiten una representación eficiente de relaciones jerárquicas y son fundamentales en muchos algoritmos de búsqueda y ordenación.

Propiedades de los Niveles en un Árbol: Profundidad de un nodo: Se refiere al nivel en el que se encuentra un nodo. Por ejemplo, un nodo en el nivel 2 tiene una profundidad de 2.Altura del árbol: La altura del árbol es el número de niveles o el nivel más profundo del árbol. La altura se cuenta desde el nodo raíz (nivel 0) hasta el nodo hoja más alejado.

Estructura de datos. SESIÓN 3

Árboles BinariosUn árbol binario es un tipo especial de árbol en el que cada nodo puede tener como máximo dos hijos, generalmente denominados hijo izquierdo e hijo derecho. Estos árboles son la base de estructuras más complejas y algoritmos de búsqueda.Propiedades de los árboles binarios:

• Un árbol binario de altura h puede tener hasta 2h −1 nodos.
• La profundidad de un nodo se define como el número de aristas desde la raíz hasta ese nodo.
• Los árboles binarios pueden ser representados eficientemente en memoria mediante arreglos o mediante punteros.

Recorridos: A, B, D, H, I, E, J, K, C, F, L, M, G, N, O

Recorridos: H, D, I, B, J, E, K, A, L, F, M, C, N, G, O

Recorridos:H, I, D, J, K, E, B, L, M, F, N, O, G, C, A

Estructura de datos. SESIÓN 3

Árboles AVLLos árboles AVL son un tipo de árbol binario de búsqueda auto-balanceado, que garantiza que la altura del subárbol izquierdo y derecho de cualquier nodo difieran en no más de uno. Este balanceo asegura que las operaciones de búsqueda, inserción y eliminación sean eficientes, manteniendo una complejidad de tiempo de O(log n).Rotaciones: Para mantener el balance, los árboles AVL utilizan rotaciones simples o dobles cuando la inserción o eliminación desbalancea el árbol. Las rotaciones reestructuran el árbol de manera que se restaure el equilibrio.Inserción en AVL: Similar a los BST, pero con la adición de rotaciones para asegurar el balance.Eliminación en AVL: También similar, pero requiere más operaciones de rotación para garantizar el balance tras la eliminación.Ventajas de los Árboles AVL:Eficiencia garantizada: Las operaciones de inserción, búsqueda y eliminación siempre se ejecutan en O(log⁡n)O(logn), asegurando un rendimiento eficiente.Aplicaciones prácticas: Son útiles en bases de datos y sistemas donde es importante mantener el equilibrio para mejorar el rendimiento de búsqueda

Árboles Binarios de BúsquedaLos árboles binarios de búsqueda (BST, por sus siglas en inglés) son una variante donde cada nodo sigue la propiedad de que todos los nodos en su subárbol izquierdo tienen un valor menor, y todos los nodos en su subárbol derecho tienen un valor mayor.

Estructura de datos. SESIÓN 3

Grafos

Los grafos son estructuras de datos más generales que los árboles, donde un conjunto de nodos (o vértices) están conectados por aristas. Los grafos pueden ser dirigidos (con aristas que tienen una dirección) o no dirigidos (las aristas no tienen dirección).

Grafos Dirigidos (Digrafos)En un grafo dirigido, cada arista tiene una dirección, es decir, una conexión va desde un nodo hacia otro en un solo sentido. Las aristas se representan con flechas que indican el sentido de la relación entre los nodos. Los grafos dirigidos son útiles para modelar relaciones donde el sentido importa, como en los grafos de flujo de datos, redes sociales (quién sigue a quién) o rutas de tráfico.Características:

• Las aristas tienen una dirección.
• Se representan con flechas que apuntan de un nodo origen a un nodo destino.
• Puede haber aristas unidireccionales o bidireccionales (en ambas direcciones).

Ejemplo:Si un grafo dirigido tiene cuatro nodos A, B, C y D, las aristas pueden ser:

Grafos No DirigidosEn un grafo no dirigido, las aristas no tienen una dirección específica, lo que significa que la relación entre dos nodos es bidireccional. En este tipo de grafo, una arista entre dos nodos significa que ambos están conectados de manera recíproca. Este tipo de grafo es ideal para modelar relaciones simétricas, como redes de amigos o conexiones en redes de computadoras.Características:

• Las aristas no tienen dirección; la relación es mutua.
• Se representan como líneas entre dos nodos, sin flechas.
• Si hay una arista entre A y B, ambos nodos pueden interactuar entre sí.

Ejemplo:Si un grafo no dirigido tiene cuatro nodos A, B, C y D, las aristas pueden ser:

El nodo A está conectado tanto a B como a C.B está conectado a A, C y D.C está conectado a A, B y DD está conectado a A y C.

El nodo A tiene una arista dirigida hacia B y hacia D. B tiene una arista que apunta hacia C.C tiene una arista que regresa a A.

Estructura de datos. SESIÓN 3

Búsqueda de CaminosExisten algoritmos especializados como Dijkstra y Bellman-Ford para encontrar el camino más corto en grafos ponderados. Un grafo ponderado es un tipo de grafo en el que cada arista tiene un peso o costo asociado.

1. Algoritmo de Dijkstra:

1. Encuentra el camino más corto desde un nodo fuente a todos los otros nodos en un grafo con pesos no negativos. Utiliza una cola de prioridad para seleccionar el nodo con el camino más corto conocido hasta el momento.
2. Complejidad: O((V+E) log V), donde V es el número de vértices y E es el número de aristas.

2. Algoritmo de Bellman-Ford:

1. Similar a Dijkstra, pero puede manejar grafos con aristas de peso negativo. Evalúa todos los caminos posibles y ajusta los costos de manera iterativa.
2. Complejidad: O(VE), útil cuando los grafos tienen aristas con peso negativo.

3. Algoritmo de Floyd-Warshall:

1. Calcula los caminos más cortos entre todos los pares de nodos. Es útil para grafos densos donde se requiere conocer todos los caminos posibles.
2. Complejidad: O(V 3), menos eficiente en grafos grandes, pero útil para matrices de distancias entre todas las combinaciones de nodos.

Ciclos y ConectividadCiclos: Un grafo contiene un ciclo si existe un camino que empieza y termina en el mismo nodo sin repetir aristas. Los ciclos son importantes en la detección de dependencias o bucles en redes.Conectividad: Un grafo es conexo si existe un camino entre cualquier par de nodos. Para verificar la conectividad, se puede utilizar DFS o BFS. Los componentes conexos son subgrafos dentro de un grafo no dirigido, donde cada par de nodos está conectado por un camino.

Estructura de datos. SESIÓN 3

Algoritmos Básicos en GrafosRecorridos en GrafosEl recorrido de grafos se refiere al proceso de visitar todos los nodos de un grafo en un orden específico. Existen dos algoritmos principales para recorrer un grafo: Búsqueda en Anchura (BFS) y Búsqueda en Profundidad (DFS). Ambos algoritmos se utilizan para explorar grafos, pero lo hacen de manera diferente.

1. Búsqueda en Profundidad (DFS):

1. Explora tan lejos como sea posible a lo largo de cada rama antes de retroceder. Utiliza una pila (o la recursión) para llevar un seguimiento de los vértices visitados.
2. Aplicaciones: detección de ciclos, caminos en laberintos, análisis de conectividad.

Busqueda en Profundidad

2. Búsqueda en Anchura (BFS) Es un algoritmo utilizado para recorrer o buscar en grafos, tanto dirigidos como no dirigidos. Este algoritmo explora los nodos de un grafo por niveles, es decir, primero visita todos los nodos vecinos al nodo inicial, luego los vecinos de esos vecinos, y así sucesivamente. BFS utiliza una cola para llevar un seguimiento de los nodos a visitar y un conjunto para marcar los nodos ya visitados.

Busqueda en Anchura

Estructura de datos. SESIÓN 3

Operaciones y Algoritmos Fundamentales

Las estructuras de datos no lineales como los árboles y los grafos requieren operaciones específicas para su manipulación. Las operaciones más comunes incluyen la inserción, eliminación, búsqueda y recorridos, cada una de las cuales puede variar dependiendo de la estructura en cuestión.

Árbol Binario de Búsqueda (BST)Operaciones comunes en BST:

• Inserción: Para insertar un valor, se compara con el nodo actual y se desplaza al subárbol izquierdo o derecho según corresponda, repitiendo hasta encontrar una posición vacía.
• Búsqueda: Se sigue un proceso similar de comparación, desplazándose a la izquierda o derecha hasta encontrar el valor o llegar a una hoja vacía.
• Eliminación: Es un poco más complicada y tiene tres casos: el nodo a eliminar es una hoja, tiene un solo hijo, o tiene dos hijos.

El rendimiento de estas operaciones depende de la altura del árbol, que puede ser lineal en el peor de los casos (cuando el árbol se degenera en una lista enlazada).

Algoritmo de Búsqueda en un BST

Se puede implementar mediante clases, donde cada nodo tiene tres atributos principales: el valor del nodo y dos punteros (referencias) para los hijos izquierdo y derecho.

Estructura de datos. SESIÓN 3

Estructura de datos. SESIÓN 3

Operaciones en Grafos

Representación de GrafosLista de Adyacencia: Es una representación común y eficiente en términos de espacio, especialmente cuando el grafo es disperso. Cada nodo tiene una lista de nodos a los que está conectado directamente.

1. Ventaja: Eficiente en términos de memoria.
2. Desventaja: Acceder a una arista específica puede ser lento.

Matriz de Adyacencia: Es una matriz de n×n (siendo n el número de nodos), donde cada posición [i,j] indica si existe una arista entre los nodos i y j.

1. Ventaja: Acceso rápido a las aristas.
2. Desventaja: Poco eficiente en términos de espacio si el grafo es disperso.

Estructura de datos. SESIÓN 3

Análisis de Complejidad y Optimización de Algoritmos en Estructuras No Lineales

Optimización de AlgoritmosLa optimización en estructuras no lineales se enfoca en:Balanceo: En árboles, mantener el balance es esencial para reducir el tiempo de búsqueda e inserción. Estructuras como los Árboles AVL o Árboles Rojo-Negro garantizan que el árbol no se degrade en su forma.Estructuras de datos especializadas: En grafos, usar una representación eficiente (lista de adyacencia en vez de matriz) puede mejorar significativamente el rendimiento en memoria y velocidad de acceso.Uso de estructuras auxiliares: El uso de colas de prioridad en Dijkstra, por ejemplo, optimiza la búsqueda del camino más corto.Ejemplo de Optimización:Para un grafo muy denso (con muchas aristas), el uso de una lista de adyacencia reducirá el uso de memoria y mejorará la velocidad en comparación con una matriz de adyacencia, que ocuparía O(V 2) en espacio.

Complejidad de las Operaciones en ÁrbolesÁrboles Binarios de Búsqueda (BST):Inserción, Búsqueda y Eliminación:En el mejor de los casos, donde el árbol está balanceado, la complejidad es O(log n) porque se reduce el problema a la mitad en cada paso.En el peor de los casos (si el árbol está desbalanceado y se convierte en una lista enlazada), la complejidad es O(n).Árboles AVL:Al estar balanceados automáticamente, garantizan una complejidad de tiempo de O(log n) para todas las operaciones, ya que las rotaciones aseguran que el árbol no se desbalancee.

Estructura de datos. SESIÓN 3

Recursos bibliográficos

• Hernández Bejarano, M. & Baquero Rey, L. E. (2022). Estructuras de datos: fundamentación práctica: (1 ed.). RA-MA Editorial. Consulta de la página 302 a 318.

Recuperado de: https://elibro.net/es/ereader/udibiblioteca/230581

Estructura de datos. SESIÓN 3

Recursos bibliográficos

• Rodríguez, L. (2012). Estructuras no lineales de datos: árboles . Colimbo. Revisa el documento en el cual conocerás más acerca de las estructuras de datos no lineales especificamente de tipo árbol.

Recuperado de: https://www.colimbo.net/documentos/documentacion/113/FPII04_Estructuras_no_lineales_de_datos.pdf

Estructura de datos. SESIÓN 3

MarkTech (2024, 08 de octubre). ESTRUCTURAS DE DATOS NO LINEALES. [video]. Revisa el video en el cual explica la teoría y la implementación de los datos lineales.

Recuperado de: https://www.youtube.com/watch?v=em3mENEHHQU

Nivel 0

El nivel 0 corresponde al nodo raíz del árbol. Es el nodo principal a partir del cual se ramifican todos los demás nodos. No tiene ningún nodo antecesor.

Preorden (raíz, izquierda, derecha): recorre primero la raíz, ideal para copiar el árbol.

Nivel 1

Los nodos en el nivel 1 son los hijos directos del nodo raíz. Son los nodos que están conectados directamente con el nodo raíz mediante una sola arista.

Inorden (izquierda, raíz, derecha): útil para obtener los nodos en orden ascendente.

Nivel 2, 3…. , n

Los nodos en niveles posteriores son los descendientes de los nodos del nivel anterior. Es decir, un nodo en el nivel 2 es hijo de un nodo del nivel 1, y así sucesivamente. Cuanto mayor es el nivel, mayor es la distancia del nodo con respecto a la raíz.

Postorden (izquierda, derecha, raíz): ideal para borrar o liberar nodos en programas.