Facundo Uferer
🇦🇷 🇺🇸
Contact

Part of: Java for Beginners › The Tree ADT: Traversals and Binary Search Trees

Hierarchical Data Structures

Binary Trees and Binary Search Trees (BST) in Java

1 of 7
Slide 1 / 7 • Hierarchical Vocabulary

Binary Tree Anatomy and Core Terminology

Non-linear hierarchical structure where each node carries at most two descendants: left child and right child.

Á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

The 3 Depth-First Traversals (DFS)

Preorder, Inorder, and Postorder: visiting the root relative to its subtrees defines the algorithm output.

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

Breadth-First Level-Order Traversal (BFS) with a Queue

Horizontal layer-by-layer exploration coordinated by an auxiliary FIFO queue.

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

The Binary Search Tree (BST) Invariant

Left subtree values are smaller, right values are greater. Discard half the search space at each comparison.

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

Interactive BST Insertion Simulator

Descending through comparisons until reaching a null pointer where the new leaf attaches.

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

BST Deletion: The 3 Critical Cases

Deleting a leaf, a node with 1 child, or a node with 2 children (inorder successor replacement).

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

Tree Degeneration and Balanced Trees

Sorted insertions degrade trees into O(N) linked lists. Self-balancing trees (AVL and Red-Black) maintain O(log N).

Á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.