ARBOLES AVL

ARBOLES AVL 

¿Qué Son? 

El nombre AVL son las iniciales de los hombres que idearon este tipo de árbol Adelson-Velskii y Landis en 1962.

Básicamente un árbol AVL es un Árbol binario de búsqueda al que se le añade una condición de equilibrio. Esta condición es que para todo nodo la altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1.

Caracteristicas:

- Un AVL es un ABB

- La diferencia entre las alturas de los subárboles derecho e izquierdo no debe excederse en más de 1.
- Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles.
- Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su subárbol izquierdo es más alto y 0 si las alturas son las mismas.
- La inserción y eliminación en AVLs es la misma que en los ABBs. 

Equilibrio:

Equilibrio (n) = altura-der (n) – altura-izq (n) describe relatividad entre subárbol der y subárbol izq.
+ (positivo) -> der mas alto (profundo)
- (negativo) -> izq mas alto (profundo)

Un árbol binario es un AVL si y sólo si cada uno de sus nodos tiene un equilibrio de –1, 0, + 1.
Si alguno de los pesos de los nodos se modifica en un valor no válido (2 o -2) debe seguirse un esquema de rotación.

Operaciones sobre un AVL:

- Insertar
- Balancear
* Caso 1 Rotación simple izquierda RSI
* Caso 2 Rotación simple derecha RSD
* Caso 3 Rotación doble izquierda RDI
* Caso 4 Rotación doble derecha RDD
- Eliminar
- Calcular Altura

Balancear el Árbol:

Caso 1: Rotación simple izquierda RSI

Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo (+) hacemos rotación sencilla izquierda.

Luego de la rotación: 

Caso 2: Rotación simple derecha RSD

Luego de la rotación: 

Eliminar un Dato:

Al eliminar un nodo en un árbol AVL puede afectar el equilibrio de sus nodos. Entonces hay que hacer rotaciones simples o dobles.
Eliminas un nodo como lo hacemos en un árbol binario ordenado. Al localizar el nodo que queremos eliminar seguimos este procedimiento:
- Si el nodo es un nodo hoja, simplemente lo eliminamos.
- Si el nodo solo tiene un hijo, lo sustituimos con su hijo.
- Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y colocamos el hijo izquierdo en el subárbol izquierdo del hijo derecho.

Ahora que hemos eliminado el nodo, tenemos que volver a equilibrar el árbol:
- Si el equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo concluye.
- Si el padre del nodo eliminado cambio de +-1 a 0, la altura del árbol ha cambiado y se afecte el equilibrio de su abuelo.
- Si el equilibrio del padre del nodo eliminado cambia de +- 1 a +- 2 hay que hacer una rotación.
- Después de concluirla, el equilibrio del padre podría cambiar, lo que, a su vez, podría forzarnos a hacer otros cambios (y probables rotaciones) en toda la ruta hacia arriba a medida que ascendemos hacia la raíz. Si encontramos en la ruta un nodo que cambie de 0 a +- 1 entonces terminamos.

MANEJO DE ARCHIVOS

Manejo de Archivos en C:

¿Qué Son? 

Los datos que hemos tratado hasta el momento han residido en la memoria principal. Sin embargo, las grandes cantidades de datos se almacenan normalmente en un dispositivo de memoria secundaria. Estas colecciones de datos se conocen como archivos (antiguamente ficheros). Un archivo es un conjunto de datos estructurados en una colección de entidades elementales o básicas denominadas registros que son de igual tipo y constan a su vez de diferentes entidades de nivel más bajos denominadas campos. Hay dos tipos de archivos, archivos de texto y archivos binarios. Un archivo de texto es una secuencia de caracteres organizadas en líneas terminadas por un carácter de nueva línea. 

En estos archivos se pueden almacenar canciones, fuentes de programas, base de datos simples, etc. Los archivos de texto se caracterizan por ser planos, es decir, todas las letras tienen el mismo formato y no hay palabras subrayadas, en negrita, o letras de distinto tamaño o ancho. Un archivo binario es una secuencia de bytes que tienen una correspondencia uno a uno con un dispositivo externo. Así que no tendrá lugar ninguna traducción de caracteres. Además, el número de bytes escritos (leídos) será el mismo que los encontrados en el dispositivo externo. Ejemplos de estos archivos son Fotografías, imágenes, texto con formatos, archivos ejecutables (aplicaciones), etc. 

En c, un archivo es un concepto lógico que puede aplicarse a muchas cosas desde archivos de disco hasta terminales o una impresora. Se asocia una secuencia con un archivo especifico realizando una operación de apertura. Una vez que el archivo está abierto, la información puede ser intercambiada entre este y el programa. Se puede conseguir la entrada y la salida de datos a un archivo a través del uso de la biblioteca de funciones; C no tiene palabras claves que realicen las operaciones de E/S. La siguiente tabla da un breve resumen de las funciones que se pueden utilizar. Se debe incluir la librería STDIO.H. Observe que la mayoría de las funciones comienzan con la letra “F”, esto es un vestigio del estándar C de Unix.

