Organizar datos en jerarquías: un nodo ya no tiene un solo camino hacia adelante, puede tener varios.
Una función es recursiva cuando se resuelve llamándose a sí misma con una versión más chica del mismo problema, hasta llegar a un caso base tan simple que ya no necesita llamarse de nuevo.
como una muñeca rusa: cada caja abre una más chica, hasta llegar a la que ya no tiene nada adentro
factorial(n) = n × factorial(n − 1), hasta llegar al caso base: factorial(0) = 1.
| Paso | Qué pasa |
|---|---|
| factorial(3) | llama a factorial(2) |
| factorial(2) | llama a factorial(1) |
| factorial(1) | llama a factorial(0) |
| factorial(0) | = 1 (caso base, no llama a nadie más) |
| factorial(1) | = 1 × 1 = 1 |
| factorial(2) | = 2 × 1 = 2 |
| factorial(3) | = 3 × 2 = 6 |
las llamadas que esperan su turno se van apilando — igual que una pila (LIFO): la última en entrar es la primera en resolverse
Hasta ahora, cada nodo tenía un solo camino hacia adelante. En un árbol, un nodo puede tener varios hijos al mismo tiempo.
Un solo camino. Cada nodo lleva únicamente al siguiente, en línea recta.
Se puede ramificar. Un nodo lleva a varios nodos distintos, formando niveles.
Un árbol se arma con relaciones de padres e hijos.
Cada nodo guarda un valor y dos referencias: al hijo izquierdo y al hijo derecho.
Un nodo puede tener 0, 1 o 2 hijos — nunca más de dos. Por eso se llama binario.
Esa única regla, aplicada en cada nodo, es lo que hace que buscar en un árbol de búsqueda sea mucho más rápido que en una lista.
Vamos a insertar el valor 5 en el árbol de la diapositiva anterior.
| Comparación | Decisión |
|---|---|
| 5 vs. 8 (raíz) | 5 < 8 → ir a la izquierda |
| 5 vs. 3 | 5 > 3 → ir a la derecha |
| 5 vs. 6 | 5 < 6 → ir a la izquierda |
| 6 no tiene hijo izquierdo | lugar vacío se inserta el 5 ahí |
El 5 quedó como hijo izquierdo del 6, tal como lo fuimos decidiendo paso a paso.
"Recorrer" un árbol es pasar por todos sus nodos, uno por uno. El orden en que visitas izquierda, nodo y derecha define el recorrido. Vamos a ver los tres, uno a la vez, con el mismo árbol de antes (sin el 5).
En cada nodo, primero se visita todo el subárbol izquierdo, después el nodo, y al final el subárbol derecho. El número en cada nodo es el orden en que se visita.
dato curioso: en un árbol de búsqueda, el in-order siempre da los valores ordenados
En cada nodo, primero se visita el propio nodo, después todo el subárbol izquierdo, y al final el subárbol derecho.
En cada nodo, primero se visita todo el subárbol izquierdo, después el subárbol derecho, y al final el propio nodo.
| Lista enlazada | Árbol de búsqueda | |
|---|---|---|
| Buscar un valor | Revisar uno por uno, desde el inicio | Descartar la mitad restante en cada paso |
| Estructura | Lineal, en fila | Jerárquica, por niveles |
| Ideal para | Mantener un orden de llegada | Búsquedas rápidas sobre datos ordenados |
Árbol: nodos organizados en niveles, con relaciones de padres e hijos.
Árbol binario: cada nodo tiene como máximo dos hijos, izquierdo y derecho.
Árbol de búsqueda: los menores van a la izquierda y los mayores a la derecha — esa regla acelera las búsquedas.
Recorridos: in-order, pre-order y post-order visitan los mismos nodos, pero en distinto orden.