Download árbol árbol binaria

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 Nodos
int j=0;
//Se insertan en el vector de punteros de nodos
//los que están en la "rama" izquierda de la raíz
while(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;
}
}
}
Árboles AVL
• 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)
• 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 rotaciones
• 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 inorden
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
P c
0
Q b
+1
Q b
0
a
0
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 = 0
FIN
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)
P a
-2
Q b
0
0
0
-1
P a
Q b
c
0
c
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_Izquierda(P, Q)
P -> hijoDer = Q -> hijoIzq
Q -> hijoIzq = P
P -> FB = 0
Q -> FB = 0
FIN
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
+2
P c
Q a
R b
-1
R b
Antes
0
Q a
0
0
c P
0
Después
Nótese que los recorridos INORDEN sobre ambos árboles es el mismo
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
P
a
R d
e
Q b
0
0
-1
0
f
+1
d R
Q
0
-1
e P
b
0
a
0
c
0
c
Antes
Después
0
f
• 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 Q
factor_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 = -1
Q -> FB = 0
:-1:
P -> FB = 0
Q -> FB = 1
FIN(Caso)
R -> FB = 0
Q = R //Se deja la raíz en Q
Luego se verá la codificación
FIN
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
-2
0
P c
R b
Q a
R b
+1
P c
0
0
a Q
0
Antes
Después
Nótese que los recorridos INORDEN sobre ambos árboles es el mismo
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
P
0
R
e
0
b
R a
+1
f Q
P
0
0
+1
d
b
a
0
-1
f Q
e
0
c
0
C
Antes
Después
0
d
• 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 Q
factor_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 = 0
Q = R
// Se deja la raíz en Q
Luego se verá la codificación
FIN
en C++ en el algoritmo completo
de inserción