Arbol AVL

Es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó. [(AVL) Adelson-Velskii y Landis]

Características:

• Están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa
• La complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n)
• La inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Factor de equilibrio:

El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo; Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

Si el factor de equilibrio de un nodo es: 0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. 1 -> el nodo está desequilibrado y su subárbol derecho es un nivel más alto. -1 -> el nodo está desequilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.

.

Arboles

El árbol es una estructura muy usada en todos los ámbitos de la informática ya que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación. Las estructuras tipo árbol se usan para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc

CARACTERSTCAS:

Un árbol se define como un conjunto finito de uno o más nodos relacionados de la siguiente forma:

• Hay un nodo especial llamado raíz del árbol, que proporciona un punto de entrada a la estructura.
• Los nodos restantes se subdividen en conjuntos disjuntos, cada uno de los cuales es a su vez un árbol. (Recursividad) Estos árboles se llaman subárboles del raíz.

La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendiente, descendiente.

Junto a estos conceptos se definen otros tales como raíz, nodo, hoja, camino, nivel, profundidad, etc.

PARTES DE UN ARBOL:

Longitud de caminos interno y externo

Se define como la longitud de camino del nodo X como el numero de arcos q se deben recorrer para llegar desde la raíz hasta el nodo X.
La raíz tiene longitud de camino 1, sus descendientes directos longitud de camino 2 y así sucesivamente.

.

Ordenamiento Shell (codigo)

En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.

Pseudocódigo

INT, I y AUX son variables de tipo entero. BAND es una variable de tipo booleano)
1.- Hacer INT ? N +1.
2.- Mientras (INT > 1) Repetir
Hacer INT ? parte entera (INT /2) y BAND? VERDADERO.
2.1.- Mientras (BAND == VERDADERO) Repetir.
Hacer BAND ? FALSO e I ? 1.
2.1.1.- Mientras ((I + INT) <= N) Repetir.
2.1.1.1.- Si A [I] > A[I + INT] Entonces.
Hacer AUX ? A[I], A[I] ? A[I + INT], A[I + INT] ? AUX y
BAND ? VERDADERO.
2.1.1.2.- {Fin del condicional del paso 2.1.1.1}
Hacer I ? I + 1.
2.1.2.- {Fin del ciclo del paso 2.1.1}
2.2.- { Fin del ciclo del paso 2.1}
3.- { Fin del ciclo del paso 2}

Secuenciales coordinados

La operaciones secuenciales coordinadas implica el procesamiento coordinado de dos o más listas
secuenciales para producir una única lista de salida.
Dichas lista se pueden producir ya sea por: Correspondencia (intersección) Intercalación (unión)

Correspondencia
Las listas deben de estar en orden ascendente.
1. Se inicia con la lectura del nombre inicial del la lista 1 y lo compara con el nombre inicial de la lista
2. Si encuentra una correspondencia se inserta el elemento en un nuevo archivo.

Intercalación
Es la unión de los elementos de dos listas.
La diferencia entre la correspondencia y la intercalación es que con la intercalación debe leerse totalmente cada una de ellas.

.

Ordenamiento Shell

El método de Shell es una versión mejorada del método de inserción directa recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959. Este método también se conoce con el nombre de inserción con incrementos decrecientes.
En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.

CARACTERÍSTICAS

• Se trata de un algoritmo de ordenación interna. Al igual que cualquier otro de ordenación interna (los datos están en memoria principal) podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.

• Se basa en comparaciones e intercambios.
• Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
• No es estable: dados dos elementos que al compararlos sean "iguales" no mantienen necesariamente el orden relativo inicial entre ellos
• El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
• Sin embargo, optimizaciones posteriores han logrado reducir esa cota... Por ejemplo, con la optimización de Robert Sedgewick se llega a O(n4/3), y con la propuesta por Vaughan Pratt se llega al orden de O(n log2n).
• En 1992, Greg Plaxton, Bjorn Poonen y Torsten Suel prueban que es posible incluso rebajar aún más esas cotas.
• En cierto modo, puede considerarse una ampliación del algortimo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
• No es un algoritmo en-línea.

EFICIENCIA

El análisis de eficiencia es un problema complicado y aun no resuelto.

Nadie ha sido capaz de establecer la mejor secuencia de incrementos cuando N es muy grande.
Una medida de eficiencia es:
Contar el # de comparaciones (C)
Contar el # de movimientos de items (M)
Estos están en función de el #(n) de items a ser ordenados.
Un "buen algoritmo" de ordenamiento requiere de un orden nlogn comparaciones.
La eficiencia de los algoritmos se mide por el número de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el número de elementos que tiene el arreglo o vector a ordenar y se dice que un algoritmo realiza O(n2) comparaciones cuando compara n veces los n elementos, n x n = n2

Archivos Secuenciales

Archivo secuencial es la forma más simple de almacenar y recuperar registros en un archivo.
En un archivo secuencial, se almacenan los registros uno tras otro. El primer registro almacenado se coloca al principio del archivo y el segundo se almacena inmediatamente después.

Operaciones

Las operaciones que podemos realizar sobre éstos archivos son:

....Creación
La creación exige organización, estructura, localización o reserva de espacio en el soporte
de almacenamiento, transferencia del archivo del soporte antiguo al nuevo.
Es la operación que permite al usuario acceder al archivo de datos para conocer el contenido
de uno, varios o todos los registros

....Actualización
Es la operación que permite tener actualizado (puesto al día) el archivo, de tal modo que sea posible realizar las siguientes operaciones con sus registros: Consulta del contenido de un registro. Inserción de un registro nuevo en el archivo.

....Clasificación
Reubicación de los registros de tal forma que queden ordenados según determinados criterios.
Una operación muy importante en un archivo es la clasificación u ordenación. Esta clasificación
se realizará de acuerdo con el valor de un campo específico, pudiendo ser ascendente (creciente) o descendente (decreciente): alfabética o numérica.

....Borrado
Es la operación inversa a la creación de un archivo. Cuando se destruye (anula o borra) un archivo, éste ya no se puede utilizar y, por consiguiente, no se podrá acceder a ninguno de sus registros.

...Reorganización De Un Archivo
La reorganización suele consistir en la copia de un nuevo archivo a partir del archivo modificado, a fin de obtener una nueva estructura lo más óptima posible.

.

Indizacion de Archivos

Es la aplicación de incluir índices en el almacenamiento de los archivos;
de esta forma nos será más fácil buscar algún registro sin necesidad de ver todo el archivo.
Un índice en un archivo consiste en un listado de los valores del campo clave que ocurren en el archivo,
junto con la posición de registro correspondiente en el almacenamiento masivo.

• La colocación de un listado al inicio del archivo: para la identificación del contenido.
• La presentación de un segundo índice: para reflejar la información de cada punto principal del índice anterior.
• La actualización de los índices: Cuando se insertan y eliminan archivos, es preciso actualizar los
• índices para evitar contratiempos actualizando un archivo.
• La organización de un índice: Nos evita examinar archivo por archivo para recuperar
• algún registro buscado; por lo tanto ahorraríamos tiempo si tenemos una adecuado organización de los índices.