Facundo Uferer
🇦🇷 🇺🇸
Contacto

Parte de: Java para Principiantes › TAD Árbol: Recorridos y Árbol Binario de Búsqueda

Estructuras de Datos Jerárquicas

TAD Árboles Binarios y Búsqueda (ABB) en Java

1 de 7
Slide 1 / 7 • Hierarchical Vocabulary

Anatomía y Vocabulario de un Árbol Binario

Estructura jerárquica no lineal donde cada nodo tiene a lo sumo dos descendientes: hijo izquierdo e hijo derecho.

Árbol de 7 Nodos (Hacé click en cualquier nodo) Nodos: 7 | Altura: 3
Nivel 0 Nivel 1 Nivel 2 50 30 70 20 40 60 80
Hacé click en cualquier nodo para inspeccionar su rol, nivel y descendientes.

Conceptos Fundamentales

Raíz (Root)

El único nodo sin padre (aquí: 50). Punto de entrada a la estructura.

Hojas (Leaves)

Nodos sin ningún hijo (izq == null && der == null): 20, 40, 60, 80.

Nivel de un nodo

Distancia en aristas desde la raíz. La raíz está en nivel 0.

Altura (Height)

Cantidad máxima de niveles desde la raíz a la hoja más profunda ($H = 3$).

Definición recursiva: Un árbol binario está vacío (`null`) o consta de un nodo raíz con dos subárboles binarios disjuntos: el subárbol izquierdo y el subárbol derecho.
Slide 2 / 7 • Depth-First Search

Los 3 Recorridos en Profundidad (DFS)

Preorden, Inorden y Postorden: el orden en que se visita la raíz frente a sus subárboles define el propósito del algoritmo.

Simulador de Recorridos en Profundidad Paso 0 de 7
Cinta de Salida (Secuencia Visitada):
Presiona "Paso Siguiente" para comenzar...
Modo Inorden activo. En un ABB, este recorrido entrega los datos ordenados: [20, 30, 40, 50, 60, 70, 80].

Propósitos en el Mundo Real

  • Inorden (L-N-R): En un ABB produce la secuencia de elementos en estricto orden ascendente. Clave para iteradores ordenados.
  • Preorden (N-L-R): Visita la raíz antes que los hijos. Ideal para serializar, clonar o guardar el árbol en archivo preservando la topología.
  • Postorden (L-R-N): Procesa los hijos antes que el padre. Esencial para liberar memoria (destruir hijos primero) o calcular el tamaño acumulado de carpetas en disco. 
void inorden(Nodo n) {
    if (n == null) return;
    inorden(n.izq);
    System.out.print(n.dato + " ");
    inorden(n.der);
}
Slide 3 / 7 • Breadth-First Search

Recorrido por Niveles (BFS) con una Cola

Exploración horizontal piso por piso orquestada mediante una cola auxiliar FIFO.

Exploración por Capas con Cola Auxiliar Nivel 0 en proceso
Cola FIFO (offer / poll):
Orden de Visita por Niveles:
Piso por piso: [50] → [30, 70] → [20, 40, 60, 80]
Cola inicializada con la raíz [50]. Presioná avanzar para desencolar y agregar sus hijos.

Algoritmo BFS Canónico

public void porNiveles(Nodo raiz) {
    if (raiz == null) return;
    Cola<Nodo> cola = new ArrayDeque<>();
    cola.offer(raiz);

    while (!cola.isEmpty()) {
        Nodo actual = cola.poll();
        System.out.print(actual.dato + " ");

        if (actual.izq != null) cola.offer(actual.izq);
        if (actual.der != null) cola.offer(actual.der);
    }
}
Complejidad óptima: Tiempo $O(N)$ visitando cada nodo una vez. Memoria $O(W)$ donde $W$ es el ancho máximo del árbol (hasta $N/2$ nodos en el último nivel de un árbol completo).
Slide 4 / 7 • BST Invariant

Invariante del Árbol Binario de Búsqueda (ABB)

Todo nodo izquierdo es estrictamente menor y todo nodo derecho es mayor. Permite descartar la mitad del árbol en cada comparación.

Búsqueda Binaria O(log N): Buscar un Valor En espera
Ingresa un número (ej. 60, 20, 99) y pulsa buscar.
Para cualquier nodo K: subárbol izquierdo < K, subárbol derecho > K.

El Poder del Descarte Logarítmico

N = 1,000 elementos ≈ 10 comparaciones
N = 1,000,000 elementos ≈ 20 comparaciones
N = 1,000,000,000 elementos ≈ 30 comparaciones
Lista Enlazada O(N) 1,000,000,000 pasos
En cada paso: Comparar con el nodo actual te permite descartar instantáneamente el 50% de los elementos restantes sin siquiera mirarlos.
Slide 5 / 7 • BST Insertion

Simulador de Inserción en ABB

Búsqueda del hueco natural: el nuevo valor desciende comparando hasta hallar un puntero null donde enlazarse.

Inserción Paso a Paso Árbol Dinámico
Presiona "Insertar" para ver la trayectoria del nodo bajando por el árbol hasta enlazarse como hoja.
Base actual: [50, 30, 70, 20, 40, 60, 80].

Algoritmo Recursivo de Inserción

public Nodo insertar(Nodo actual, int dato) {
    if (actual == null) {
        return new Nodo(dato); // Hueco encontrado
    }
    if (dato < actual.dato) {
        actual.izq = insertar(actual.izq, dato);
    } else if (dato > actual.dato) {
        actual.der = insertar(actual.der, dato);
    }
    // Si dato == actual.dato, ya existe (no duplicados)
    return actual;
}
Slide 6 / 7 • Deletion Cases

Eliminación en ABB: Los 3 Casos Críticos

Borrar una hoja, un nodo con un solo hijo o un nodo con dos hijos (sucesor inorden).

Los 3 Escenarios de Eliminación Caso 3: Dos Hijos
Caso 3: Se busca el sucesor inorden (el menor del subárbol derecho: 60) y se reemplaza en la raíz.

Por qué el Sucesor Inorden

El sucesor inorden: Es el elemento inmediatamente mayor que el nodo a borrar. Al ser el más chico de la derecha, se garantiza que es mayor que todo el subárbol izquierdo y menor que todo el resto del subárbol derecho, preservando la invariante del ABB intacta. 
// Caso 3: Dos hijos
Nodo sucesor = encontrarMinimo(nodo.der);
nodo.dato = sucesor.dato; // Copia valor
nodo.der = eliminar(nodo.der, sucesor.dato); // Borra sucesor
Slide 7 / 7 • Degeneration & Self-Balancing

El Problema del Desbalanceo y Rotaciones

Insertar datos ordenados degenera el árbol en una lista enlazada O(N). Los árboles balanceados (AVL y Red-Black) previenen esta catástrofe.

Árbol Balanceado (AVL / Red-Black) Altura H = 3 | Costo O(log N)

Forma piramidal compacta. Descarte del 50% en cada salto.

Árbol Degenerado (Insertado en Orden) Altura H = 7 | Costo O(N)

¡Se convirtió en una lista enlazada disfrazada! Se pierde todo el beneficio del árbol.