El puntero a un archivo:

El puntero a un archivo es el hilo común que unifica el sistema de E/S con buffer. Un puntero a un archivo es un puntero a una información que define varias cosas sobre él, incluyendo el nombre, el estado y la posición actual del archivo. En esencia identifica un archivo especifico y utiliza la secuencia asociada para dirigir el funcionamiento de las funciones de E/S con buffer. Un puntero a un archivo es una variable de tipo puntero al tipo FILE que se define en STDIO.H. Un programa necesita utilizar punteros a archivos para leer o escribir en los mismos. Para obtener una variable de este tipo se utiliza una secuencia como esta: FILE *F.

Apertura de un archivo

La función fopen(): Abre una secuencia para que pueda ser utilizada y la asocia a un archivo. Su prototipo es: FILE *fopen(const char nombre_archivo, cost charmodo); Donde nombre_archivo es un puntero a una cadena de caracteres que representan un nombre valido del archivo y puede incluir una especificación del directorio. La cadena a la que apunta modo determina como se abre el archivo. La siguiente tabla muestra los valores permitidos para modo.

Cierre de un archivo

La función fclose():Cierra una secuencia que fue abierta mediante una llamada a fopen(). Escribe toda la información que todavía se encuentre en el buffer en el disco y realiza un cierre formal del archivo a nivel del sistema operativo. Un error en el cierre de una secuencia puede generar todo tipo de problemas, incluyendo la pérdida de datos, destrucción de archivos y posibles errores intermitentes en el programa. El prototipo de esta función es: int fclose(FILE *F); Donde F es el puntero al archivo devuelto por la llamada a fopen(). Si se devuelve un valor cero significa que la operación de cierre ha tenido éxito. Generalmente, esta función solo falla cuando un disco se ha retirado antes de tiempo o cuando no queda espacio libre en el mismo.

Acá un ejemplo de como hacer la lectura y modificación de un archivo en C:

El código anterior realiza la apertura de una archivo de texto, y permite escribir y modificar su nombre y edad respectivamente.

SI DESEA CONOCER MAS SOBRE ESTE TEMA, INGRESE A ESTE ENLACE 

ÁRBOLES B

¿Qué Son?

Los B-árboles sugieron en 1972 creados por R.Bayer y E.McCreight.El problema original comienza con la necesidad de mantener índices en almacenamiento externo para acceso a bases de datos,es decir,con el grave problema de la lentitud de estos dispositivos se pretende aprovechar la gran capacidad de almacenamiento para mantener una cantidad de información muy alta organizada de forma que el acceso a una clave sea lo más rápido posible.

Como se ha visto anteriormente existen métodos y estructuras de datos que permiten realizar una búsqueda dentro de un conjunto alto de datos en un tiempo de orden O(log2n). Así tenemos el caso de los árboles binarios AVL.¿Por qué no usarlos para organizar a través de ellos el índice de una base de datos?la respuesta aparece si estudiamos más de cerca el problema de acceso a memoria externa.Mientras que en memoria interna el tiempo de acceso a n datos situados en distintas partes de la memoria es independiente de las direcciones que estos ocupen(n*cte donde cte es el tiempo de acceso a 1 dato),en memoria externa es fundamental el acceder a datos situados en el mismo bloque para hacer que el tiempo de ejecución disminuya debido a que el tiempo depende fuertemente del tiempo de acceso del dispositivo externo,si disminuimos el número de accesos a disco lógicamente el tiempo resultante de ejecución de nuestra búsqueda se ve fuertemente recortado.Por consiguiente,si tratamos de construir una estructura de datos sobre disco es fundamental tener en cuenta que uno de los factores determinantes en el tiempo de ejecución es el número total de accesos,de forma que aunque dicho n&uacite;mero pueda ser acotado por un orden de eficiencia es muy importante tener en cuenta el número real ya que el tiempo para realizar un acceso es suficientemente alto como para que dos algoritmos pese a tener un mismo orden,puedan tener en un caso un tiempo real de ejecución aceptable y en otro inadmisible.

De esta forma,si construimos un árbol binario de búsqueda equilibrado en disco,los accesos a disco serán para cargar en memoria uno de los nodos,es decir,para poder llevar a memoria una cantidad de información suficiente como para poder decidir entre dos ramas.Los árboles de múltiples ramas tienen una altura menor que los árboles binarios pues pueden contener más de dos hijos por nodo,además de que puede hacerse corresponder los nodos con las páginas en disco de forma que al realizar un único acceso se leen un número alto de datos que permiten elegir un camino de búsqueda no entre dos ramas,sino en un número considerablemente mayor de ellas.Además,este tipo de árboles hace más fácil y menos costoso conseguir equilibrar el árbol.

