Sistemas

Solo disponible en BuenasTareas
  • Páginas : 8 (1933 palabras )
  • Descarga(s) : 0
  • Publicado : 5 de marzo de 2012
Leer documento completo
Vista previa del texto
Estructuras no lineales: Grafos
Las estructuras de datos no lineales se caracterizan por no existir una relación de adyacencia, entre sus elementos, es decir, un elemento puede estar relacionado con cero, uno o más elementos.
La estructura no lineal de datos más general es el grafo donde sus nodos pueden relacionarse de cualquier manera sin una relación de orden predefinida.Entre las
Entrelas múltiples aplicaciones que tienen estas estructuras podemos mencionar:
•Para modelar diversas situaciones tales como: sistemas de aeropuertos, flujo de tráfico, y responder a preguntas como: ¿Quétiempo es más corto?, ¿Cómoes más barato?, o ¿Quécamino es más corto?.
•Los grafos también son utilizados para realizar planificación de actividades, tareas del computador, planificar operaciones enlenguaje de máquinas para minimizar tiempo de ejecución.¿Quétarea debo hacer primero?.
•Para representar circuitos eléctricos,de aguas etc... , y preguntar, están todas las componentes conectadas.
Estructura de datos no lineales: árboles y grafos.
Diferenciar entre las estructuras árboles y grafos. Conocer la representación en memoria de un árbol y de un grafo. Árboles.
• Árboles binarios. •Árboles de expresión. • Construcción de árbol binario. • Recorrido de un árbol. • Aplicación de árboles binarios. • Árbol binario y de búsqueda. • Opresiones con árboles binarios de búsqueda.
Grafos.
Un grafo (específicamente, grafo simple no dirigido) es un par G D .V; E/ D .V .G/; V .E//, donde V es un conjunto finito no vacío de elementos llamados vértices y E es un conjunto de paresdesordenados de elementos distintos de V llamados aristas. Es decir, una arista e 2 E tiene la forma fu; vg, donde u; v 2 V y u 6D v.
La terminología en teoría de grafos varía muchísimo: prácticamente no hay dos textos que adopten la misma. En particular, los vértices de un grafo también reciben a veces el nombre de nodos, y las aristas arcos, ejes o líneas.

Estructuras de Datos No Lineales 
Árboles B:Los árboles B son estructuras no lineales que fueron introducidos por R. Bayer y E. McCreight en 1972, con el principal objetivo de mejorar el tiempo de acceso en estructuras de datos manejadas en memoria externa.
Los árboles B son una generalización de los árboles balanceados, con una estructura jerárquica que beneficia considerablemente la búsqueda de un elemento en específico, reduciendo elnúmero de nodos o archivos accesados.
En un árbol B se debe procurar:
1. Conservar la altura del árbol al mínimo, por lo que no deben existir subárboles vacíos al interior del árbol.
2.Que todos los nodos, excepto la raíz, tengan un mínimo número de llaves (quizás la mitad del máximo).
3.Que todas las hojas se mantengan al mismo nivel, garantizando así que las búsquedas se consigan conaproximadamente el mínimo número de accesos.
Luego, un árbol B de "orden d" se puede formalizar de la siguiente forma:
1. Cada página (nodo), exceptuando la raíz contiene entre d y 2d elementos.
2. Cada página (nodo), excepto la página raíz y las páginas hojas, tienen entre d+1 y 2d+1 descendientes. Se utiliza m para expresar el número de elementos pos cada página.
3. La página raízposee al menos dos descendientes.
4. Las páginas hojas están todas al mismo nivel.
La inserción en árboles B: Para insertar elementos en un árbol B se debe:
1. Determinar el máximo y mínimo número de elementos por nodo, de acuerdo al orden del árbol B:
Key mínimo = d
Key máximo = 2*d
2. Hacer una búsqueda en el árbol B del lugar donde debe insertarse la llave.
3. Toda inserciónen un árbol B tiene lugar siempre en una hoja del árbol. Si la hoja no está llena, la llave es añadida en ésa hoja.
4. Si el nodo hoja está lleno, entonces, éste se divide en dos (requiriendo la creación de un nuevo nodo) y la llave de valor medio se promueve como padre de los nodos. Si el nodo padre también está lleno, se repite el proceso, teniendo cuidado de mantener el orden de las...
tracking img