Fundamentos de Estructuras de Datos y Algoritmos Clave

Árbol de Búsqueda Binario (BST)

Un Árbol de Búsqueda Binario (BST, por sus siglas en inglés) es una estructura de datos jerárquica con las siguientes propiedades:

• Cada nodo tiene como máximo dos hijos: uno izquierdo y uno derecho.
• Los valores de los nodos cumplen la siguiente propiedad:
  • Todos los valores del subárbol izquierdo son menores que el valor del nodo.
  • Todos los valores del subárbol derecho son mayores que el valor del nodo.
• No necesariamente está balanceado, lo que significa que su forma puede volverse desigual, con ramas mucho más largas que otras.

Ventajas del BST

• Es fácil de implementar.
• Ideal para búsquedas rápidas si el árbol está equilibrado.

Desventajas del BST

• Puede degenerarse en una lista enlazada si los datos están ordenados al insertarlos, resultando en un rendimiento de O(n) en búsquedas.

Algoritmo de Dijkstra

El Algoritmo de Dijkstra es fundamental para encontrar rutas óptimas en grafos.

• Propósito: Encuentra la ruta más corta desde un nodo inicial hasta todos los demás nodos en un grafo ponderado (sin pesos negativos).
• Tipo de grafo: Dirigido o no dirigido, ponderado.
• Requiere: Un grafo representado con una lista de adyacencia, donde los pesos de las aristas sean fáciles de acceder.
• Eficiencia: O(V log V + E) con cola de prioridad (heap).

Algoritmo de Kruskal

El Algoritmo de Kruskal es utilizado para construir árboles de expansión mínimos.

• Propósito: Encuentra el Árbol de Expansión Mínimo (MST), que conecta todos los nodos del grafo con el costo total mínimo.
• Tipo de grafo: No dirigido, ponderado.
• Requiere: Una representación donde sea fácil listar todas las aristas y sus pesos, como una lista de adyacencia o una lista de aristas.
• Eficiencia: O(E log E), ya que clasifica las aristas por peso.

Árbol Balanceado

Un Árbol Balanceado es un Árbol Binario de Búsqueda que mantiene una estructura equilibrada. Esto significa que:

• La diferencia de altura entre los subárboles izquierdo y derecho de cualquier nodo no supera un valor constante (generalmente 1).
• Garantiza operaciones de búsqueda, inserción y eliminación en tiempo O(log n).

Ejemplos Comunes de Árboles Balanceados

Árbol AVL

• Un Árbol AVL es un árbol de búsqueda binario balanceado que realiza rotaciones para mantener el equilibrio.
• Rendimiento: Consistente para todas las operaciones (O(log n)).
• Desventaja:
  • Más complejo de implementar.
  • Las operaciones de inserción y eliminación pueden requerir reequilibrar el árbol.