DEFINICIÓN:

Los B-árboles son árboles cuyos nodos pueden tener un número múltiple de hijos tal como muestra el esquema de uno de ellos en la figura 1. 

Como se puede observar en la figura 1,un B-árbol se dice que es de orden m si sus nodos pueden contener hasta un máximo de m hijos.En la literatura también aparece que si un árbol es de orden m significa que el mínimo número de hijos que puede tener es m+1(m claves).Nosotros no la usaremos para diferenciar el caso de un número máximo par e impar de claves en un nodo.

El conjunto de claves que se sitúan en un nodo cumplen la condición:

INSERCIÓN EN UN B-ÁRBOL:

Para insertar una nueva clave usaremos un algoritmo que consiste en dos pasos recursivos:

1. Buscamos la hoja donde debieramos encontrar el valor de la clave de una forma totalmente paralela a la búsqueda de ésta tal como comentabamos en la sección anterior(si en esta búsqueda encontramos en algun lugar del árbol la clave a insertar,el algoritmo no debe hacer nada más).Si la clave no se encuentra en el árbol habremos llegado a una hoja que es justamente el lugar donde debemos realizar esa inserción.
2. Situados en un nodo donde realizar la inserción si no está completo,es decir,si el número de claves que existen es menor que el orden menos 1 del árbol,el elemento puede ser insertado y el algoritmo termina.En caso de que el nodo esté completo insertamos la clave en su posición y puesto que no caben en un único nodo dividimos en dos nuevos nodos conteniendo cada uno de ellos la mitad de las claves y tomando una de éstas para insertarla en el padre(se usará la mediana).Si el padre está también completo,habrá que repetir el proceso hasta llegar a la raíz.En caso de que la raíz esté completa,la altura del árbol aumenta en uno creando un nuevo nodo raíz con una única clave.

BORRADO EN UN B-ÁRBOL.

La idea para realizar el borrado de una clave es similar a la inserción teniendo en cuenta que ahora,en lugar de divisiones,realizamos uniones.Existe un problema añadido,las claves a borrar pueden aparecer en cualquier lugar del árbol y por consiguiente no coincide con el caso de la inserción en la que siempre comenzamos desde una hoja y propagamos hacia arriba.La solución a esto es inmediata pues cuando borramos una clave que está en un nodo interior,lo primero que realizamos es un intercambio de este valor con el inmediato sucesor en el árbol,es decir,el hijo más a la izquierda del hijo derecho de esa clave.

Las operaciones a realizar para poder llevar a cabo el borrado son por tanto:

1. Redistribución:la utilizaremos en el caso en que al borrar una clave el nodo se queda con un número menor que el mínimo y uno de los hermanos adyacentes tiene al menos uno más que ese mínimo,es decir,redistribuyendo podemos solucionar el problema.
2. Unión:la utilizaremos en el caso de que no sea posible la redistribución y por tanto sólo será posible unir los nodos junto con la clave que los separa y se encuentra en el padre.

En definitiva,el algoritmo nos queda como sigue:

1. Localizar el nodo donde se encuentra la clave.
.
2. Si el nodo localizado no es una hoja,intercambiar el valor de la clave localizada con el valor de la clave más a la izquierda del hijo a la derecha.En definitiva colocar la clave a borrar en una hoja.Hacemos nodo actual igual a esa hoja.
3. Borrar la clave.
4. Si el nodo actual contiene al menos el mínimo de claves como para seguir siendo un B-árbol,fin.
5. Si el nodo actual tiene un número menor que el mínimo:
1. Si un hermano tiene más del mínimo de claves,redistribución y fin.
2. Si ninguno de los hermanos tiene más del mínimo,unión de dos nodos junto con la clave del padre y vuelta al paso 4 para propagar el borrado de dicha clave(ahora en el padre).

ÁRBOLES B+

¿Qué Son? 

Descripción:

Una variante de los árboles B que permite realizar de forma eficiente tanto el acceso directo mediante clave como el procesamiento en secuencia ordenada de los registros, es la estructura de árbol B+ (propuesta por Knuth [Knu97b]). Los árboles B+ almacenan los registros de datos sólo en sus nodos hoja (agrupados en páginas o bloques), y en los nodos interiores y nodo raíz se construye un índice multinivel mediante un árbol B, para esos bloques de datos.

Los árboles-B+ se han convertido en la técnica mas utilizada para la organización de archivos indizados. La principal característica de estos arboles es que todas las claves se encuentran en las hojas y por lo tanto cualquier camino desde la raíz hasta alguna de las claves tienen la misma longitud.

