En la última parte de la solución dice hacer una rotación derecha en el 7 cuando es una rotación izquierda. Quería saber si efectivamente es un error o ese año se tomó una convención distinta en cuanto a rotaciónes refiere. A su vez me gustaría saber cuál es la que se va a considerar en el parcial. Muchas gracias
En respuesta a Nicolás Alejandro Rivoir Malán
Re: Error solución parcial 2019 Ej 1a
de Fernando Fernandez -
Sí, es un poco confusa la nomenclatura.
Hay una manera de describirla por como se mueven los nodos y otra por qué inserción es lo que causa el desbalance y determina qué rotación o rotaciones hay que hacer.
En ese caso es una rotación hacia la izquierda porque el nodo que estaba en la raíz y un subárbol (el que tiene raíz en 8) del subárbol derecho pasan al subárbol izquierdo y un nodo del subárbol derecho, el 9, pasa a la raíz. Gráficamente es como si se hiciera un giro hacia la izquierda.
La otra forma de describirlo es qué inserción es lo que la causa. Pero en esta notación siempre hay que usar dos letras. En este caso sería LR. El nodo que quedó desequilibrado es el 10. La inserción se hizo en su subárbol izquierdo, de ahí sale la L. Y además se hizo en el subárbol derecho de su hijo izquierdo, el 7, y de ahí sale la R. Tal vez sería más completo decir 'rotaciones causadas por un desbalance tras una inserción LR' en vez de la versión abreviada rotación LR.
La forma de determinar que nomenclatura se está usando es si se usan dos letras o no.
Como en general la rotación no necesariamente tiene que ser causada por una inserción, sino que también puede ser causada por un borrado la nomenclatura de las dos letras no siempre se puede usar.
En este caso tenemos rotaciones causadas por un desbalance tras una inserción LR que consisten en una rotación hacia la izquierda y luego otra hacia la derecha
En respuesta a Fernando Fernandez
Re: Error solución parcial 2019 Ej 1a
Muchas gracias. Quería dejar dicho, por si alguien más lo lee, que está mal el título, me confundí. No es el parcial de 2019 sino el examen de juio.
En respuesta a Nicolás Alejandro Rivoir Malán
Re: Error solución parcial 2019 Ej 1a
de Fernando Fernandez -
Bien.
Ahí está explicado casi en los mismos términos que usé en la explicación anterior: es una inserción izquierda-izquierda que produce un desbalance que se corrige, en este caso, con una única rotación a la derecha.
Editado viernes 17 de junio, 17:35 Donde decía balance debe decir desbalance.