ESTRUCTURAS DE DATOS:

En este blog es creado para compartir el conocimiento sobre este pilar de la Ingeniería de sistemas, el como proponiendo, explicando y profundizando un poco más sobre los temas que conformaran este blog, entenderán de manera más eficiente los temas que aquí trataremos.
Encontraran terminologías generales sobre árboles A.V..L, árboles B, árboles B+, sus operaciones básicas y ejemplos de los mismos. También trataremos temas sobre los Grafos, como: su clasificación, tipos, algoritmos y  métodos.

ARBOLES A.V.L

Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus sub-árboles izquierdo y derecho no difieren en más de 1.
No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos.
El algoritmo para mantener un árbol A.V.L equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o borrado.

OPERACIONES EN ARBOLES A.V.L:

Los AVL son también ABB, de modo que mantienen todas las operaciones que poseen éstos. Las nuevas operaciones son las de equilibrar el árbol, pero eso se hace como parte de las operaciones de insertado y borrado.

Si hay desbalance:
-Rotación hacia la izquierda.
-Rotación hacia la derecha.
-Doble rotación hacia la izquierda.
-Doble rotación hacia la derecha.

y el inorden debe ser igual tanto antes como después de la rotación.

ROTACIÓN HACIA LA IZQUIERDA:

se realiza una rotación a la izquierda cuando un árbol queda desbalanceado a la derecha. y es la acción de 2 apuntadores después de una altura no permitida.

Ejemplo 1:

12, 6, 20, 15, 22, 30.

Tenemos que esta des-balanceado por la derecha; por lo tanto realizamos una rotación hacia la izquierda y nos queda:

Es A.V.L.

Ejemplo 2:

Inorden:

D, B, E, A, F, C, H, G, I, J.

Tenemos que esta des-balanceado por la derecha; por lo tanto realizamos una rotación hacia la izquierda y nos queda:

Es A.V.L.

ROTACIÓN HACIA LA DERECHA:

F.B= Factor de Balance.

1. El nodo indicado por "P" tiene F.B. > 1.

2. El nodo indicado por "Q" tiene F.B.= 1.

Ejemplo:

Inorden:

F, D, B, E, A, C.

Tenemos que esta des-balanceado por izquierda; por lo tanto realizamos una rotación hacia la derecha y nos queda:

Es A.V.L.

DOBLE ROTACIÓN HACIA LA IZQUIERDA:

Se realiza si cumple:

1. El nodo indicado por "p" tiene un factor de balance < 1.

2. El nodo indicado por "q" tienen un factor de balance=1.

Entonces, realizamos una simple rotación hacia la derecha desde "q" y una simple hacia la izquierda desde "p".

Ejemplo:

10, 15, 12.

Si evidenciamos el grafo y los factores de balance de los nodos indicados "p" y "q",  tenemos que el F.B. del nodo "p"<1 (cumple la 1ra regla). Y el F.B. del nodo "q"=1 (cumple la 2da regla).

Entonces realizamos los siguiente:

Una rotación hacia la derecha desde el nodo "q"; lo cual nos da como resultado:

Y ahora procedemos a realizar una rotación hacia la izquierda desde el nodo "p"; lo cual no da como resultado:

Ahora si es A.V.L

DOBLE ROTACIÓN HACIA LA DERECHA:

F.B= Factor de Balance.

1. El nodo indicado por "p" tiene F.B. > 1.

2. El nodo indicado por "q" tiene F.B.= -1.

Entonces, realizamos una simple rotación hacia la izquierda desde "q" y una simple hacia la derecha desde "p".

Ejemplo:

Si evidenciamos el grafo y los factores de balance de los nodos indicados "p" y "q",  tenemos que el F.B. del nodo "p">1 (cumple la 1ra regla). Y el F.B. del nodo "q"=-1 (cumple la 2da regla).

Entonces realizamos los siguiente:

Una rotación hacia la izquierda desde el nodo "q"; lo cual nos da como resultado:

Y ahora procedemos a realizar una rotación hacia la derecha desde el nodo "p"; lo cual no da como resultado:

Ahora si es A.V.L.

ÁRBOL B

Los árboles reciben su nombre de R. Bayer, quien en 1970 propuso un nuevo tipo de árboles, en los que todas las páginas, excepto una), contienen entre n y 2n nodos, siendo n una constante dada. Como consecuencia de esto se puede deducir que los árboles B no son árboles binarios como sí lo son los binarios de búsqueda o los AVL.

En los árboles B los nodos se agrupan dentro de páginas, por lo que se podría definir a la página como un conjunto de nodos.

Los árboles B deben cumplir las siguientes características en cuanto a estructura:

Toda página tiene como máximo 2n nodos.
Toda página distinta de la raíz tiene como mínimo n nodos. La raíz tiene como mínimo 1 nodo.
Toda página que no sea una hoja tiene m+1 páginas hijas, siendo m el número máximo de llaves.
Todas las páginas hoja están en el último nivel.
Además de estas características, los árboles B tienen que cumplir un cierto orden:

Los nodos dentro de una página mantienen un orden ascendente de izquierda a derecha.
Cada nodo es mayor que los nodos situados a su izquierda.
Cada nodo es mayor que los nodos situados a su derecha.
A continuación se muestran dos árboles, uno de ellos es un árbol B y otro no.

ESTRUCTURA DE UN ÁRBOL B: 

Cada hoja tiene 4 nodos. Este es un árbol B correcto, ya que cumple todas las reglas en cuanto a su estructura y al orden.

ESTRUCTURA DE UN ÁRBOL B INCORRECTO:

Nodo no raíz con menos de n nodos.
En cambio, este no es un árbol B, ya que a pesar de mantener el orden, hay una página (que no es la raíz) que tiene menos de n elementos (en este caso menos de 2 elementos). Esta página es la que contiene al elemento 10.

OPERACIONES:

las operaciones básicas que se pueden realizar en los árboles B:
*Búsqueda.
*Inserción.
*Retiro.

Ejemplo Inserción:

30, 60, 45, 8, 22, 35, 4, 28, 52, 33, 13, 39, 41, 43, 24, 25, 15.

Inserción: 30, 60, 45, 8:

Inserción: 22:

Inserción: 35, 4, 28, 52:

Inserción: 33:

Inserción: 13:

Inserción: 39:

Inserción: 41:

Inserción: 43:

Inserción: 24, 25:

Inserción: 15:

ELIMINACIÓN:

PROCESO DE ELIMINACIÓN:

* Buscar el elemento a eliminar.

* Si el elemento a borrar esta en el nodo hoja, se borra y termina (manteniendo reglas).

* Si el elemento no se encuentra en la hoja, se buscara el sustituto así:

           - El último elemento de la hoja más a la derecha del sub-árbol izquierdo del nodo actual.

             (el mayor de los menores).

           - El primer elemento de la hoja más a la izquierda del su-árbol derecho del nodo actual .

             (el menor de los mayores).  

Ejemplo:

Caso 1:

Retirar llaves 61 y 16:

no hay problema.

Caso 2:

Retirar llave 41:

En este caso se aplica la 2da regla (41=46 y 46=50)(llaves).

Para complementar estos temas:

  

ÁRBOL B+

Los árboles B+ constituyen otra mejora sobre los árboles B,pues conservan la propiedad de acceso aleatorio rápido y permiten además un recorrido secuencial rápido.En un árbol B+ todas las claves se encuentran en hojas,duplicándose en la raíz y nodos interiores aquellas que resulten necesarias para definir los caminos de búsqueda.Para facilitar el recorrido secuencial rápido las hojas se pueden vincular,obteniéndose ,de esta forma,una trayectoria secuencial para recorrer las claves del árbol.

Su principal característica es que todas las claves se encuentran en las hojas.Los árboles B+ ocupan algo más de espacio que los árboles B,pues existe duplicidad en algunas claves.En los árboles B+ las claves de las páginas raíz e interiores se utilizan únicamente como índices.

OPERACIONES:

INSERCIÓN EN UN ÁRBOL B+

Su diferencia con el proceso de inserción en árboles B consiste en que cuando se inserta una nueva clave en una página llena,ésta se divide también en otras dos,pero ahora la primera contendrá con m/2 claves y la segunda 1+m/2, y lo que subirá a la página antecesora será una copia de la clave central.


Vamos a complementar con este vídeo:

2. 
   

1. BÚSQUEDA:

1. la búsqueda de una llave Y se realiza de manera análoga a la búsqueda en un árbol binario de búsqueda. Se comienza buscando por el nodo raíz y se compara la llave y con las llaves ki que se encuentran en ese nodo. Si Y es igual a algún ki termina la búsqueda satisfactoriamente. 

1. INSERCIÓN:

1. Para realizar la inserción lo primero que debe hacerse es un proceso de proceso de búsqueda da por resultado que el elemento ya existe, no se realizara ninguna operación pues el árbol b no permite elementos repetidos. 

1. Ejemplo:

insertamos el 13:

     

4. 
   

1. ElIMINACIÓN:

1. La eliminación siempre debe realizarse en una hoja si después de realizar la búsqueda el nodo a borrar no estuviese en una hoja de la misma manera que se procede en una árbol binario de búsqueda el nodo a borrar se sustituiría por su antecesor o sucesor que si se debe estar en una hoja.

1. Ejemplo:

1. 
   

GRAFOS

