Cont. Arbol Binario de Búsqueda (2)

Sobre los recorridos

• Las versiones recursivas de los

recorridos son costosas debido a la

gran cantidad de llamadas recursivas

que pueden llegar a copar la pila (stack)

• Se prefieren entonces versiones no

recursivas para dichos recorridos

• Las versiones no recursivas de estos recorridos requieren el uso de un arreglo (o lista) auxiliar de apuntadores a los nodos

• Su codificación es menos clara que sus versiones recursivas

• Se verá la versión no recursiva de inorden

Implementación

Se agrega a la clase ArbolBin la siguiente declaración:

void inorden_nr(Nodo *r);

Inorden No Recursivo

void ArbolBin::inorden_nr(Nodo *r){

Nodo *vec[100]; // Vector de punteros a Nodosint j=0;

//Se insertan en el vector de punteros de nodos//los que están en la "rama" izquierda de la raízwhile(r != NULL){

j++;vec[j] = r;r= r ->hijoIzq;

}

/* Se saca el último puntero insertado en el vector, imprimimos y nos pasamos a su hijo derecho para realizar el mismo proceso hecho a la raíz */

while(j>0){r = vec[j];j--;cout<< (r->dato).codigo << endl;r = r->hijoDer;while(r != NULL){

j++;vec[j] = r;r= r ->hijoIzq;

}}

}

• Son árboles binarios balanceados por altura

• Sus inventores fueron G. Adelson-Velskii y E. Landis

• Concebidos especialmente para ser aplicados en los árboles binarios de búsqueda

• Evitan que los árboles se “degeneren” (sesgados a derecha o izquierda)

Árboles AVL

• Su implementación es más compleja que un árbol binario simple

• Las operaciones de búsqueda, inserción y borrado mantienen un buen tiempo de desempeño O(Log n)

• Para comprender el algoritmo de inserción en AVL se requiere entender primero que son las rotacionesrotaciones

• La operación de borrado es bastante compleja

• Se han propuesto variantes y mejoras a los árboles AVL: Árboles rojinegros, Árboles Splay, AA-Árboles

• Se verá a continuación las rotaciones y luego el algoritmo de inserción

Factor de Balance:• Concepto clave en los árboles AVL• El factor de balance para cualquier nodo x

del árbol se define como la diferencia entre la altura del subárbol izquierdo de x y la altura del subárbol derecho de x.

Es decir:FB(x) = Altura(subárbol Izq. de x) –

Altura(subárbol Der. de x)Un árbol binario H es AVL si: │FB (x)│ < 2 , x H

Operaciones de rebalanceo:

• Consiste en reacomodar los registros de un árbol binario de tal forma que los factores de balance de todos los nodos sean -1, 0, ó 1 y que el recorrido inordeninorden sea el mismo que antes del reacomodo.

• Estas operaciones se conocen como rotaciones

Operaciones de Rebalanceo:

1. Rotación a la derecha

2. Rotación a la izquierda

3. Doble rotación a la derecha

4. Doble rotación a la izquierda

Para explicar lo referente a las rotaciones se

asume la siguiente convención:

• Sea P el puntero al nodo con factor de balance no permitido (+2 ó -2)

• Sea Q el puntero al hijo izquierdo o al hijo derecho de P, dependiendo de si FB(P)=+2 ó FB(P)= -2

Rotación a la Derecha

Se efectúa cuando: FB (P) = + 2

FB (Q) = + 1

Consiste en girar, en sentido de las manecillas del reloj, el registro P alrededor del registro Q.

Consecuencias:• P pasará a ser el nuevo hijo derecho de Q• El anterior hijo derecho de Q será el

nuevo hijo izquierdo de P• Q será la nueva raíz del árbol balanceado• Los nuevos factores de balance de P y Q

serán cero (0)• La altura del árbol balanceado disminuye

en uno (1)

+2 0 P c Q b +1 0 0 Q b a c P 0 a

Antes Después

Nótese que los recorridos INORDEN sobre ambos árboles es el mismo

Pseudo Código de la operación:

Rotacion_a_la_Derecha(P, Q) P -> hijoIzq = Q -> hijoDer Q -> hijoDer = P P -> FB = 0 Q -> FB = 0FIN

Luego se verá la codificación en C++ en el algoritmo completo de inserción

Rotación a la Izquierda

Se efectúa cuando: FB (P) = - 2

FB (Q) = - 1

Consiste en girar, en sentido contrario de las manecillas del reloj, P alrededor de Q.

Consecuencias:• P será el nuevo hijo izquierdo de Q• El nuevo hijo derecho de P será el anterior

hijo izquierdo Q• Q será la nueva raíz del árbol balanceado• Los factores de balance P y Q quedarán

en cero• La altura del árbol balanceado disminuye

en uno (1)

Antes Después

Nótese que los recorridos INORDEN sobre ambos árboles es el mismo

-2 0 P a Q b -1 0 0 Q b P a c 0 c

Pseudo Código de la operación:

Rotacion_a_la_Izquierda(P, Q) P -> hijoDer = Q -> hijoIzq Q -> hijoIzq = P P -> FB = 0 Q -> FB = 0FIN

Luego se verá la codificación en C++ en el algoritmo completo de inserción

• Las últimas 2 rotaciones se denominan dobles

• Para definirlas se adopta la siguiente convención:

Sea R el registro que representa el hijo izquierdo o el hijo derecho de Q dependiendo de si el factor de balance de Q es +1 ó -1.

Doble Rotación a la Derecha

Se efectúa cuando: FB (P) = + 2

FB (Q) = - 1

Consiste en: Una rotación a la izquierda de Q alrededor de R seguida de una rotación a la derecha de P alrededor de R

Consecuencias:

• R será la nueva raíz del árbol balanceado • P será el nuevo hijo derecho de R• Q será el nuevo hijo izquierdo de R • El anterior hijo derecho de R será el nuevo hijo izquierdo

de P• El anterior hijo izquierdo de R será el nuevo hijo derecho

de Q • La altura del árbol balanceado disminuye en uno (1)• El factor de balance de R será cero• Los factores de balance de P y Q tomarán nuevos

valores, los cuales dependerán del factor de balance inicial del registro R el cual puede ser -1, 0 ó 1

Antes Después

Nótese que los recorridos INORDEN sobre ambos árboles es el mismo

+2 0 P c R b -1 0 0 Q a Q a c P 0 R b

En el caso anterior el FB del nodo R es 0.

Para este caso los FB finales de los nodos

P y Q serán cero.

Si FB inicial de R es cero entonces:

FB(P) = 0 y FB(Q) = 0

Veamos los otros casos:

+2 0 P e R d -1 0 0 -1 Q b f Q b e P 0 +1 0 0 0 a d R a c f 0 c

Antes Después

• En conclusión si FB inicial de R es 1

entonces FB(P) = -1 y FB(Q) = 0

• De manera similar se puede comprobar que si FB inicial de R es -1entonces

FB(P) = 0 y FB(Q) = 1

Pseudo Código de la operación:Doble_Rotacion_a_la_Derecha(P, Q)

R = Q -> hijoDer //Se obtiene R a partir de Qfactor_R = R->FB //Se guarda el factor de balance de R

Rotacion_a_la_Izquierda(Q, R)Rotacion_a_la_Derecha(P, R)Caso de factor_R

:0: P -> FB = 0 Q -> FB = 0

:1: P -> FB = -1Q -> FB = 0

:-1: P -> FB = 0 Q -> FB = 1

FIN(Caso)R -> FB = 0Q = R //Se deja la raíz en Q

FIN Luego se verá la codificación en C++ en el algoritmo completo de inserción

Doble Rotación a la Izquierda

Se efectúa cuando: FB (P) = - 2

FB (Q) = +1

Consiste en: Una rotación a la derecha de Q alrededor de R seguida de una rotación a la izquierda de P alrededor de R.

Consecuencias:• R será la nueva raíz del árbol balanceado• P será el nuevo hijo izquierdo de R• Q será el nuevo hijo derecho de R• El anterior hijo derecho de R será el nuevo hijo izquierdo

de Q• El anterior hijo izquierdo de R será el nuevo hijo derecho

de P • La altura del árbol balanceado disminuye en uno (1)• El FB de R será cero • Los factores de balance de P y Q tomarán nuevos

valores, los cuales dependerán del factor de balance inicial del registro R el cual puede ser -1, 0 ó 1

Antes Después

Nótese que los recorridos INORDEN sobre ambos árboles es el mismo

-2 0 P c R b +1 0 0 Q a P c a Q 0 R b

En el caso anterior el FB del nodo R es 0.

Para este caso los FB finales de los nodos

P y Q serán cero.

Si FB inicial de R es cero entonces:

FB(P) = 0 y FB(Q) = 0

Veamos los otros casos:

Antes Después

-2 0 P e R a 0 +1 0 -1 b f Q P e f Q +1 0 0 0 0 R a d b c d 0 C

• En conclusión si FB inicial de R es 1

entonces FB(P) = 0 y FB(Q) = -1

• De manera similar se puede comprobar que si FB inicial de R es -1entonces

FB(P) = 1 y FB(Q) = 0

Pseudo Código de la operación:Doble_Rotacion_a_la_Izquierda(P, Q)

R = Q -> hijoIzq //Se obtiene R a partir de Qfactor_R = R->FB //Se guarda el factor de balance de R

Rotacion_a_la_Derecha(Q, R) Rotacion_a_la_Izquierda(P, R)Caso de factor_R

:0: P -> FB = 0 Q -> FB = 0:1: P -> FB = 0 Q -> FB = -1

:-1: P -> FB = 1 Q -> FB = 0

FIN(Caso)R -> FB = 0Q = R // Se deja la raíz en Q

FIN Luego se verá la codificación en C++ en el algoritmo completo de inserción