Contexto

A diferencia de las colecciones lineales donde la búsqueda secuencial cuesta O(N), un Árbol Binario de Búsqueda (BST) organiza la información jerárquicamente imponiendo un invariante de orden: Para cualquier nodo $X$ del árbol:

  • Todos los elementos del subárbol izquierdo de $X$ son estrictamente menores que $X$.
  • Todos los elementos del subárbol derecho de $X$ son estrictamente mayores que $X$.

Gracias a esta propiedad, en un árbol balanceado la búsqueda, inserción y consulta se reducen a tiempo logarítmico $O(\log N)$.

Consigna

Vas a implementar un ArbolBinarioBusqueda<T extends Comparable<T>> completamente funcional en Java.

1. Estructura de Clases y Nodos

public class ArbolBinarioBusqueda<T extends Comparable<T>> {
    
    private static class NodoArbol<T> {
        T dato;
        NodoArbol<T> izquierdo;
        NodoArbol<T> derecho;

        NodoArbol(T dato) {
            this.dato = dato;
        }
    }

    private NodoArbol<T> raiz;
    private int tamano;
    // ...
}

2. Operaciones Algorítmicas

  1. Inserción recursiva:
    • Si la raíz es nula, el nuevo nodo se convierte en la raíz.
    • De lo contrario, descender comparando: si valor.compareTo(actual.dato) < 0, avanzar al subárbol izquierdo; si es mayor, al derecho.
  2. Búsqueda eficiente:
    • boolean contiene(T valor) navega descartando la mitad del árbol en cada paso.
  3. Recorridos canónicos:
    • In-Order: Subárbol izquierdo $\rightarrow$ Raíz $\rightarrow$ Subárbol derecho (produce la secuencia ordenada).
    • Pre-Order: Raíz $\rightarrow$ Subárbol izquierdo $\rightarrow$ Subárbol derecho.
    • Post-Order: Subárbol izquierdo $\rightarrow$ Subárbol derecho $\rightarrow$ Raíz.
  4. Métricas estructurales:
    • Altura del árbol: $1 + \max(\text{altura}(izq), \text{altura}(der))$.
    • Mínimo y máximo: navegar persistentemente por el puntero izquierdo o derecho respectivamente.