4. Estructuras jerárquicas (árboles)

Cada nodo puede tener varios hijos; en un binario como máximo dos. Los BST ordenan los datos de forma que los recorridos y las búsquedas tienen significado algorítmico claro.

Árbol binario de búsqueda (BST)

Invariante: subárbol izquierdo < nodo < subárbol derecho (para claves comparables). Inserción y búsqueda promedio O(log n) si el árbol está balanceado; en el peor caso (lista encadenada) O(n).

            (8)
           /   \
        (3)     (10)
        / \        \
      (1) (6)      (14)
          / \        /
        (4) (7)    (13)

Nodo BST

JAVA

  public class NodoBST { 
      int valor; 
      NodoBST izquierdo; 
      NodoBST derecho; 
    
      public NodoBST(int valor) { 
          this.valor = valor; 
      } 
  } 

Recorridos

In-order (izq, raíz, der): en BST devuelve claves ordenadas.
Pre-order (raíz, izq, der): útil para copiar/serializar forma del árbol.
Post-order (izq, der, raíz): útil para borrar de abajo hacia arriba.

In-order: 1, 3, 4, 6, 7, 8, 10, 13, 14
          (visitar izquierdo → raíz → derecho en cada subárbol)

Árboles balanceados (AVL, red-black)

Para evitar degenerar a lista, se mantienen invariantes de altura o color de enlaces. AVL: rotaciones simples/dobles cuando el factor de balance se desvía. Red-black: reglas de color y nil; la base de muchos TreeMap en Java.

Antes (desbalanceado a la izquierda):     Después de rotar a la derecha en raíz:

       (A)                                      (B)
      /                                           / \
    (B)     ──▶                               (C)   (A)
    / \                                           / \
  (C) (x)                                       ...   (x)

Propuesta: implementá primero BST sin balanceo; medí altura con datos aleatorios vs ordenados. Luego leé la ficha teórica de rotaciones y dibujá cada caso en papel.

Heap (cola de prioridad)

Árbol binario completo almacenado en arreglo: hijos de i en 2i+1 y 2i+2 (o índices 1-based con otra fórmula). Max-heap: padre ≥ hijos; peek O(1), insert/extract O(log n).

Uso típico en Java (JDK)