Estructuras de Datos I - Árbol AVL

Vista previa del material en texto

Árboles Parte 2
Árbol AVL
1
Actividad: Casos extremos
Realiza un árbol binario de búsqueda con la siguiente información de entrada:
Árbol 1:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
Árbol 2:
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
Orden
El orden para estos casos es de:
O(n)
Como si fuera una búsqueda lineal
8
4
12
2
6
10
14
5
13
3
7
15
9
11
1
Orden
El orden para este caso:
O(n * log2 n)
Como si fuera una búsqueda binaria
Árbol completo:
Todos los nodos tienen todos los hijos que pueden tener.
	Altura (n)	No. De nodos
	0	1
	1	2
	2	7
	3	15
2n – 1
N = 10 : 1,023
N = 20 : 1’048,575
N = 30 : 10, 073’741,823
Nacimiento
Gracias a este concepto, Gueorgui Adelsón-Velski y Yevgueni Landis crean en 1962 al conocido:
Árbol AVL
Adelsón-Velski and Landi’s Tree
Funcionamiento
Este árbol cuida cada vez que se inserta un nuevo elemento, que esta balanceado, de allí que también se le conozca como Árboles Binarios de Búsqueda Auto Balanceados
Árbol AVL
En un árbol balanceado la altura de dos subárboles hermanos en cualquier nodo del árbol son iguales o difieren por no mas de un nivel de altura.
Si en algún momento la diferencia de las alturas entre los hermanos difieren por mas de uno, se realiza un rebalanceo para mantener balanceado el resto del árbol.
La diferencia entre subárboles hermanos da pie al termino factor de equilibrio.
El rebalanceo se hace a partir de una Rotación.
Rotaciones
Rotación Simple a la Izquierda (RSI) – RII: Rotación Izquierda Izquierda
Rotación Simple a la Derecha (RSD) – RDD: Rotación Derecha Derecha
Rotación Doble a la Izquierda (RDI) – RID: Rotación Izquierda Derecha
Rotación Doble a la Derecha (RDD) – RDI: Rotación Derecha Izquierda
Factor de equilibrio
FE = ASD – ASI
FE: Factor de Equilibrio.
ASD: Altura del Subárbol Derecho
ASI: Altura del Subárbol Izquierdo
0
1
–1
Factor de equilibrio
FE = ASD – ASI
FE: Factor de Equilibrio.
ASD: Altura del Subárbol Derecho
ASI: Altura del Subárbol Izquierdo
0
1
–1
2
1
–2
–1
Factor de equilibrio
FE = ASD – ASI
FE: Factor de Equilibrio.
ASD: Altura del Subárbol Derecho
ASI: Altura del Subárbol Izquierdo
0
1
–1
2
1
–2
–1
2
1
–2
–1
Factor de equilibrio
FE = ASD – ASI
FE: Factor de Equilibrio.
ASD: Altura del Subárbol Derecho
ASI: Altura del Subárbol Izquierdo
0
1
–1
2
1
–2
–1
2
1
–2
–1
	Factor	
	2	Desequilibrado a la derecha
	1	Equilibrado
	0	
	–1	
	–2	Desequilibrado a la izquierda
