Arboles Binarios Ordenados Equilibrados

Vamos a resolver el siguiente ejercicio:

Inserta, en el orden especificado, los siguientes enteros en un ABOE
aplicando las rotaciones pertinentes cuando corresponda: 11, 8, 18, 15, 13, 20, 7, 6, 10, 12 y 21.

1) Comenzamos insertando el "11"

 

2) Insertamos el "8"

 3) Insertamos el "18"

 

4)Insertamos el "15"

 

5) Insertamos el "13" y vemos que el arbol esta desequilibrado a partir del nodo "18" con una desigualdad mayor de uno (Izquierda 2-Derecha 0), y procedemos a reorganizarlo.

 

6) Hacemos una rotacion simple Izquierda-Izquierda y queda equilibrado de nuevo

 

7) Insertamos el "20"

 

8) Insertamos el "7"

 

9) Insertamos el "6" y el arbol vuelve a desequilibrarse desde el nodo "8".

 

10) Volvemos a usar una rotacion simple Izquierda-Izquierda para reestructurarlo.

 

11) Insertamos el "10" y se desequilibra desde el nodo "11"

 

12) Aplicamos una rotacion doble Izquierda-Derecha para recuperar el equilibrio.

 

13) Al introducir el "12" como hijo del nodo "13" volvemos a perder el equilibrio a partir del nodo raiz con un (4-2) y reestructuramos con una rotacion doble Izquierda-Derecha para reequilibrar el arbol

 

14) Insertamos finalmente el nodo "21" y el arbol sigue ordenado.

 

Antonio Sanchez Rosa

Estructura de Datos y de la Informacion (EDI)