Estructuras de Datos

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

Árboles Avanzados

Los árboles binarios crecen mucho en altura. Si guardamos el árbol en disco, cada nivel que bajamos es una lectura lenta. Los Árboles B (y su variante B+) solucionan esto siendo "árboles gordos": cada nodo puede tener cientos de claves e hijos, reduciendo la altura drásticamente.

Imagen 54. Estructura de un nodo en Árbol B

Imagen 54. Estructura de un nodo en Árbol B

Anatomía de un Nodo B: A diferencia de un nodo binario (1 dato, 2 hijos), un nodo B contiene múltiples claves ordenadas y múltiples punteros a hijos. Esto maximiza el uso de cada bloque de lectura del disco.

14.1 Árboles B y B+: El motor de las Bases de Datos
Mirar en YouTube

Un Trie (pronunciado "trai" o "tri") es un árbol especializado en strings. No guarda la palabra completa en el nodo, sino carácter por carácter. Esto permite que palabras con el mismo inicio (ej: "Casa", "Cama", "Caza") compartan el mismo camino en memoria.

14.2 Tries: Autocompletado
Mirar en YouTube
Imagen 55. Árbol Trie representando un diccionario

Imagen 55. Árbol Trie representando un diccionario

Diagrama lógico: Observa cómo la raíz está vacía y los caminos se bifurcan según las letras. Buscar "Hola" toma 4 saltos, independientemente de cuántas palabras existan en total (O(L)).

main.cpp
#define ALPHABET_SIZE 26

struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    int isEndOfWord; // Marca si aquí termina una palabra válida
};

// Cada nodo es un array de punteros, uno por cada letra posible.
#define ALPHABET_SIZE 26

struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    int isEndOfWord; // Marca si aquí termina una palabra válida
};

// Cada nodo es un array de punteros, uno por cada letra posible.

Los árboles AVL son estrictamente balanceados, lo que hace que insertar sea lento por tantas rotaciones. Los Árboles Rojo-Negro (Red-Black Trees) son una variante que permite un poco más de desbalance a cambio de inserciones más rápidas. Se usan en el kernel de Linux y en librerías estándar.

Imagen 56. Propiedades e Invariantes del Árbol Rojo-Negro

Imagen 56. Propiedades e Invariantes del Árbol Rojo-Negro

Propiedades visuales: 1) La raíz es negra. 2) No puede haber dos nodos rojos seguidos (padre-hijo). 3) Todo camino a una hoja tiene el mismo número de nodos negros.

14.3 Árboles Rojo-Negro (Visión General)
Mirar en YouTube
Volver al nivel