Skip to content

Tema 6: Estructuras de Datos Jerárquicas (Árboles Complejos)

1. Resumen Ejecutivo

Esta sesión marca el salto de estructuras simples a estructuras optimizadas para rendimiento. Mientras que un Árbol Binario de Búsqueda (ABB) puede degradarse y volverse lento (O(n)), los Árboles AVL y Árboles B introducen mecanismos de "auto-balanceo" para garantizar tiempos de búsqueda eficientes de orden logarítmico (O(\log n)). El foco principal no es la implementación en código (que es compleja), sino entender la lógica de reequilibrio (rotaciones) y las reglas de estructuración de los árboles multicamino.

2. Conceptos Clave

  • Factor de Equilibrio (FE): Valor numérico que indica cuán descompensado está un nodo (Altura derecha - Altura izquierda).
  • Árbol AVL: Árbol Binario de Búsqueda que se mantiene equilibrado automáticamente mediante rotaciones (FE siempre es -1, 0 o 1).
  • Rotación: Operación local para corregir el desequilibrio moviendo nodos y reestructurando enlaces.
  • Árbol Multicamino: Árbol donde un nodo puede tener más de 2 hijos (Grado > 2).
  • Árbol B: Tipo de árbol multicamino auto-balanceado, optimizado para sistemas de almacenamiento y bases de datos.

3. Desarrollo del Temario

3.1. Motivación:El problema de los ABB

En un Árbol Binario de Búsqueda (ABB) normal, la estructura depende totalmente del orden de inserción.

  • El Problema: Si insertamos datos ordenados (ej. 1, 2, 3, 4, 5), el árbol se convierte en una "lista enlazada", perdiendo su eficiencia. La búsqueda pasa de ser rápida a ser lineal O(n).

  • La Solución: Necesitamos árboles que mantengan su altura controlada (O(\log n)) independientemente del orden de inserción. Estos son los Árboles Equilibrados (como el AVL).

3.2. Árboles Equilibrados y Factor de Equilibrio (FE)Para controlar la altura, medimos el "peso" de cada lado del árbol usando el Factor de Equilibrio.

  • Valores de Altura:

  • Árbol vacío: altura = -1.

  • Árbol de 1 nodo: altura = 0.

  • Interpretación del FE:

  • 0: Perfectamente equilibrado.
  • 1 o -1: Equilibrado (aceptable en AVL).

  • > 1: Desequilibrio hacia la derecha (pesa más la derecha).

  • < -1: Desequilibrio hacia la izquierda (pesa más la izquierda).

Nota del Profesor: "Yo esto lo miro como una balanza. Si pesa más un lado, tenemos que realizar una rotación para compensar."

3.3. Árboles AVL (Adelson-Velskii y Landis)Definición: Es un ABB donde el FE de cualquier nodo es estrictamente -1, 0 o 1.

  • Autobalanceable: En cada inserción o borrado, si se rompe la condición de equilibrio (FE sale del rango), el árbol se "arregla" solo.

  • Mecanismo: El arreglo se realiza mediante Rotaciones.

Tipos de RotacionesLas rotaciones buscan subir nodos de la rama larga y bajar nodos de la rama corta para equilibrar la altura. Se realizan de forma ascendente desde el nodo donde ocurre el problema.

  1. Rotación Simple a la Derecha (RSD):

  2. Cuándo se usa: Desequilibrio hacia la izquierda (FE negativo, ej: -2) provocado por un hijo izquierdo.

  3. Lógica: El hijo izquierdo sube a ser la nueva raíz; la antigua raíz baja a la derecha.

  4. Rotación Simple a la Izquierda (RSI):

  5. Cuándo se usa: Desequilibrio hacia la derecha (FE positivo, ej: +2) provocado por un hijo derecho.

  6. Lógica: El hijo derecho sube; la antigua raíz baja a la izquierda.

  7. Rotaciones Dobles (Zig-Zag):

  8. Se usan cuando el desequilibrio no es lineal (ej. el árbol pesa a la derecha, pero el hijo derecho pesa a la izquierda).

  9. Doble a la Derecha: Rotación Izquierda sobre el hijo + Rotación Derecha sobre la raíz.

  10. Doble a la Izquierda: Rotación Derecha sobre el hijo + Rotación Izquierda sobre la raíz.

¡OJO AL DATO!: En el examen o ejercicios, no se trata solo de saber que existe la rotación, sino de identificar cuál aplicar. Si insertas y el camino hace un "codo" (derecha-izquierda o izquierda-derecha), necesitas una rotación doble. Si es recto (derecha-derecha), es simple.

3.4. Árboles Multicamino: Árboles BA diferencia de los binarios, aquí los nodos pueden tener muchos hijos. Son fundamentales en bases de datos y sistemas de archivos.

Reglas del Árbol B (Orden m)1. Estructura del Nodo: Un nodo contiene claves (datos ordenados) que actúan como separadores.

  • Si tengo k claves, tengo k+1 hijos.

  • Ejemplo: Si un nodo tiene las claves [10, 20], tendrá 3 hijos:

  • Hijo 1: Valores < 10.
  • Hijo 2: Valores entre 10 y 20.

  • Hijo 3: Valores > 20 .

  • Llenado:

  • Máximo de hijos: m.

  • Mínimo de hijos: m/2 (excepto raíz y hojas).

  • Hojas: Todas las hojas deben estar al mismo nivel (árbol perfectamente plano por abajo).

Operación de Inserción (Proceso de División)El profesor enfatizó este proceso visualmente:

  1. Buscas la hoja donde debería ir el dato.
  2. Si cabe (nodo no lleno): Lo insertas ordenado.

  3. Si NO cabe (nodo lleno): Ocurre una división (split).

  4. El nodo se parte en dos.

  5. La clave mediana (la del medio) sube al nodo padre.

  6. Las claves menores se quedan en el hijo izquierdo, las mayores en el derecho.

  7. Este proceso puede propagarse hacia arriba (recursivo) si el padre también está lleno.

4. Preguntas de Autoevaluación1. Cálculo de FE: Si un nodo tiene un subárbol derecho de altura 3 y un subárbol izquierdo de altura 1, ¿cuál es su Factor de Equilibrio y qué indica?

  1. Lógica de AVL: Tras insertar el valor 3 en un árbol AVL con nodos 1 (raíz) y 2 (hijo derecho), se produce un desequilibrio. ¿Qué tipo de rotación se debe aplicar?
  2. Estructura Árbol B: En un Árbol B de orden 5, ¿cuál es el número máximo de claves que puede almacenar un nodo antes de tener que dividirse?
  3. Concepto General: ¿Por qué se dice que la complejidad de búsqueda en un AVL es siempre O(\log n) mientras que en un ABB normal puede ser O(n)?