¿Qué rotación aplcar?
Si esta desbalanceado a la izquierda (–2)
Aplicar rotación a la derecha
Si esta desbalanceado a la derecha (2)
Aplicar rotación a la izquierda
¿Qué rotación aplcar?
Si esta desbalanceado a la izquierda (–2)
Aplicar rotación a la derecha
Si esta desbalanceado a la derecha (2)
Aplicar rotación a la izquierda
En un árbol que esta desbalanceado a la izquierda revisar el factor de equilibrio del subárbol izquierdo
En un árbol que esta desbalanceado a la derecha revisar el factor de equilibrio del subárbol derecho
¿Qué rotación aplcar?
Si esta desbalanceado a la izquierda (–2)
Aplicar rotación a la derecha
Si esta desbalanceado a la derecha (2)
Aplicar rotación a la izquierda
En un árbol que esta desbalanceado a la izquierda revisar el factor de equilibrio del subárbol izquierdo
En un árbol que esta desbalanceado a la derecha revisar el factor de equilibrio del subárbol derecho
2
1
–2
–1
Si el signo de los factores coincide, será una rotación simple
¿Qué rotación aplcar?
Si esta desbalanceado a la izquierda (–2)
Aplicar rotación a la derecha
Si esta desbalanceado a la derecha (2)
Aplicar rotación a la izquierda
En un árbol que esta desbalanceado a la izquierda revisar el factor de equilibrio del subárbol izquierdo
En un árbol que esta desbalanceado a la derecha revisar el factor de equilibrio del subárbol derecho
2
1
–2
–1
Si el signo de los factores coincide, será una rotación simple
2
1
–2
–1
Si el signo de los factores no coincide, será una rotación doble
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Pivote
1.- El hijo derecho del pivote pasa a ser la raíz del árbol.
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Pivote
1.- El hijo derecho del pivote pasa a ser la raíz del árbol.
c
b
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Pivote
1.- El hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
c
b
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Pivote
1.- El hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
c
b
a
Pivote
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Pivote
1.- El hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo izquierdo del hijo derecho del pivote pasa a ser el hijo derecho del pivote en su nueva posición.
c
b
a
Pivote
Rotaciones Simples
A la izquierda
(RSI)
a
c
b
d
Pivote
1.- El hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo izquierdo del hijo derecho del pivote pasa a ser el hijo derecho del pivote en su nueva posición.
c
b
a
Pivote
d
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
1.- El hijo izquierdo del pivote pasa a ser la raíz del árbol.
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
1.- El hijo izquierdo del pivote pasa a ser la raíz del árbol.
a
b
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
1.- El hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo derecho de la nueva raíz.
a
b
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
1.- El hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo derecho de la nueva raíz.
a
b
d
Pivote
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
1.- El hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo derecho de la nueva raíz.
3.- El hijo derecho del hijo izquierdo del pivote pasa a ser el hijo izquierdo del pivote en su nueva posición.
a
b
d
Pivote
Rotaciones Simples
A la derecha
(RSD)
d
a
b
c
Pivote
1.- El hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo derecho de la nueva raíz.
3.- El hijo derecho del hijo izquierdo del pivote pasa a ser el hijo izquierdo del pivote en su nueva posición.
a
b
d
Pivote
c
Rotaciones Simples
A la izquierda
(RSI)
Aux1 = (*r)der;
Aux2 = aux1 izq;
(*r)der = aux2;
Aux1izq = (*r);
(*r) = aux1;
1.-
2.-
3.-
A
C
D
B
r
aux2
aux1
Rotaciones Simples a la Izquierda
A
C
D
B
r
Rotaciones Simples a la Izquierda
A
C
D
B
r
aux1
Rotaciones Simples a la Izquierda
A
C
D
B
r
aux2
aux1
Rotaciones Simples a la Izquierda
A
C
D
B
r
aux2
aux1
Rotaciones Simples a la Izquierda
A
C
D
B
r
aux2
aux1
Rotaciones Simples a la Izquierda
A
C
D
B
r
aux2
aux1
Rotaciones Simples a la Izquierda
A
C
D
B
r
aux2
aux1
Actividad 1 de 4
Inserte en un árbol AVL los siguientes elementos:
1, 2, 3, 4, 5, 6, 7, 8, 9
(aplique solamente la rotación simple a la izquierda)
Actividad 2 de 4
Inserte en un árbol AVL los siguientes elementos:
9, 8, 7, 6, 5, 4, 3, 2, 1
(aplique solamente la rotación simple a la derecha)
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
c
Rotaciones Dobles
A laizquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
c
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
c
a
Pivote
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo derecho del pivote pasa a ser el hijo derecho de la nueva raíz.
c
a
Pivote
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo derecho del pivote pasa a ser el hijo derecho de la nueva raíz.
c
a
Pivote
e
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo derecho del pivote pasa a ser el hijo derecho de la nueva raíz.
4.- El hijo izquierdo del hijo izquierdo del hijo derecho del pivote pasa a ser el hijo derecho del pivote en su nueva posición,
c
a
Pivote
e
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo derecho del pivote pasa a ser el hijo derecho de la nueva raíz.
4.- El hijo izquierdo del hijo izquierdo del hijo derecho del pivote pasa a ser el hijo derecho del pivote en su nueva posición,
c
a
Pivote
e
b
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo derecho del pivote pasa a ser el hijo derecho de la nueva raíz.
4.- El hijo izquierdo del hijo izquierdo del hijo derecho del pivote pasa a ser el hijo derecho del pivote en su nueva posición.
5.- El hijo derecho del hijo izquierdo del hijo derecho del pivote pasa a ser el hijo izquierdo del hijo derecho de la nueva raíz.
c
a
Pivote
e
b
Rotaciones Dobles
A la izquierda
(RDI)
a
c
e
d
b
Pivote
1.- El hijo izquierdo del hijo derecho del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser el hijo izquierdo de la nueva raíz.
3.- El hijo derecho del pivote pasa a ser el hijo derecho de la nueva raíz.
4.- El hijo izquierdo del hijo izquierdo del hijo derecho del pivote pasa a ser el hijo derecho del pivote en su nueva posición.
5.- El hijo derecho del hijo izquierdo del hijo derecho del pivote pasa a ser el hijo izquierdo del hijo derecho de la nueva raíz.
c
a
Pivote
e
b
d
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
c
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
c
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
c
e
Pivote
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
3.- El hijo izquierdo del pivote pasa a ser hijo izquierdo de la nueva raíz.
c
e
Pivote
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
3.- El hijo izquierdo del pivote pasa a ser hijo izquierdo de la nueva raíz.
c
e
Pivote
a
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
3.- El hijo izquierdo del pivote pasa a ser hijo izquierdo de la nueva raíz.
4.- El hijo izquierdo del hijo derecho del hijo izquierdo del pivote pasa a ser hijo derecho del hijo izquierdo de la nueva raíz.
c
e
Pivote
a
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
3.- El hijo izquierdo del pivote pasa a ser hijo izquierdo de la nueva raíz.
4.- El hijo izquierdo del hijo derecho del hijo izquierdo del pivote pasa a ser hijo derecho del hijo izquierdo de la nueva raíz.
c
e
Pivote
a
b
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
3.- El hijo izquierdo del pivote pasa a ser hijo izquierdo de la nueva raíz.
4.- El hijo izquierdo del hijo derecho del hijo izquierdo del pivote pasa a ser hijo derecho del hijo izquierdo de la nueva raíz. 
5.- El hijo derecho del hijo derecho del hijo izquierdo del pivote pasa a ser el hijo izquierdo del pivote en su nueva posición.
c
e
Pivote
a
b
Rotaciones Dobles
A la Derecha
(RDD)
e
c
a
d
b
Pivote
1.- El hijo derecho del hijo izquierdo del pivote pasa a ser la raíz del árbol.
2.- El pivote pasa a ser hijo derecho de la nueva raíz.
3.- El hijo izquierdo del pivote pasa a ser hijo izquierdo de la nueva raíz.
4.- El hijo izquierdo del hijo derecho del hijo izquierdo del pivote pasa a ser hijo derecho del hijo izquierdo de la nueva raíz. 
5.- El hijo derecho del hijo derecho del hijo izquierdo del pivote pasa a ser el hijo izquierdo del pivote en su nueva posición.
c
e
Pivote
a
b
d
Rotaciones Dobles
A la izquierda
(RDI)
Aux1 = (*r)der;
Aux2 = (*r)derizq
Aux3 = aux2izq;
Aux4 = aux2der; 
(*r)der = aux3;
Aux1izq = aux4;
Aux2izq = (*r);
Aux2der = aux1;
(*r) = aux2;
1.-
2.-
3.-
4.-
5.-
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
B
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux1
B
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
aux2
aux1
B
aux3
aux4
Rotaciones Dobles a la Izquierda
A
E
D
C
r
B
Rotaciones Dobles a la Izquierda
A
E
D
C
r
B
Rotaciones Dobles
A la Derecha
(RDD)
Aux1 = (*r)izq;
Aux2 = aux1der;
Aux3 = aux2der;
Aux4 = aux2izq; 
(*r)izq = aux3;
Aux1der= aux4;
Aux2der = (*r);
Aux2izq = aux1;
(*r) = aux2;
1.-
2.-
3.-
4.-
5.-
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux1
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux1
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
rB
aux3
aux1
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
aux3
aux1
aux4
aux2
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
Rotaciones Dobles a la Derecha
E
A
D
C
r
B
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
a
c
e
d
b
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
a
c
e
d
b
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
a
c
e
d
b
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
a
c
e
d
b
a
c
e
d
b
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
a
c
e
d
b
Pivote
1.- RSD en el subárbol derecho
2.- RSI en la raíz
a
c
e
d
b
a
c
e
d
b
Rotaciones Dobles
A la izquierda como una secuencia de dos rotaciones simples
(RDI)
1.- RSD en el subárbol derecho
2.- RSI en la raíz
a
c
e
d
b
Void rotdobizq(árbol* root){
Rotsimder(&(*root)der);
Rotsimizq(root);
}
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
e
a
c
b
d
Pivote
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
e
a
c
b
d
Pivote
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
e
a
c
b
d
Pivote
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
e
a
c
b
d
Pivote
e
a
c
b
d
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
e
c
a
d
b
Pivote
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
e
a
c
b
d
Pivote
e
a
c
b
d
Rotaciones Dobles
A la derecha como una secuencia de dos rotaciones simples
(RDD)
1.- RSI en el subárbol izquierdo
2.- RSD en la raíz
e
a
c
b
d
Void rotdobder(árbol* root){
Rotsimizq(&(*root)izq);
Rotsimder(root);
}
Actividad 3 de 4
Inserte en un árbol AVL los siguientes elementos:
1, 3, 2, 8, 5, 4, 10, 9, 7, 6
(aplique solamente la rotación doble a la izquierda)
Actividad 4 de 4
Inserte en un árbol AVL los siguientes elementos:
10, 8, 9, 3, 6, 7, 1, 2, 4, 5
(aplique solamente la rotación doble a la derecha)
Bienvenidos a:
Árboles Parte 2
Fuentes
Experiencia Laboral
Joyanes L. (2006). Programación en C++. Algoritmos, Estructuras de Datos y Objetos. España. Mcgraw-hill / Interamericana De España
Silvia Guardati Buemo (2007). Estructura de datos orientada a objetos: Algoritmos con C++ Pearson
113