Recursión, Rotación Izquierda Derecha y Balance de Arboles AVL

Recursión en el método insert

¿Qué sucede cuando la función insert() encuentra un nodo vacío? ¿Cómo garantiza la recursión que el árbol se recorre hasta el lugar adecuado?

Cuando la función insert() encuentra un nodo vacío, significa que ha encontrado el lugar donde debe insertarse el nuevo valor. En ese punto, la función crea un nuevo nodo con el valor a insertar. La recursión garantiza que el árbol se recorra hasta el lugar adecuado siguiendo una lógica de comparación: se compara el valor a insertar con el valor del nodo actual y, según sea menor o mayor, se decide recorrer el subárbol izquierdo o el derecho. Este proceso se repite recursivamente hasta encontrar un nodo vacío.

Actividad: Hacer un diagrama de flujo del proceso recursivo de la función insert(). Representar cómo la función se llama a sí misma y cuál es el caso base que detiene la recursión.

1. Iniciar en el nodo raíz.

2. Comparar el valor a insertar con el valor del nodo actual.

3. Si el valor es menor, moverse al subárbol izquierdo; si es mayor, moverse al subárbol derecho.

4. Si se encuentra un nodo vacío, insertar el nuevo valor y detener la recursión.

Rotaciones en los métodos left_rotate y right_rotate

¿Cómo funciona la rotación a la izquierda y a la derecha? Describir el proceso y cómo cambia la estructura del árbol después de una rotación.

Las rotaciones a la izquierda y a la derecha son operaciones que se realizan para mantener el balance de un árbol binario de búsqueda (por ejemplo, un árbol AVL). 

Rotación a la izquierda: Se realiza sobre un nodo que tiene un hijo derecho. El hijo derecho del nodo se convierte en el nuevo nodo raíz del subárbol, y el nodo original se convierte en el hijo izquierdo de este nuevo nodo raíz.

Rotación a la derecha: Se realiza sobre un nodo que tiene un hijo izquierdo. El hijo izquierdo del nodo se convierte en el nuevo nodo raíz del subárbol, y el nodo original se convierte en el hijo derecho de este nuevo nodo raíz.

Estos procesos reorganizan los nodos del árbol de manera que se mantiene el balance, asegurando que las operaciones de inserción, eliminación y búsqueda se realicen de manera eficiente.

Actividad: Realizar un ejercicio en papel donde representen un árbol AVL antes y después de cada rotación (izquierda y derecha). Dibujar las conexiones de los nodos y observar cómo cambia la estructura del árbol.

Relación entre recursión y balance del árbol

¿Cómo se combina la recursión con la verificación del balance del árbol? ¿Cómo se propaga la recursión de vuelta hacia arriba después de insertar un nodo?

La recursión y la verificación del balance del árbol trabajan de la mano para mantener el árbol balanceado después de cada inserción. Después de insertar un nodo, la recursión se propaga de vuelta hacia arriba, verificando y ajustando el balance de cada nodo en el camino de regreso a la raíz. Si se detecta que el balance de algún nodo se ha desviado (por ejemplo, si la diferencia de altura entre los subárboles izquierdo y derecho es mayor que 1), se realizan rotaciones (ya sea a la izquierda o a la derecha) para restaurar el equilibrio.

Actividad: Elegir una secuencia de inserción de valores (por ejemplo, 10, 20, 30, 40, 50) y analizar cómo el árbol se equilibra automáticamente con las rotaciones. Dibujar el árbol en cada paso.