Lección 2: Operaciones Básicas 

1. Búsqueda (Search)

La búsqueda es la operación más intuitiva y la razón por la que los BST son tan eficientes. En lugar de revisar elemento por elemento como en una lista, el árbol nos permite descartar la mitad de las opciones en cada paso. Su eficiencia teórica es de O(log n) en árboles balanceados.

El Algoritmo paso a paso:

1. Comenzamos siempre por la Raíz.

2. Comparamos el valor que buscamos (llamémoslo X) con el valor del nodo actual.

3. Si X es igual al nodo actual, ¡lo encontramos! Terminamos.

4. Si X es menor, nos movemos hacia el hijo izquierdo e iteramos el proceso.

5. Si X es mayor, nos movemos hacia el hijo derecho e iteramos el proceso.

6. Si llegamos a un punto donde no hay más hijos (un valor nulo) y no encontramos X, significa que el valor no existe en el árbol.

3. Eliminación (Delete)

Es el mayor reto algorítmico, ya que el árbol debe reestructurarse para mantener su orden lógico. Se divide en 3 casos:

• Caso 1 (Eliminar una Hoja): Es el más simple. Solo se rompe el enlace con el nodo padre y el recolector de basura de Java libera la memoria.

• Caso 2 (Nodo con un solo hijo): Se hace un "puente". El padre del nodo a eliminar adopta directamente al único hijo (nieto) del nodo borrado.

• Caso 3 (Nodo con dos hijos): Requiere un reemplazo perfecto para no desordenar el árbol.

  1. Se busca el Sucesor Inorden (el valor más pequeño del lado derecho) o el Predecesor (el más grande del lado izquierdo).

  2. Se copia ese valor en el nodo que queremos eliminar.

  3. Finalmente, se borra el Sucesor o Predecesor original (que siempre caerá en el Caso 1 o 2).