Los arbolesAVLfueron descubiertos por matemáticos rusos Adel son Vel skii y Landis (avl), en el año 1962. Estos arboles tienen la propiedad de que la altura de la rama izquierda, menos la altura de la rama derecha difiere en un máximo de uno
la altura de la rama izquierda es 1 y la altura de la rama derecha es 1 por lo cual el árbol es AVL al restar las alturas de la rama izquierda y de la rama derecha el resultado es 0. Se define como factor de balance de cada nodo la diferencia de alturas de la rama izquierda y la derecha pertenecientes a dicho nodo, De acuerdo a esto el factor de balance para cada no es .
El factor de balance siempre se calcula con base en la diferencia entre las alturas de la rama izquierda y la rama derecha. Veamos este árbol:
El factor de balance para cada nodo es.
A => 2 - 3=-1
B => 1 - 0= 1
C => 2 - 1= 1
D => 0 - 0= 0 hoja
E => 0 -1 = -1
F => 0 -0 = 0 hoja
G => 0 -0 = 0 hoja
Veamos el árbol anterior con los factores de balance en cada nodo
podemos afirmar, entonces que toda hoja tiene un factor de balance igual a 0 y que un árbol es AVL si el factor de balance de todos y cada uno de los nodos que componen al árbol están en el rango -1..+1.
Basados en lo anterior se determinara si el siguiente árbol es AVL:
Calculando el factor de balance para cada nodo se ve así
El árbol anterior no es AVL ya que el factor de balance de los nodos A y E no están en el rango -1 ..+1 para que el árbol pueda llamarse avl, como se puede observar para el estudio de los arboles AVL es necesario que cada nodo incluya una variable adicional que almacene el factor de balance de ese nodo lo cual implica diseñar cada nodo así.
struct nodo{
int info;
int bal;
struct nodo *izq;
struct nodo *der;
};
La variable bal, tiene como función almacenar el factor de balance para ese nodo. esta variable tendra un numero en el rango -1..+1 cuando se exija que el arbol tenga las propiedades de un arbol avl
la altura de la rama izquierda es 1 y la altura de la rama derecha es 1 por lo cual el árbol es AVL al restar las alturas de la rama izquierda y de la rama derecha el resultado es 0. Se define como factor de balance de cada nodo la diferencia de alturas de la rama izquierda y la derecha pertenecientes a dicho nodo, De acuerdo a esto el factor de balance para cada no es .
El factor de balance siempre se calcula con base en la diferencia entre las alturas de la rama izquierda y la rama derecha. Veamos este árbol:
El factor de balance para cada nodo es.
A => 2 - 3=-1
B => 1 - 0= 1
C => 2 - 1= 1
D => 0 - 0= 0 hoja
E => 0 -1 = -1
F => 0 -0 = 0 hoja
G => 0 -0 = 0 hoja
Veamos el árbol anterior con los factores de balance en cada nodo
podemos afirmar, entonces que toda hoja tiene un factor de balance igual a 0 y que un árbol es AVL si el factor de balance de todos y cada uno de los nodos que componen al árbol están en el rango -1..+1.
Basados en lo anterior se determinara si el siguiente árbol es AVL:
Calculando el factor de balance para cada nodo se ve así
El árbol anterior no es AVL ya que el factor de balance de los nodos A y E no están en el rango -1 ..+1 para que el árbol pueda llamarse avl, como se puede observar para el estudio de los arboles AVL es necesario que cada nodo incluya una variable adicional que almacene el factor de balance de ese nodo lo cual implica diseñar cada nodo así.
struct nodo{
int info;
int bal;
struct nodo *izq;
struct nodo *der;
};
La variable bal, tiene como función almacenar el factor de balance para ese nodo. esta variable tendra un numero en el rango -1..+1 cuando se exija que el arbol tenga las propiedades de un arbol avl
Concepto de rotacion
L palabra rotación expresa movimiento alrededor de un eje fijo. Para el caso de los arboles vamos a definir una rotación como el ajuste de varios apuntadores con el propósito de convertir un árbol no-AVL. en AVL por ejemplo el siguiente.
Es AVL y no existe rotacion ya que tiene propiedades AVL , si al nodo anterior le adicionamos un nodo a la izquierda de B los nuevos factores de balance serán.
El arbol ha perdido las propiedades AVL es necesario rotar el árbol para que mantenga las propiedades AVL. Una rotacion exige el ajuste de algunos apuntadores con dos propositos fundamentales.
- Que el arbol siga siendo AVL
- Que su recorrido en inorden se igual antes de la rotación y después de ella.
Para el caso anterior el recorrido en inorden es C B A
EJ:
Si insertamos el nodo G a la izquierda de F el árbol quedara así
Este nuevo árbol en in-orden queda así:
D B E A G F C
Si deseamos mantener el árbol con propiedades AVL es necesario efectuar una rotación de tal manera que el recorrido en in-orden sea exactamente igual antes de rotarlo.
L palabra rotación expresa movimiento alrededor de un eje fijo. Para el caso de los arboles vamos a definir una rotación como el ajuste de varios apuntadores con el propósito de convertir un árbol no-AVL. en AVL por ejemplo el siguiente.
Es AVL y no existe rotacion ya que tiene propiedades AVL , si al nodo anterior le adicionamos un nodo a la izquierda de B los nuevos factores de balance serán.
El arbol ha perdido las propiedades AVL es necesario rotar el árbol para que mantenga las propiedades AVL. Una rotacion exige el ajuste de algunos apuntadores con dos propositos fundamentales.
- Que el arbol siga siendo AVL
- Que su recorrido en inorden se igual antes de la rotación y después de ella.
Para el caso anterior el recorrido en inorden es C B A
EJ:
Si insertamos el nodo G a la izquierda de F el árbol quedara así
Este nuevo árbol en in-orden queda así:
D B E A G F C
Si deseamos mantener el árbol con propiedades AVL es necesario efectuar una rotación de tal manera que el recorrido en in-orden sea exactamente igual antes de rotarlo.
Rotación a la derecha
Se define una rotación a la derecha como el ajuste de 2 apuntadores cuando un árbol después de una inserción quedo como altura no permitida por la izquierda. Tenemos el siguiente árbol.
Al insertar el nodo C el árbol no es AVL:
recorrido en in-orden
CBA
Este árbol exige una rotación a la derecha ya que la altura no es permitida por la izquierda, solamente es permitida hasta la altura 1. Con el proposito de que el árbol vuelva a tener las propiedades AVL y su recorrido en in-orden sea el mismo, la rotacion a efectuar es.
recorrido en in-orden
CBA
Se ajustaron 2 apuntadores y se modificaron los factores de balance de los nodos B A, vamos a diseñar una funcion que efectué este trabajo. El diseño de esta funcion parte de la basee que se recibieron dos apuntadores, uno de ellos cuyo factor de blance no se encuentra en el rango permitido y el 2 indicado en el nodo izquierdo. para el ejemplo los apuntadores recibidos seran.
Veamos otro ejemplo si contamos con este arbol:
Al insertar un nodo F a la izquierda del nodo D , el arbol pierde las propiedades AVL.
y su recorrido en inorden sera
F D B E A C
El árbol anterior se rota y se deja organizado así.
Recupera las propiedades AVL y su recorrido inorden no se modifica, una rutina para efectuar este movimiento aparente de los nodos (realmente los nodos modificados son los valores de los apuntadores), puede diseñarse así
void r_derecha (struct nodo *p,struct nodo *q)
Rotación Izquierda
Se define una rotación a la izquierda como el ajuste de dos apuntadores cuando el árbol después de una inserción queda con una altura no permitida por la derecha. Tenemos el siguiente árbol.
Al insertar el nodo C a la derecha del nodo B el árbol se transforma en
Recorrido in-orden A B C
Este árbol exige una rotación a la izquierda ya que la altura -2 no es permitida por la derecha, con el propósito de que el árbol vuelva a tener las propiedades AVL y su recorrido en in-orden es el mismo la rotación que se debe efectuar es
Se ajustaron 2 apuntadores y se modificaron los factores de balance de los nodos A y B, vamos a diseñar una función que efectué este trabajo. Su construcción parte de la base que se recibieron 2 apuntadores, uno de ellos indicando el nodo cuyo factor de balance no está permitido y el segundo indicando su hijo derecho. Para el ejemplo los apuntadores recibidos serán.
Veamos otro ejemplo si tenemos inicialmente este árbol.
Al insertar el nodo J a la derecha de I, el árbol quedara así.
Recorrido en in-orden DBEAFCHGIJ
El nodo más próximo a J que tiene es facto de balance invalido es C, esto nos permite afirmar si hacemos una rotación a la izquierda partido del estado de los apuntadores p y q, el árbol recuperara las propiedades avl y su recorrido en in-orden será el mismo antes que rotarlo. Lo anterior nos permite deducir que el factor de balance del nodo A.
Y el árbol a la izquierda de A
Debe permanecer inalterado
Al rotar el aro cuya raíz es p, debe quedar así.
Y así el árbol total quedaría
Recorrido in-orden DBEAFCHGIJ
Observe que el factor de balance del nodo >A, no cambio. Una rutina para efectuar este movimiento aparente de los nodos (realmente los nodos modificados son los valores de los apuntadores), puede diseñarse así
void r_izquierda(struct nodo *p,struct nodo *q)
Se define una rotación a la derecha como el ajuste de 2 apuntadores cuando un árbol después de una inserción quedo como altura no permitida por la izquierda. Tenemos el siguiente árbol.
Al insertar el nodo C el árbol no es AVL:
recorrido en in-orden
CBA
Este árbol exige una rotación a la derecha ya que la altura no es permitida por la izquierda, solamente es permitida hasta la altura 1. Con el proposito de que el árbol vuelva a tener las propiedades AVL y su recorrido en in-orden sea el mismo, la rotacion a efectuar es.
recorrido en in-orden
CBA
Se ajustaron 2 apuntadores y se modificaron los factores de balance de los nodos B A, vamos a diseñar una funcion que efectué este trabajo. El diseño de esta funcion parte de la basee que se recibieron dos apuntadores, uno de ellos cuyo factor de blance no se encuentra en el rango permitido y el 2 indicado en el nodo izquierdo. para el ejemplo los apuntadores recibidos seran.
Veamos otro ejemplo si contamos con este arbol:
Al insertar un nodo F a la izquierda del nodo D , el arbol pierde las propiedades AVL.
y su recorrido en inorden sera
F D B E A C
El árbol anterior se rota y se deja organizado así.
Recupera las propiedades AVL y su recorrido inorden no se modifica, una rutina para efectuar este movimiento aparente de los nodos (realmente los nodos modificados son los valores de los apuntadores), puede diseñarse así
void r_derecha (struct nodo *p,struct nodo *q)
{
p->bal=0;
q->bal=0;
p->izq= q->der;
q->der = p;
}
Para el uso de esta rutina, p debe indicar el nodo cuya variable bal no este en el rango permitido y q debe indicar su hijo izquierdo.
Rotación Izquierda
Se define una rotación a la izquierda como el ajuste de dos apuntadores cuando el árbol después de una inserción queda con una altura no permitida por la derecha. Tenemos el siguiente árbol.
Al insertar el nodo C a la derecha del nodo B el árbol se transforma en
Recorrido in-orden A B C
Este árbol exige una rotación a la izquierda ya que la altura -2 no es permitida por la derecha, con el propósito de que el árbol vuelva a tener las propiedades AVL y su recorrido en in-orden es el mismo la rotación que se debe efectuar es
Se ajustaron 2 apuntadores y se modificaron los factores de balance de los nodos A y B, vamos a diseñar una función que efectué este trabajo. Su construcción parte de la base que se recibieron 2 apuntadores, uno de ellos indicando el nodo cuyo factor de balance no está permitido y el segundo indicando su hijo derecho. Para el ejemplo los apuntadores recibidos serán.
Veamos otro ejemplo si tenemos inicialmente este árbol.
Al insertar el nodo J a la derecha de I, el árbol quedara así.
Recorrido en in-orden DBEAFCHGIJ
El nodo más próximo a J que tiene es facto de balance invalido es C, esto nos permite afirmar si hacemos una rotación a la izquierda partido del estado de los apuntadores p y q, el árbol recuperara las propiedades avl y su recorrido en in-orden será el mismo antes que rotarlo. Lo anterior nos permite deducir que el factor de balance del nodo A.
Y el árbol a la izquierda de A
Debe permanecer inalterado
Al rotar el aro cuya raíz es p, debe quedar así.
Y así el árbol total quedaría
Recorrido in-orden DBEAFCHGIJ
Observe que el factor de balance del nodo >A, no cambio. Una rutina para efectuar este movimiento aparente de los nodos (realmente los nodos modificados son los valores de los apuntadores), puede diseñarse así
void r_izquierda(struct nodo *p,struct nodo *q)
{
p->bal=0;
q->bal=0;
p->der= q->izq;
q->izq= p;
}
Doble rotación a la derecha
Existen árboles en los cuales insertar un nuevo nodo, pierden las propiedades AVL, y no recuperan esta al aplicarle una rotación a la derecha o izquierda. Veamos este ejemplo.
Si insertamos un nuevo nodo a la derecha de B, el árbol quedara así.
Se pierden las propiedades AVL, si aplicamos la función r_derecha(), el árbol quedara así.
Lo que demuestra que no siempre que el árbol pierde las propiedades AVL, las puede recuperar ejecutando una simple rotación. Veamos estos dos árboles:
Si rotamos a la derecha el árbol T1, el proceso funciona correctamente. Si rotamos a la derecha T2 el proceso no funciona. Obsérvese que el factor del nodo indicado por q es diferente para cada caso. Podemos deducir que se debe efectuar una rotación a la derecha si se cumplen 2 condiciones:
1. el nodo indicado por p tiene un factor de balance mayor a 1
Para el árbol T2 , se debe aplicar una rotación denominada rotación doble a la derecha y debe efectuar 2 condiciones.
1. el nodo indicado por p tiene un factor de balance mayor a 1
Veamos otro caso
Si al insertar el nodo a la izquierda de D, el nuevo árbol será:
Una simple rotación a la derecha nos resuelve el problema
Pero si la inserción se efectúa a la derecha de E, una simple rotación a la derecha o a la izquierda no resolvería el problema. Debemos aplicar una doble rotación a la derecha a partir de los apuntadores p y q como dijimos anteriormente esta doble rotación se identifica con el valor de la variable:
p->bal
Una doble rotación a la derecha se define como una simple rotación a la izquierda, tomando como base el apuntador q y luego una simple rotación a la derecha tomando como base el apuntador p. Vamos el árbol original
Al insertar F a la derecha de E, El árbol cuya raíz es p quedaría:
El nodo más próximo a F que representa el factor de balance no permitido es el indicado por p. para ajustar el árbol son necesarias, como ya se dijo, una simple rotación a la izquierda del árbol que tiene la raíz q y luego una simple rotación a la derecha del árbol que tiene la raíz p. Obsérvese que se necesita una doble rotación a la derecha ya que la condición.
(q->bal==-1)
Es cierta. A continuación diseñaremos la rutina que recibe p y q y efectúa una doble rotación a la derecha. Esta función tiene como encabezamiento
void dr_derecha(struct nodo *p,struct nodo **q)
El apuntador p recibe por valor, mientras el apuntador q es recibido por referencia. En cuanto se refiere a apuntadores solamente el proceso que efectúa una rotación a la izquierda seguida de una rotación a la derecha es:
r=(*q)->der;
Hasta el momento, hemos efectuado una simple rotación a la izquierda y el árbol se encuentra así:
Ahora debemos efectuar una rotación a la derecha cuya raíz es p
p->izq= r->der;
Quedando el árbol así:
Como podemos observar el recorrido del árbol en inorden se mantiene, pro debemos ajustar los factores de balance de los nodo indicados por p,*q y r para el caso que nos ocupa r->bal el valor es -1 observase si esta condición se cumple,(*q)->bal debe tomar el valor de 1 y p->bal el valor Veamos un ejemplo cuando r _>bal sea uno, tomemos el árbol original:
Si insertamos el nodo F a la izquierda de E, tendremos el siguiente árbol.
Al aplicar una doble rotación a la derecha el árbol quedaría así:
Si r->bal es 1 entonces (*q)->bal debe tomar el valor de 0 y p->bal el valor de -1
Al aplicar doble rotación a la derecha el árbol quedaría así:
Si r->bal es 0 entonces (*q)>bal debe tomar el valor de 0 y p->bal también el valor de 0. Para todos los casos, el valor de r->bal debe ser 0 y r siempre se convierte en la raíz del nuevo árbol AVL. Estos dos últimos detalles no permiten incluir las siguientes instrucciones:
r->bal=0;
La variable (*q) devuelve el valor de la raíz del nuevo árbol AVL después de efectuarse una doble rotación a la derecha.
El análisis anterior nos perite escribir la rutina en su totalidad:
void dr_derecha(struct nodo *p,struct nodo **q)
Para definir una doble rotación a la derecha consideremos algunos ejemplos:
Si insertamos el nodo F a la derecha de E el árbol quedaría así.
Podemos observar que una simple rotación a la izquierda, nos deja el árbol con las propiedades AVL.
Ahora supongamos que el nodo F se inserta a la derecha de E:
Una simple rotación a la izquierda no deja que un árbol AVL. En este caso, es necesario ejecutar un movimiento llamado doble rotación a la izquierda que consiste en ejecutar una simple rotación a la derecha tomando como base el apuntador q y luego una simple rotación a la izquierda tomando como base el apuntador p. Ejecutando las rutinas r_derecha () y r_izquierda (), en este orden, el proceso es invalido ya que aquellas rutinas no devuelven ni cambian direcciones almacenadas en los apuntadores recibidos. Cambian el contenido de las direcciones almacenadas en esos apuntadores. Debemos diseñar un conjunto de instrucciones que efectúen una simple rotación ala derecha seguida de una rotación a la izquierda. Vemos el ejemplo más simple, supongamos que tenemos un árbol con propiedades AVL así:
Si deseamos insertar un nuevo nodo a la derecha o a la izquierda de I el factor de balance del nodo A quedaría en -2 y el factor de balance del nodo C quedaría en 1. Vamos a considerar el caso en el que el nodo se inserto a la derecha de I con lo cual los factores de balance se modifican así;
Para ajustar este árbol es necesario una doble rotación a la izquierda. En principio vamos aceptar esta desciño porque esta comparación:
(q->bal== 1)
Es cierta en el siguiente numeral, explicaremos el porqué de esta determinación. Si la rutina la denominamos dr_izquierda (), vamos a diseñar la función considerando que el apuntador p se recibe por valor y el apuntador q por referencia, así:
void dr_izquierda(struct nodo*p, struct nodo**q)
Un proceso para efectuar una doble rotación a la izquierda tomando como base el árbol precedente, consiste en ejecutar una simple rotación a la derecha tomando como base el apuntador *q, lo cual nos presenta el árbol así:
Ahora debemos ejecutar una simple rotación a la izquierda tomando como base el apuntador p, lo cual nos deja el árbol finalmente así:
Si se recorre el árbol en in-orden el árbol inicial, los resultados serán lo mismos:
D B E A H F I N C J G K
Hasta este momento, con el propósito de ajustar los apuntadores para llegar al árbol anterior son necesaria las siguientes instrucciones:
Observase que en este caso r->bal es uno si esto sucede, los ajustes a evaluar son:
p->bal = 0;
Nos hace falta analizar el caso en el que r->bal se 0. Para que presente esta circunstancia, debemos tomar otro ejemplo. Veamos este árbol.
Si insertamos el nodo C a la izquierda de B, antes de ajustar los apuntadores, el nuevo árbol será:
Ahora, después de ajustar los apuntadores en el nuevo árbol será:
Lo cual demuestra si r->bal es 0, los ajustes que deben hacer a las variables son:
p->bal = 0;
El análisis anterior nos permite presentar la rutina en su totalidad veamos
void dr_izquierda(struct nodo *p,struct nodo **q)
Existen árboles en los cuales insertar un nuevo nodo, pierden las propiedades AVL, y no recuperan esta al aplicarle una rotación a la derecha o izquierda. Veamos este ejemplo.
Si insertamos un nuevo nodo a la derecha de B, el árbol quedara así.
Se pierden las propiedades AVL, si aplicamos la función r_derecha(), el árbol quedara así.
Lo que demuestra que no siempre que el árbol pierde las propiedades AVL, las puede recuperar ejecutando una simple rotación. Veamos estos dos árboles:
Si rotamos a la derecha el árbol T1, el proceso funciona correctamente. Si rotamos a la derecha T2 el proceso no funciona. Obsérvese que el factor del nodo indicado por q es diferente para cada caso. Podemos deducir que se debe efectuar una rotación a la derecha si se cumplen 2 condiciones:
1. el nodo indicado por p tiene un factor de balance mayor a 1
2. el nodo indicado por q tiene un factor de balance igual a 1
Para el árbol T2 , se debe aplicar una rotación denominada rotación doble a la derecha y debe efectuar 2 condiciones.
1. el nodo indicado por p tiene un factor de balance mayor a 1
2. el nodo indicado por q tiene un factor de balance igual a -1
Veamos otro caso
Si al insertar el nodo a la izquierda de D, el nuevo árbol será:
Una simple rotación a la derecha nos resuelve el problema
Pero si la inserción se efectúa a la derecha de E, una simple rotación a la derecha o a la izquierda no resolvería el problema. Debemos aplicar una doble rotación a la derecha a partir de los apuntadores p y q como dijimos anteriormente esta doble rotación se identifica con el valor de la variable:
p->bal
Una doble rotación a la derecha se define como una simple rotación a la izquierda, tomando como base el apuntador q y luego una simple rotación a la derecha tomando como base el apuntador p. Vamos el árbol original
Al insertar F a la derecha de E, El árbol cuya raíz es p quedaría:
El nodo más próximo a F que representa el factor de balance no permitido es el indicado por p. para ajustar el árbol son necesarias, como ya se dijo, una simple rotación a la izquierda del árbol que tiene la raíz q y luego una simple rotación a la derecha del árbol que tiene la raíz p. Obsérvese que se necesita una doble rotación a la derecha ya que la condición.
(q->bal==-1)
Es cierta. A continuación diseñaremos la rutina que recibe p y q y efectúa una doble rotación a la derecha. Esta función tiene como encabezamiento
void dr_derecha(struct nodo *p,struct nodo **q)
El apuntador p recibe por valor, mientras el apuntador q es recibido por referencia. En cuanto se refiere a apuntadores solamente el proceso que efectúa una rotación a la izquierda seguida de una rotación a la derecha es:
r=(*q)->der;
(*q)->der= r->izq;
r->izq=*q;
Hasta el momento, hemos efectuado una simple rotación a la izquierda y el árbol se encuentra así:
Ahora debemos efectuar una rotación a la derecha cuya raíz es p
p->izq= r->der;
r->der=p;
Quedando el árbol así:
Como podemos observar el recorrido del árbol en inorden se mantiene, pro debemos ajustar los factores de balance de los nodo indicados por p,*q y r para el caso que nos ocupa r->bal el valor es -1 observase si esta condición se cumple,(*q)->bal debe tomar el valor de 1 y p->bal el valor Veamos un ejemplo cuando r _>bal sea uno, tomemos el árbol original:
Si insertamos el nodo F a la izquierda de E, tendremos el siguiente árbol.
Al aplicar una doble rotación a la derecha el árbol quedaría así:
Si r->bal es 1 entonces (*q)->bal debe tomar el valor de 0 y p->bal el valor de -1
Veamos un ejemplo cuando r->bal sea 0.Tomemos este árbol.
Al aplicar doble rotación a la derecha el árbol quedaría así:
Si r->bal es 0 entonces (*q)>bal debe tomar el valor de 0 y p->bal también el valor de 0. Para todos los casos, el valor de r->bal debe ser 0 y r siempre se convierte en la raíz del nuevo árbol AVL. Estos dos últimos detalles no permiten incluir las siguientes instrucciones:
r->bal=0;
*q = r;
La variable (*q) devuelve el valor de la raíz del nuevo árbol AVL después de efectuarse una doble rotación a la derecha.
El análisis anterior nos perite escribir la rutina en su totalidad:
void dr_derecha(struct nodo *p,struct nodo **q)
{
struct nodo *r;
r = (*q)->der;
(*q)->der = r ->izq;
r->izq = *q;
r->izq = r ->der;
r->der = p;
switch(r->bal){
case -1: (*q)->bal = 1;
p->bal = 0;
break;
case 0:(*q)->bal = p->bal = 0;
break;
case 1: (*q)->bal = 0;
p->bal = -1;
break;
}
r->bal = 0;;
*q = r;
}
Doble rotación a la derecha
Para definir una doble rotación a la derecha consideremos algunos ejemplos:
Si insertamos el nodo F a la derecha de E el árbol quedaría así.
Podemos observar que una simple rotación a la izquierda, nos deja el árbol con las propiedades AVL.
Ahora supongamos que el nodo F se inserta a la derecha de E:
Una simple rotación a la izquierda no deja que un árbol AVL. En este caso, es necesario ejecutar un movimiento llamado doble rotación a la izquierda que consiste en ejecutar una simple rotación a la derecha tomando como base el apuntador q y luego una simple rotación a la izquierda tomando como base el apuntador p. Ejecutando las rutinas r_derecha () y r_izquierda (), en este orden, el proceso es invalido ya que aquellas rutinas no devuelven ni cambian direcciones almacenadas en los apuntadores recibidos. Cambian el contenido de las direcciones almacenadas en esos apuntadores. Debemos diseñar un conjunto de instrucciones que efectúen una simple rotación ala derecha seguida de una rotación a la izquierda. Vemos el ejemplo más simple, supongamos que tenemos un árbol con propiedades AVL así:
Si deseamos insertar un nuevo nodo a la derecha o a la izquierda de I el factor de balance del nodo A quedaría en -2 y el factor de balance del nodo C quedaría en 1. Vamos a considerar el caso en el que el nodo se inserto a la derecha de I con lo cual los factores de balance se modifican así;
Para ajustar este árbol es necesario una doble rotación a la izquierda. En principio vamos aceptar esta desciño porque esta comparación:
(q->bal== 1)
Es cierta en el siguiente numeral, explicaremos el porqué de esta determinación. Si la rutina la denominamos dr_izquierda (), vamos a diseñar la función considerando que el apuntador p se recibe por valor y el apuntador q por referencia, así:
void dr_izquierda(struct nodo*p, struct nodo**q)
Un proceso para efectuar una doble rotación a la izquierda tomando como base el árbol precedente, consiste en ejecutar una simple rotación a la derecha tomando como base el apuntador *q, lo cual nos presenta el árbol así:
Ahora debemos ejecutar una simple rotación a la izquierda tomando como base el apuntador p, lo cual nos deja el árbol finalmente así:
Si se recorre el árbol en in-orden el árbol inicial, los resultados serán lo mismos:
D B E A H F I N C J G K
Hasta este momento, con el propósito de ajustar los apuntadores para llegar al árbol anterior son necesaria las siguientes instrucciones:
struct nodo *r
r=(*q)->izq;
(*q)->izq= r->der;
r->der=*q;
p->der = r ->izq;
r->izq = p;
Se certifica la validez de las instrucciones anteriores, como se observa hasta ese momento estan ajustados los apuntadores, debemos diseñar las instrucciones con el propósito de ajustar los factores de balance, de los nodos implicados en el proceso. Existen 3 casos. El primero es cuando p->bal toma el valor de 1, r->bal el valor 0 y (*q)->bal el valor 0. El segundo caso lo podemos apreciar si consideramos que hubiera sucedido si el nodo N lo hubiéramos insertado a la izquierda del nodo H. Después de ejecutar las instrucciones el árbol podría quedar así:
Observase que en este caso r->bal es uno si esto sucede, los ajustes a evaluar son:
p->bal = 0;
(*q)->bal = -1;
r->bal = 0;
Nos hace falta analizar el caso en el que r->bal se 0. Para que presente esta circunstancia, debemos tomar otro ejemplo. Veamos este árbol.
Si insertamos el nodo C a la izquierda de B, antes de ajustar los apuntadores, el nuevo árbol será:
Ahora, después de ajustar los apuntadores en el nuevo árbol será:
Lo cual demuestra si r->bal es 0, los ajustes que deben hacer a las variables son:
p->bal = 0;
(*q)->bal = 0;
r->bal = 0;
El análisis anterior nos permite presentar la rutina en su totalidad veamos
void dr_izquierda(struct nodo *p,struct nodo **q)
{
struct nodo *r;
r = (*q)->izq;
(*q)->izq = r ->der;
r->der = *q;
r->der = r ->izq;
r->izq = p;
switch(r->bal){
case -1: (*q)->bal = 0;
p->bal = 1;
break;
case 1: (*q)->bal = -1;
p->bal = 0;
break;
case 0: (*q)->bal = p->bal = 0;
break;
}
r->bal = 0;;
*q = r;
}
Eliminar un Dato
Al eliminar
un nodo en un árbol AVL puede afectar el equilibrio de sus nodos. Entonces hay
que hacer rotaciones simples o dobles.
Eliminas un
nodo como lo hacemos en un árbol binario ordenado. Al localizar el nodo que
queremos eliminar seguimos este procedimiento:
- Si el nodo
es un nodo hoja, simplemente lo eliminamos.
- Si el nodo
solo tiene un hijo, lo sustituimos con su hijo.
- Si el nodo
eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el
hijo izquierdo en el subárbol izquierdo del hijo derecho.
Ahora que hemos eliminado el nodo, tenemos que volver a equilibrar el árbol:
- Si el
equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo
concluye.
- Si el padre
del nodo eliminado cambio de +-1 a 0, la altura del árbol ha cambiado y se
afecte el equilibrio de su abuelo.
- Si el
equilibrio del padre del nodo eliminado cambia de +- 1 a +- 2 hay que hacer una
rotación.
- Después de
concluirla, el equilibrio del padre podría cambiar, lo que, a su vez, podría
forzarnos a hacer otros cambios (y probables rotaciones) en toda la ruta hacia
arriba a medida que ascendemos hacia la raíz. Si encontramos en la ruta un nodo
que cambie de 0 a +- 1 entonces terminamos.
No hay comentarios:
Publicar un comentario