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
- 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.
- Búsqueda eficiente:
boolean contiene(T valor)navega descartando la mitad del árbol en cada paso.
- 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.
- 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.