UNIDAD TEMA SUBTEMAS

4 Estructura de datos no lineales 4.1 Arboles.

4.1.1 Concepto de árbol.

4.1.2 Clasificación de árboles

4.1.3 Operaciones básicas sobre
árboles binarios.

4.1.4 Aplicaciones.

4.1.5 Arboles balanceados (AVL).

4.2 Grafos.

4.2.1 Terminología de grafos.

4.2.2 Operaciones básicas sobre
grafos.

4.1 ÁRBOLES

Una pequeña explicacion de arboles etc.

4.1.1 DEFINICION DE ÁRBOL

Un árbol es un conjunto de n registros (n>0, árbol vacío no está definido), tales que, hay un registro especial llamado RAIZ y los demás registros están particionados en conjuntos disjuntos, cada uno de los cuales es un árbol.

Un árbol es una estructura recursiva por definición, además cada registro que tenga hijos se podrá considerar como la raíz de un sub-árbol.

Las ramificaciones de cada nodo o registro suelen llamarse hijos y los nodos de los cuales salen las ramificaciones se llaman padres. Los registros que tienen un mismo padre se denominan hermanos.

En ciencias de la informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Solo que puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

4.1.2 CLASIFICACIÓN DE ÁRBOLES

· Árboles Binarios

Ejemplo de árbol (binario) 1

Un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Tipos de árboles binarios

· Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

· Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

· Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

· A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

· Árbol de búsqueda binario auto-balanceable

En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.

Tiempos para varias operaciones en términos del número de nodos en el árbol n:

Las rotaciones internas en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico

Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.

Estructuras de datos populares que implementan este tipo de árbol:

· Árbol AVL

Los árboles AVL 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. El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, 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.

Los árboles AVL más profundos son los árboles de Fibonacci.

Un ejemplo de árbol binario no equilibrado(no es AVL)

· es AVL

Definición de árbol AVL

· Un árbol vacío es un árbol AVL

· Si es un árbol no vacío y y sus subárboles, entonces es AVL si y solo si:

· Árboles Rojo-Negro

Un árbol rojo-negro es un tipo abstracto de datos. Concretamente, es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. Es complejo, pero tiene un buen peor caso de tiempo de ejecución para sus operaciones y es eficiente en la práctica. Puede buscar, insertar y borrar en un tiempoO(log n), donde n es el número de elementos del árbol.

Un árbol rojo-negro es un árbol binario de búsqueda en el que cada nodo tiene un atributo de color cuyo valor es rojo o negro. En adelante, se dice que un nodo es rojo o negro haciendo referencia a dicho atributo.

Además de los requisitos impuestos a los árboles binarios de búsqueda convencionales, se deben satisfacer las siguientes reglas para tener un árbol rojo-negro válido:

1. Todo nodo es o bien rojo o bien negro.

2. La raíz es negra.

3. Todas las hojas (NIL) son negras.

4. Todo nodo rojo debe tener dos nodos hijos negros.

5. Cada camino desde un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros.

· Árbol AA

Un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente.

Los árboles AA son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho. En otras palabras, ningún nodo rojo puede ser un hijo izquierdo. De esta manera se simula un árbol 2-3 en lugar de un árbol 2-3-4, lo que simplifica las operaciones de mantenimiento. Los algoritmos de mantenimiento para un árbol rojo-negro necesitan considerar siete diferentes formas para balancear adecuadamente el árbol:

En un árbol AA, al cumplirse el estricto requisito de que sólo los enlaces derechos pueden ser rojos, sólo es necesario considerar dos formas:

· Árboles Multicamino

Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas en computación.

Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:

· A está vacío

· Cada nodo de A muestra la siguiente estructura: [nClaves,Enlace₀,Clave₁,...,Clave_nClaves,Enlace_nClaves]

nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves <= g-1

Enlace_i, son los enlaces a los subárboles de A, pudiendo ser: 0 <= i <= nClaves

Clave_i, son los valores de clave, pudiendo ser: 1 <= i <= nClaves

· Clave_i < Clave_i+1

· Cada valor de clave en el subárbol Enlace_i es menor que el valor de Clave_i+1

· Los subárboles Enlace_i, donde 0 <= i <= nClaves, son también árboles m-caminos.

La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos.

· Árboles B (Árboles de búsqueda multicamino autobalanceados)

los árboles-B o B-árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles balanceados de búsqueda en los cuales cada nodo puede poseer más de dos hijos.Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten.

