Necesitas reconocer raíz, subárbol, altura y recorridos; todos se trabajan en la sección anterior.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Invariante ABB con Buscar e insertar y resolver un caso nuevo.
Reserva entre 75 y 120 minutos o divide el laboratorio en dos sesiones.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Invariante ABB y Buscar e insertar? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Construirás un diccionario ordenado y entenderás por qué su rendimiento depende de la forma del árbol.
Al terminar podrás
- Cada nodo divide las claves en dos regiones
- La altura limita el número de comparaciones
- La eliminación tiene tres casos y debe conservar el invariante
01
Invariante de orden
Cada nodo divide las claves en dos regiones
En un ABB, todas las claves del subárbol izquierdo son menores y todas las del derecho son mayores, según un comparador. La política para duplicados debe ser explícita: reemplazar, contar, rechazar o almacenarlos de otra manera.
La condición aplica a todo el subárbol, no solo a los hijos.
compareTo o Comparator define el orden.
Inorden devuelve las claves en orden.
¿Basta con que cada hijo izquierdo sea menor que su padre?
Mostrar respuesta ＋
No. Todos los descendientes izquierdos deben ser menores que el nodo, y todos los derechos mayores.
02
Buscar e insertar
La altura limita el número de comparaciones
Buscar e insertar siguen una sola rama hasta encontrar la clave o una referencia null. El costo es O(h), donde h es la altura. En un árbol equilibrado h es O(log n); al insertar claves ordenadas puede degradarse a O(n).
La raíz de un árbol vacío es null.
La inserción termina en un enlace vacío.
Una secuencia de entrada puede cambiar completamente la forma.
¿Por qué Big O de un ABB no siempre es O(log n)?
Mostrar respuesta ＋
Porque un ABB común no garantiza equilibrio. Su costo depende de h y el peor caso tiene altura n.
03
Eliminar
La eliminación tiene tres casos y debe conservar el invariante
Una hoja se desconecta; un nodo con un hijo se reemplaza por ese hijo; uno con dos hijos puede reemplazarse por su sucesor inorden y después eliminar ese sucesor. La operación debe devolver la nueva raíz del subárbol para reconectar correctamente.
Caso cero hijos: retorna null.
Caso un hijo: retorna el hijo existente.
Caso dos hijos: copia sucesor y elimina el duplicado.
¿Por qué no basta con desconectar el nodo con dos hijos?
Mostrar respuesta ＋
Porque ambos subárboles quedarían sin un enlace válido. El sucesor o predecesor permite reconectarlos manteniendo el orden.
Tu recorrido en tres ideas
- Cada nodo divide las claves en dos regiones
- La altura limita el número de comparaciones
- La eliminación tiene tres casos y debe conservar el invariante
Implementa y rompe deliberadamente un ABB
Une invariante global, recursión, casos de eliminación, altura y degradación por orden de entrada.
CASO
El diccionario funciona con datos mezclados, pero se vuelve lento cuando recibe identificadores crecientes.
Procedimiento
- Implementa buscar, insertar y eliminar devolviendo la raíz actualizada.
- Comprueba recursivamente límites mínimo y máximo en todo el árbol.
- Compara altura y tiempo con entradas ordenadas y aleatorias.
Evidencia mínima
- Pruebas de los tres casos de eliminación.
- Verificador del invariante global.
- Altura y comparación por secuencia de entrada.
Mostrar razonamiento modelo ＋
El árbol ordenado sigue siendo un ABB válido, pero tiene altura n. La auditoría separa corrección de rendimiento y motiva una estructura autoequilibrada cuando el peor caso importa.
Para ir más lejos¿Qué garantía adicional aporta un AVL o un árbol rojo-negro?
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Comprobar orden solo contra el padre inmediato.
Eliminar un nodo con dos hijos sin reconectar ambos subárboles.
Ahora hazlo sin guía
Implementa put, contains y remove para un ABB genérico con una política explícita de duplicados.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- El inorden queda ordenado tras cada cambio.
- Prueba cero, uno y dos hijos.
- Mide el efecto de entradas ordenadas y mezcladas.