¿QUÉ ES UN GRAFO?

Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de
aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es,
pues, un subconjunto {a, b}, con a, b ∈ V , a = b.

Los grafos se pueden clasificar en dos grupos:

Dirigidos y no Dirigidos, de los cuales enfocaremos e los términos más adelante.

CLASES DE GRAFOS:

A continuación enumeraremos algunas clases de grafos que aparecerán continuamente en
lo que sigue; conviene recordar sus nombres y características.
Diremos que un grafo es un Ln, un grafo lineal con n v´ertices (n ≥ 2) si tiene n vértices
(dos de grado 1 y el resto, si los hay, de grado 2) y es isomorfo a:

Otra clase de grafos muy relevante son los llamados grafos circulares con n vértices

(todos de grado 2), para n ≥ 3, que denotaremos por Cn:

Si un grafo con n vértices tiene todas las (n/2) posibles aristas, diremos que estamos ante el grafo completo con n vértices, Kn:

GRAFOS DIRIGIDOS: 

Un grafo dirigido es simétrico si para toda arista (x,y)perteneciente a A también aparece la arista (y,x)perteneciente a A;y es antisimétrico si dada una arista (x,y) perteneciente a A implica que (y,x) no pertenece a A.

En un grafo no dirigido el par de vértices que representa un arco no está ordenado

Tanto a las aristas como a los vértices les puede ser asociada información.A esta información se le llama etiqueta.Si la etiqueta que se asocia es un número se le llama peso,costo o longitud.Un grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o ponderado.

El número de elementos de V se denomina orden del grafo.Un grafo nulo es un grafo de orden cero.

Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya de x a y ((x,y)pertenece a A),a x se le denomina origen del arco y a y extremo del mismo.De igual forma se dirá que y es adyacente a x.En el caso de que el grafo sea no dirigido si x es adyacente(resp. incidente) a y entonces y también es adyacente (resp. incidente) a x.

Se dice que dos arcos son adyacentes cuando tienen un vértice común que es a la vez origen de uno y extremo del otro.

Se denomina camino (algunos autores lo llaman cadena si se trata de un grafo no dirigido)en un grafo dirigido a una sucesión de arcos adyacentes:

C={(v1,v2),(v2,v3),...,(vn-1,vn), para todo vi perteneciente a V}

Esos son solo algunos de las clases de grafos que existen.

LONGITUD DEL CAMINO:

Es el número de arcos que comprende y en el caso en el que el grafo sea ponderado se calculará como la suma de los pesos de las aristas que lo constituyen. 

CLASES DE GRAFOS

Un camino se dice simple cuando todos sus arcos son distintos y se dice elemental cuando no utiliza un mismo vértice dos veces.Por tanto todo camino elemental es simple y el recíproco no es cierto.

Un camino se dice Euleriano si es simple y además contiene a todos los arcos del grafo.

Un circuito(o ciclo para grafos no dirigidos)es un camino en el que coinciden los vértices inicial y final.Un circuito se dice simple cuando todos los arcos que lo forman son distintos y se dice elemental cuando todos los vértices por los que pasa son distintos.La longitud de un circuito es el número de arcos que lo componen.Un bucle es un circuito de longitud 1(están permitidos los arcos de la forma(i,i) y notemos que un grafo antisimétrico carecería de ellos).


Un circuito elemental que incluye a todos los vértices de un grafo lo llamaremos circuito Hamiltoniano.

Un grafo se denomina simple si no tiene bucles y no existe más que un camino para unir dos nodos.

Diremos que un grafo no dirigido es bipartido si el conjunto de sus vértices puede ser dividido en dos subconjuntos(disjuntos) de tal forma que cualquiera de las aristas que componen el grafo tiene cada uno de sus extremos en un subconjunto distinto.Un grafo no dirigido será bipartido si y sólo si no contiene ciclos con un número de aristas par.

Matriz de Adyacente:

Lista de Adyacente:

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta. 

EJEMPLO:

Links de profundización:

Teoría:

https://www.uam.es/personal_pdi/ciencias/gallardo/capitulo8a.pdf

http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/grafos.htm

Vídeo didáctico: 

 

Aplicaciones de los Grafos

Adjuntamos las presentaciones de estos temas, expuestos por estudiantes de Ingeniería de Sistemas, en donde explican de forma detallada y didáctica estos temas:

APLICACIONES DE LA TEORÍA DE GRAFOS:

GRAFOS PARTICULARES:

ALGORITMO DE FLOYD:

ALGORITMO DE KRUSKAL

ALGORITMO DE DIJKSTRA

Dijkstra expo from Estiven Parra

MATRIZ DISPERSA

Matriz dispersa-2 (1) from Estiven Parra

ALGORITMO DE WARSHALL

Exposicion from Estiven Parra

MÉTODO DE RUTA CRÍTICA