Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 10

Árboles Balanceados y Heaps

La promesa de búsqueda en O(log n) del Árbol Binario de Búsqueda (ABB) tiene una debilidad fatal: depende de que el árbol esté "lleno". Si insertamos datos ya ordenados (ej: 1, 2, 3, 4, 5), el árbol crece solo hacia la derecha, degenerando en una Lista Enlazada con rendimiento O(n).

Imagen 39. Árbol Equilibrado vs Árbol Degenerado

Imagen 39. Árbol Equilibrado vs Árbol Degenerado

Comparativa crítica: A la izquierda, un árbol equilibrado (ideal). A la derecha, un árbol "degenerado" o "sesgado" (skewed) que ocurre al insertar datos ordenados, perdiendo toda eficiencia.

10.1 ¿Por qué balancear? El árbol degenerado
Mirar en YouTube

Los árboles AVL (Adelson-Velsky y Landis) resuelven la degeneración vigilando la altura. Cada nodo mantiene un "Factor de Equilibrio" (altura derecha - altura izquierda). Si este factor sale del rango [-1, 0, 1], el árbol aplica una "rotación" para restaurar el balance inmediatamente.

Imagen 40. Tipos de rotaciones en árboles AVL

Imagen 40. Tipos de rotaciones en árboles AVL

Mecánica de corrección: Diagrama de los 4 tipos de rotaciones (Simple Derecha, Simple Izquierda, Doble Izquierda-Derecha, Doble Derecha-Izquierda) usadas para reacomodar los nodos.

10.2 Árboles AVL: Rotaciones
Mirar en YouTube
main.cpp
struct NodoAVL {
    int dato;
    struct NodoAVL *izquierda;
    struct NodoAVL *derecha;
    int altura; // Dato extra vital para el balanceo
};

int getAltura(struct NodoAVL *n) {
    if (n == NULL) return 0;
    return n->altura;
}
struct NodoAVL {
    int dato;
    struct NodoAVL *izquierda;
    struct NodoAVL *derecha;
    int altura; // Dato extra vital para el balanceo
};

int getAltura(struct NodoAVL *n) {
    if (n == NULL) return 0;
    return n->altura;
}

A diferencia de un ABB donde el orden es izquierda/derecha, en un Heap (Montículo) el orden es vertical: el Padre siempre es mayor (Max-Heap) o menor (Min-Heap) que sus hijos. Además, el árbol siempre debe ser "completo", llenándose de izquierda a derecha.

10.3 Heaps: La cola de prioridad
Mirar en YouTube
Imagen 41. Estructura lógica de un Max-Heap

Imagen 41. Estructura lógica de un Max-Heap

Diagrama conceptual: Un Max-Heap visualizado como árbol. Nota que la raíz es el elemento máximo absoluto, y no hay relación de orden estricta entre hermanos ("hermano izquierdo" vs "hermano derecho").

Gracias a que el Heap es un árbol completo, no necesitamos punteros ni structs complejos. Podemos aplanarlo en un simple Array. Para un nodo en índice "i", su hijo izquierdo está en "2i+1" y el derecho en "2i+2".

Imagen 42. Representación de un Heap en un Array

Imagen 42. Representación de un Heap en un Array

Correspondencia Visual: Arriba el árbol conceptual, abajo el array real en memoria. Las flechas muestran cómo se calculan las posiciones sin punteros.

10.4 Implementación de Heaps en Arrays
Mirar en YouTube
main.cpp
// Macros o funciones inline para navegación rápida
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return (2 * i) + 1; }
int rightChild(int i) { return (2 * i) + 2; }

// Ejemplo: Insertar requiere comparar arr[i] con arr[parent(i)]
// y hacer swap si el hijo es mayor que el padre (en Max-Heap).
// Macros o funciones inline para navegación rápida
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return (2 * i) + 1; }
int rightChild(int i) { return (2 * i) + 2; }

// Ejemplo: Insertar requiere comparar arr[i] con arr[parent(i)]
// y hacer swap si el hijo es mayor que el padre (en Max-Heap).
Volver al nivel