· Árbol-B+

Un árbol B+ es un tipo de estructura de datos de árbol, representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Un árbol B+ es una variación de un árbol B.

En un árbol B+, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo nivel, que corresponde al más bajo. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.

Las estructuras de árbol B+ reúnen las siguientes características:

· El número máximo de claves en un registro es llamado el orden del árbol B+.

· El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.

· El número de claves que pueden ser indexadas usando un árbol B+ está en función del orden del árbol y su altura.

· Árbol-B*

Un árbol-B* es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto los nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Cuando ambos están llenos, entonces los dos nodos se transforman en tres. También requiere que la clave más a la izquierda no sea usada nunca.

No se debe confundir un árbol-B* con un árbol-B+, en el que los nodos hoja del árbol están conectados entre sí a través de una lista enlazada, aumentando el coste de inserción para mejorar la eficiencia en la búsqueda.

4.1.3 OPERACIONES BASICAS CON ARBOLES BINARIOS

Las rotaciones en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto (o casi perfecto) del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico.

Las operaciones comunes en árboles son:

· Enumerar todos los elementos.

· Buscar un elemento.

· Dado un nodo, listar los hijos (si los hay).

· Borrar un elemento.

· Eliminar un subárbol (algunas veces llamada podar).

· Añadir un subárbol (algunas veces llamada injertar).

· Encontrar la raíz de cualquier nodo.

Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:

· Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.

· Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array.

4.1.4 APLICACIONES

Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en Computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de Elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, en la toma de decisiones, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro.

A los árboles ordenados de grado dos se les conocen como árboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los árboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

A continuación podremos observar un caso típico del uso de árboles.

Ejemplo de un árbol

4.1.5 ÁRBOLES BALANCEADO (AVL)

Deﬁnición. Un árbol AVL es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1.

La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskii y Landis).

Recordamos que un árbol binario de búsqueda es un árbol binario en el cual cada nodo cumple con que todos los nodos de su subárbol izquierdo son menores que la raíz y todos los nodos del subárbol derecho son mayores que la raíz.

Recordamos también que el tiempo de las operaciones sobre un árbol binario de búsqueda son O(log n) promedio, pero el peor caso es O(n), donde n es el número de elementos.

La propiedad de equilibrio que debe cumplir un árbol para ser AVL asegura que la profundidad del árbol sea O(log(n)), por lo que las operaciones sobre estas estructuras no deberán recorrer mucho para hallar el elemento deseado. Como se verá, el tiempo de ejecución de las operación es sobre estos árboles es, a lo sumo O(log(n)) en el peor caso, donde n es la cantidad de elementos del árbol.

Sin embargo, y como era de esperarse, esta misma propiedad de equilibrio de los árboles AVL implica una diﬁcultad a la hora de insertar o eliminar elementos: estas operaciones pueden no conservar dicha propiedad.

Figure 1. Árbol AVL de enteros

A modo de ejempliﬁcar esta diﬁcultad, supongamos que al árbol AVL de enteros de Figure 1 le queremos agregar el entero 3. Si lo hacemos con el procedimiento normal Mde inserción de árbols binarios de búsqueda el resultado sería el árbol de Figure 2 el cual ya no cumple con la condición de equilibrio de los árboles AVL dado que la altura del subárbol izquierdo es 3 y la del subárbol derecho es 1.

Figure 2. Árbol que no cumple con la condición de equilibrio de los árboles AVL. 2Árboles AVL

En Section 5 se pasará a explicar una serie de operaciones sobre los nodos de un árbol AVL con las cuales poder restaurar la propiedad de equilibrio de un árbol AVL luegode agregar o eliminar elementos.

4.2 GRAFOS

Un grafo es una estructura de datos no lineal con la siguiente característica: un nodo puede apuntar a varios y a su vez ser apuntado por otro.

Consiste de un conjunto de nodos o vértices y un conjunto de ejes o aristas. Usualmente se lo denota = (). Las aristas son pares de vértices () con 2. Si () 2, se dice que y están conectados o son adyacentes. Un trazado o dibujo de un grafo = () usando segmentos de 1 recta para las aristas es una asignación de una posición en el plano a cada vértice en V. En las versiones más simples, los vértices son dibujados como puntos y las aristas como segmentos entre vértices. De aquí en más supondremos que el trazado usa segmentos para las aristas, excepto cuando se aclare lo contrario. También se supondrá que el grafo es conexo, ya que si el grafo a trazar no lo es, se puede trazar cada componente conexa por separado.

