Introducción Estructuras De Datos

Investigación

ASIGNATURA: Estructura y organización de datos

PROFESOR:

ESTUDIANTE:

CARRERA: TICS

FECHA:

CALIFICACION:

COMENTARIOS:__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

1 - ¿Que es una estructura de datos?

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:

• Alta, adicionar un nuevo valor a la estructura.

• Baja, borrar un valor de la estructura.

• Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

Otras operaciones que se pueden realizar son:

• Ordenamiento, de los elementos pertenecientes a la estructura.

• Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

2 - ¿Cuáles son las estructuras de datos lineales?

Las estructuras lineales de datos se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios sub-elementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.

Una estructura lineal de datos os lista está conformada por ninguno, uno o varios elementos que tienen una relación dónde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último.

El valor contenido en los elementos pueden ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular.

Se clasifican en listas de acceso restringido y listas de acceso no restringido.

las listas de acceso restringido son las pilas, colas y dipolos.

• Pilas: En las pilas, las operaciones de acceso se realizan por un único extremo de la lista, al cual normalmente se denomina tope de la pila. Las operaciones básicas sobre una pila son: crearlo, destruirla, agregar un nuevo elemento, suprimir un elemento, consultar el elemento del tope verificar si está vacía

• Colas: En las colas, estas operaciones de acceso se realizan por ambos extremos de la lista llamados generalmente, inicio y fin de la cola. Operaciones básicas son: creación, destrucción, inserción al final de un nuevo elemento, consultar que elemento esta al inicio y cual al final, y verificar si la cola está vacía.

• Dipolos: Que son colas dobles, las operaciones se realizan también por ambos extremos de la lista, en este caso todas las operaciones se pueden hacer por ambos extremos, es decir se pueden insertar o eliminar elementos por el tope o por el fin, a diferencia de la COLA donde se inserta siempre por el fin y se elimina por el tope.

3 - ¿Cuáles son las estructuras de datos no lineales?

Es una estructura donde se tienen relaciones no lineales y no secuenciales, se pueden encontrar colecciones no ordenadas de elementos del mismo tipo, donde no hay repeticiones; entonces una estructura de datos no lineales, se caracteriza por no existir una relación de sus elementos, es decir que un elemento puede estar con cero, uno o más elementos.

Las estructuras no lineales de datos más generales son los árboles donde no existe ninguna relación de orden Predefinida.

Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos.

Los árboles son estructuras dinámicas no lineales, hasta ahora solo se han manejado estructuras estáticas y dinámicas lineales, es decir a cada elemento de la estructura solo le sigue otro, en el caso de los árboles a estos les puede seguir uno o más elementos, es decir que un elemento de la estructura puede apuntar a varios, además de esto son dinámicos ya que se pueden crear elementos que conformen el árbol cuando se requiera y en cualquier parte del programa.

Estructuras estáticas Estructuras dinámicas

Arreglos Listas

Pilas Árboles

Colas

Estructuras lineales Estructuras no lineales

Arreglos Árboles

Pilas Árboles

Colas

Listas

• Árbol de búsqueda perfectamente balanceado.

o Definición: Para todo nodo, la cantidad de nodos de su subárbol izquierdo difiere como máximo en 1 de la cantidad de nodos del subárbol derecho.

o En el peor caso, la búsqueda necesita O(log n).

o La inserción puede necesitar reorganizar todo el árbol, O(n).

• Árbol balanceado ó AVL (Adelson-Velskii y Landis).

o Es un árbol binario de búsqueda, con una condición de balanceo más débil que hace que no sea tan costoso el proceso de balancear un árbol.

o Definición: Para todo nodo, la altura de sus subárboles difiere como máximo en 1. (Supondremos que la altura del árbol vacío es -1.)

• Árboles Binarios

Un árbol binario, es aquel que tiene como máximo 2 descendientes, es decir cada uno de los nodos del árbol tiene un máximo de 2 hijos; además si es binario de búsqueda se define de manera formal como: “Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T serán menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos del subárbol derecho de T deben ser mayores o iguales al valor del nodo T ”.

Por lo mismo se pueden realizar las operaciones de búsqueda, inserción y eliminación, de manera más eficiente en este tipo de árbol.

ARBOLES BALANCEADOS AVL

La estructura

...