Propiedades:
Un árbol B+ de orden n es una estructura formada por un conjunto de bloques de registros ordenados por clave, que se almacenan a nivel de hoja (llamado conjunto secuencia), y un índice sobre un árbol B de orden n para los bloques de registros (llamado conjunto índice).
Las restricciones de ocupación que determine el orden n del árbol sólo afectarán al conjunto índice pero no a los bloques de registros, a los cuales se les exigirá una ocupación mínima (y una máxima) pero no estará relacionada con el orden del árbol.
Por tanto, las propiedades que estudiamos para los árboles B pueden aplicarse a los árboles B+; la diferencia entre ambos está en el nivel de las hojas. Además, los árboles B+ no almacenan en sus nodos interiores direcciones de registros, sino sólo claves. Los registros se obtienen a nivel de las hojas, donde se encuentran almacenados ordenados dentro de cada bloque. Es decir, los nodos hoja del conjunto índice direccionan los nodos terminales que contienen los datos.
Es de notar que los arboles-B+ ocupan un poco mas de espacio que los arboles-B, y esto ocurre al existir duplicidad en algunas claves. Sin embargo, esto es aceptable si el archivo se modifica frecuentemente, puesto que se evita la operación de reorganización del árbol que es tan costosa en los arboles-B.

Formalmente se define un árbol-B+ de la siguiente manera:

Cada pagina, excepto la raíz, contiene entre n y 2n elementos.

Cada pagina, excepto la raíz, tiene entre n + 1 y 2n + 1 descendientes. Se utiliza m para expresar el numero de elementos por pagina.

La pagina raíz tiene al menos dos descendientes.

Las paginas hojas están todas al mismo nivel.

Todas las claves se encuentran en las paginas hojas.

Las claves de las paginas raíz e interiores se utilizan como índices.

Estructura

Conjunto secuencia: Está formado por los registros de datos, agrupados dentro de bloques en los que se mantienen ordenados en base a la clave de búsqueda. Estos bloques no tienen por qué almacenarse físicamente en el archivo según la ordenación lógica, por lo que se mantiene una lista doblemente enlazada de bloques, y de este modo poder recuperar ordenados todos los registros de datos recorriendo toda la lista de bloques.

Conjunto índice: Es un árbol B de orden n que indexa los bloques de registros de datos del conjunto secuencia. En los nodos de este árbol B sólo se almacenan claves de búsqueda y direcciones de nodos descendientes, excepto los nodos hoja, que contienen las direcciones de los bloques con los registros de datos del conjunto secuencia.

Inserción en un árbol B+:

La inserción en un árbol B+ es similar a la del árbol B se diferencia en el momento que una pagina deja de cumplir la condición del numero de datos almacenados. Para realizarla se debe subir una copia de la clave mediana de los datos del nodo a la pagina padre, solo se duplica la información cuando la clave que sube es de una pagina hoja.

Los pasos a seguir para una inserción son los siguientes:

1.Se ubica en la pagina raíz.

2.Se evalúa si es una pagina hoja

    2.1.Si la respuesta es afirmativa, se evalúa si no sobrepasa los limites de datos.

        2.1.1.Si la respuesta es afirmativa, entonces se procede a insertar el nuevo valor en lugar del correspondiente.

        2.1.2.Si la respuesta es negativa, se divide la pagina en dos, se sube una copia de  la mediana a la pagina padre, si la

                    pagina padre se encuentra llena se debe de partir igual y así el mismo proceso hasta donde sea necesario, si   este proceso llega hasta la raíz la altura del árbol aumenta en uno.

     2.2. si no es hoja, se compara el elemento a insertar con con cada uno de los valores almacenados para encontrar la pagina descendiente donde proseguir la búsqueda. Se regresa al paso 1.

Ejemplo de inserción:

-Insertar las siguientes claves a un árbol de orden 5:  10-27-29-17-25-21-15-31-13-51-20-24-48-19-60-35-66

Eliminación:

La operación de eliminación en árboles-B+ es mas simple que en árboles-B. Esto ocurre porque las claves a eliminar siempre se encuentran en las paginas hojas. En general deben distinguirse los siguientes casos:

Si al eliminar una clave, la cantidad de llaves queda mayor o igual que [m/2] entonces termina la operación. Las claves de los nodos raíz o internos no se modifican por más que sean una copia de la clave eliminada en las hojas.

Si al eliminar una clave, la cantidad de llaves queda menor que [m/2] entonces debe realizarse una redistribución de claves, tanto en el índice como en las paginas hojas.

Ejemplo del caso 1:

Ejemplo del caso 2:

Cibergrafia

https://sites.google.com/site/tutoriasarboles/arboles-b-y-b