Los grafos sólo contienen información relacional entre los vértices, así que en principio no tienen ninguna forma \natural" de ser dibujados. Sin embargo, de las infinitas formas de trazar un grafo en el plano, algunas son claramente peores que otras, siempre teniendo en cuenta que el objetivo es visualizar el grafo.

4.2.1 TERMINOLOGÍA DE GRAFOS

Un grafo se compone por un conjunto de V vértices y un conjunto de A aristas. Cada arista se identifica con el par de vértices que une. Los vértices de una arista son entre si nodos adyacentes.

ü Grado de un nodo:

Numero de aristas que contiene ese nodo. Si el grado de un nodo es 0, se dice que es un nodo aislado.

ü Grado de un grafo:

Números de vértices de ese grafo.

ü Camino:

Un camino C de longitud N de un nodo V1 a un nodo V2, se define como la secuencia de nodos por los que hay que pasar para llegar del nodo V1 a V2. La longitud es el número de aristas que comprende el camino. El camino es cerrado si empieza y termina en el mismo nodo. El camino es simple si todos los nodos de dicho camino son distintos a excepción de los de los extremos que pueden ser iguales.

ü Bucles:

Aristas cuyos extremos son idénticos.

ü Aristas múltiples:

Dos o más aristas que conectan los mismos nodos

Tipos de grafos:

Ø Grafo conectado o conexo:

Existe un camino simple entre dos cualquiera de sus nodos.

Ø Grafo desconectado:

Aquel en que existen nodos que no están unidos por ningún camino

Ø Grafo dirigido:

Cada arista tiene asignada una dirección (identificada por un par ordenado).

Ø Grafo no dirigido:

La arista está definida por un par no ordenado.}

Ø Grafo sencillo:

Aquel que no tiene ni bucles ni aristas múltiples.-

Ø Grafo múltiple o multígrafo:

Permite la existencia de aristas múltiples o bucles.-

Ø Grafo completo:

Cada nodo del grafo es adyacente a todos los demás.-

Ø Grafo etiquetado con peso ponderado:

Cada arista tiene asociado un valor denominado peso. Se usa para indicar algún criterio de evaluación como la longitud o la importancia de la arista respecto a un parámetro.-

Ø Peso de un camino:

La suma de los pesos de las aristas del camino.

Representación de los grafos:

Existen dos formas de representar un grafo:

- Con memoria estática (Matriz adyacente): Matriz de N*N elementos donde N es el número de nodos del grafo. Cada posición M (i, j) indica si hay una conexión o no entre los nodos que están asociados a la posición i y j de la matriz.

- Con memoria dinámica. Se utilizan 2 listas enlazadas:

*Lista de nodos: Formada por todos los vértices.

*Lista de adyacentes: Contiene las aristas del grafo.

4.2.2 OPERACIONES BASICAS CON GRAFOS

En los grafos, como en todas las estructuras de datos, las dos operaciones básicas son insertar y borrar. En este caso, cada una de ellas se desdobla en dos, para insertar/eliminar vértices e insertar/eliminar aristas.

Insertar vértice

La operación de inserción de un nuevo vértice es una operación muy sencilla, únicamente consiste en añadir una nueva entrada en la tabla de vértices (estructura de datos que almacena los vértices) para el nuevo nodo. A partir de ese momento el grafo tendrá un vértice más, inicialmente aislado, ya que ningúna arista llegará a él.

Insertar arista

Esta operación es también muy sencilla. Cuando se inserte una nueva arista en el grafo, habrá que añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los que un vértice puede acceder mediante una arista) del nodo origen, así si se añade la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como nuevo destino.

Eliminar vértice

Esta operación es inversa a la inserción de vértice. En este caso el procedimiento a realizar es la eliminación de la tabla de vértices del vértice en sí. A continuación habrá que eliminar las aristas que tuviesen al vértice borrado como origen o destino.

Eliminar arista

Mediante esta operación se borra un arco del grafo. Para llevar a cabo esta acción es necesario eliminar de la lista de adyacencia del nodo origen el nodo correspondiente al nodo destino.

Otras operaciones

Las operaciones adicionales que puede incluir un grafo son muy variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo, también podemos encontrarnos con ejecución de algoritmos que busquen caminos más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.

VIDEO: http://www.youtube.com/watch?v=UxhpORErvlQ

VIDEOS CON RELACION A LOS TEMAS