Código en Python Arbol ALV
¿Cómo cambia la cantidad de rotaciones dependiendo del orden de inserción? Probar diferentes secuencias de valores e identificar cuándo y por qué ocurren las rotaciones.
Lista #1 [99, 12, 39, 83, 101, 200]
Lista #2 [73, 1022, 344, 720, 999, 2450, 1, 34]
La cantidad de rotaciones varía en función del orden en que se insertan los valores porque el balance del árbol depende de cómo se distribuyen los nodos en sus subárboles izquierdo y derecho. Si se insertan valores en un orden que crea grandes diferencias en la altura entre los subárboles, el árbol se desbalancea y son necesarias más rotaciones.
Tomando de ejemplo las anteriores 2 listas a medida que se iba ingresando esos valores al árbol, este se iba acomodando según el tamaño de cada nodo, sea en la raíz izquierda o derecha, cuando los valores se iban agregando más hacia la raíz derecha, este generaba un desbalance por lo que hubo que recurrir a las rotaciones para balancear.
Actividad: Ejecutar el código con varias secuencias de valores de inserción y explicar cuántas rotaciones fueron necesarias para equilibrar el árbol en cada caso. ¿Cómo afecta el orden de inserción al equilibrio del árbol?
Con la lista #1 [99, 12, 39, 83, 101, 200]:
Se realizaron 2 rotaciones:
1 rotación derecha para equilibrar el subárbol izquierdo.
1 rotación izquierda para equilibrar el subárbol derecho.
El orden de inserción afectó el equilibrio porque los valores se agruparon de manera que hicieron que el árbol se inclinara tanto hacia la izquierda como hacia la derecha en diferentes momentos.
Con la lista #2 [73, 1022, 344, 720, 999, 2450, 1, 34]:
Se realizaron 2 rotaciones:
1 rotación izquierda.
1 rotación derecha.
El desbalance se produjo cuando se insertaron los valores más grandes (1022, 2450) y más pequeños (1, 34), lo que inclinó el árbol hacia un lado u otro.
¿Por qué es importante mantener un árbol AVL equilibrado?
RTA: Mantener un árbol AVL equilibrado es importante porque asegura que todas las operaciones, como búsqueda, inserción y eliminación, se realicen de manera eficiente. En un árbol equilibrado, la profundidad de cualquier nodo está controlada y las operaciones pueden realizarse en tiempo O(log n), lo que significa que el tiempo necesario para recorrer el árbol crece lentamente incluso cuando aumentan los datos. Si el árbol no está equilibrado, podría volverse desbalanceado y degradarse, haciendo que las operaciones tomen más tiempo.
¿Qué pasaría si no se realizaran las rotaciones necesarias en un árbol AVL? ¿Cómo afectaría eso a la eficiencia de las operaciones de búsqueda, inserción y eliminación?
RTA: Si no se realizaran las rotaciones necesarias, el árbol AVL perdería su propiedad de balance. Esto haría que el árbol se desbalanceara, creando subárboles mucho más largos en un lado que en el otro. Un árbol AVL desbalanceado se parecería a una lista enlazada, donde todas las operaciones (búsqueda, inserción, eliminación) tendrían una complejidad de tiempo O(n) en lugar de O(log n). Esto reduciría drásticamente la eficiencia, ya que las operaciones tendrían que recorrer muchos más nodos, especialmente si se trata de grandes cantidades de datos.
¿Cómo interactúan las funciones recursivas y las rotaciones para garantizar que el árbol se mantenga balanceado después de cada inserción?
Cuando se inserta un nuevo valor en un árbol AVL, la inserción se realiza de manera recursiva, lo que significa que el proceso recorre el árbol comparando el valor del nodo con los nodos existentes, hasta encontrar la posición adecuada. Una vez insertado el nuevo nodo, la recursión retrocede, y en cada paso hacia atrás, se verifica si el árbol ha quedado desbalanceado.
Si se detecta un desbalance (cuando la diferencia de alturas entre los subárboles izquierdo y derecho es mayor a 1), se ejecuta una rotación (izquierda, derecha o doble) para restaurar el equilibrio. Las rotaciones reorganizan los nodos de manera que el árbol vuelva a estar balanceado. Así, las funciones recursivas no solo garantizan que el nuevo nodo se inserte en el lugar correcto, sino que también actualizan las alturas de los nodos y aplican las rotaciones necesarias para mantener el árbol equilibrado.
