domingo, 22 de abril de 2012

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)
 

lunes, 26 de marzo de 2012

Organizaciones de ficheros

Las organizaciones de ficheros mas comunes serían las siguientes:
-Apilada.
-Secuencial.
-Encadenada.
-Secuencial Indexada.
-Indexada.
-Hashing.


Serán desarrolladas en ese orden, ya que cada una va dando solución a uno o varios de los inconvenientes de la anterior.




*ORGANIZACIÓN APILADA
Sería la primera en ver, es la más fácil de programar, y su principal desventaja es el alto coste de mantenimiento con el desarrollo del tiempo respecto a la creación del mismo. Otro sería la posible redundancia de información. Los datos entre sí no tienen orden alguno.


*SECUENCIAL
Es esta organización los datos si están ordenados por la clave. Lo que mejora bastante el acceso a los datos en eficiencia respecto a la organización apilada. La búsqueda se convierte también en mas eficiente. Las lecturas suelen ser ordenadas por lo que es mas rápido de esta forma. También seguimos teniendo inconvenientes como los problemas a la hora de insertar y la ordenación de los registros se deteriora con el tiempo.


*ENCADENADA
Esta organización tendría un puntero por cada clave de ordenación, lo que a la hora de ordenar mejoraría mucho mas la eficiencia aun teniendo varias claves. Respecto a la ordenación secuencial, esta ordenación nos permite tener varias claves y la eficiencia de búsqueda sería igual para todas. Esto también conlleva una desventaja que sería que los punteros de ordenación dependen del dispositivo físico y en la perdida o fallo de alguno conllevarían al desorden total.


*SECUENCIAL INDEXADA
Aquí tendríamos un indice que nos haría mejorar la búsqueda de un registro concreto, caso que no se ha mejorado en ninguna de las organizaciones anteriores. Pero tiene algunas desventajas como que ocupan mas espacio al tener un indice por el que acceder y también necesitan de reordenación con respecto al tiempo.


*INDEXADA

Las mejoras respecto a la secuencial indexada serian la eliminación de la zona de derrama causante de grandes retrasos en todas las operaciones,  las restricciones impuestas a la zona maestra y el índice debe ser actualizable dinámicamente.



*HASHING

Con la organización hashing lo que elimina sería el acceso repetitivo en varias operaciones de la organización indexada, para acceder a un registro concreto en una sola operación.


Antonio Sánchez Rosa
Estructuras de Datos