Estructura de datos (Cairo y Guardati)

Capítulo 1

Los tipos de datos simples ocupan un solo lugar de memoria. Por otra parte, los tipos de datos
estructurados (arreglos y registros) tiene varios componentes y el identificador de variable
hace referencia a un grupo de casillas de memoria.

Capítulo 3 – Pilas y Colas

Una pila representa una estructura lineal de datos, los elementos se eliminan en el orden
inverso al que se insertaron. Estructura LIFO el último en entrar es el primero en salir. Los
componentes ocupan lugares sucesivos, cada uno tiene un predecesor y un sucesor, excepto el
primero y el último. Se puede acceder por un extremo al que se le llama tope.

La pila implementada con arreglos se debe reservar la memoria, esto genera un problema que
si se desean cargar más datos se puede producir un desbordamiento y si se reserva una gran
cantidad de memoria el uso de esta es ineficiente. Otro problema es el subdesbordamiento
que se intenta eliminar un elemento de una pila vacía.

Las pilas son usadas para:

- Llamadas a subprogramas
- Recursividad
- Tratamiento de expresiones aritméticas
- Ordenación

Llamadas a subprogramas: se usan pilas para guardar los estados de las variables del
programa, así como también las instrucciones pendientes al momento de la llamada.

Tratamiento de expresiones aritméticas: los algoritmos usados para pasar de notación infija a
postfija o prefija se utilizan pilas.

3.3 Colas

Una cola es una estructura lineal de datos, donde se insertan elementos por un extremo y se
eliminan en el otro en el mismo orden de entrada, por eso se las conoce como FIFO primero en
entrar, primero en salir. Es necesario declarar dos variables auxiliares, una para la posición el
primer elemento de la cola, Frente y otra para la posición el último llamado Final. Las
inserciones se harán por el final de la cola y las eliminaciones por el frente.

Colas circulares

Es una estructura de datos lineal en la cual el siguiente elemento del último en realidad es el
primero. De esta manera se usa de manera mas eficiente la memoria.

Doble cola

Una doble cola o bicola es una generalización de la estructura de datos cola, donde se puede
insertar o eliminar de cualquiera de los dos extremos.

La aplicación de colas es por ejemplo cuando se envía a imprimir. Otro caso es en el uso de
recursos compartidos, estos se asignan en el orden en que fueron introducidos a la cola.

Capítulo 4 – Recursión
La recursión se puede presentar de dos maneras:

- Directa: el programa o subprograma se llama a sí mismo.

- Indirecta: el subprograma llama a otro subprograma, y este en algún momento llama al

primero.

En toda definición recursiva de un problema debe haber un paso básico y un paso recursivo. El
básico se usa como condición de parada o fin de la recursión y el segundo paso propicia la
recursividad.

Las estructuras de datos dinámicos y no lineales árboles es inherente trabajarlos con

recursividad.

Capítulo 5- Listas

Los arreglos y registros son estructuras de datos estáticas ya que durante la compilación se les
asigna un espacio de memoria, y este permanece inalterable durante la ejecución.

Las listas son lineales y dinámicas, lineales porque después de un elemento solo puede seguir
otro elemento y dinámica porque se puede usar la memoria de manera flexible sin necesidad
de reservar memoria con antelación.

La ventaja es que se puede usar espacios de memoria cuando sean necesarios y se liberen
cuando están en desuso.

Listas simplemente ligadas

Las listas ligadas son una colección de elementos llamados nodos, enlazados mediante
punteros, de esta manera no es necesario almacenar los nodos en espacios contiguos.

El primer apuntador de la lista es muy importante porque si se pierde, perdemos toda la

información de la lista, si fuera lista vacía apuntaría a nil, al igual que el último elemento que
apunta a nil.

La búsqueda es las listas simplemente ligadas es fácil pero ineficiente ya que se hace de
manera secuencial.

Listas circulares

Estas tienen la característica que el último elemento de la lista apunta al primero, en lugar de
apuntar a vacío o nil. Se necesita considerar algún criterio para detectar cuando se han visitado
todos los nodos, una solución es el uso de un nodo extra, llamado nodo cabecera.

Listas doblemente ligadas

Es una colección de nodos en la cual cada uno de ellos tiene dos apuntadores, por estos se
podrá avanzar o retroceder en la lista.

Listas doblemente ligadas circulares

El campo anterior del primer nodo apunta al último nodo y el campo siguiente de este último
nodo apunta al primer nodo.

Dos de las aplicaciones más importantes de las listas son representación de polinomios y
resolución de colisiones (hash).
Capítulo 6 – Árboles

En los árboles a los nodos le pueden preceder o suceder varios elementos. Son las estructuras
no lineales y dinámicas más importantes de la computación. Dinámicas porque pueden
cambiar de forma y de tamaño durante la ejecución, no lineales ya que cada nodo puede tener
más de un sucesor. Los árboles balanceados o AVL son los más eficientes para trabajar con la
memoria principal (interna) del procesador, mientras que los árboles B y B+ los más eficientes
para memoria externa o secundaria.

Los árboles son estructuras recursivas, ya que cada subárbol es a su vez un árbol.

Características y propiedades de los árboles

- Todo árbol que no es vacío tiene un único nodo raíz.

- Si el nodo X es descendiente directo de Y, se dice que X es hijo de Y.
- Si un nodo X es antecesor directo de Y, se dice que X es padre de Y.
- Se dice que todos los nodos descendientes directos de un mismo nodo (padre), son
hermanos.
- Todo nodo que no tiene ramificaciones o hijos, se dice que es terminal u hoja.
- Todo nodo que no es raíz ni hoja se conoce con el nombre de interior.
- Grado es el número de descendientes directos de un determinado nodo.
- Grado del árbol es el máximo grado de todos los nodos del árbol.
- Nivel es el número de arcos que deben ser recorridos para llegar a un determinado
nodo.
- Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
- Longitud de camino del nodo es el número de arcos que se deben recorrer para llegar
desde la raíz hasta el nodo determinado.
- La longitud de camino interno del árbol es la suma de las longitudes de camino de
todos los nodos del árbol.

El árbol extendido es aquel en el que el número de hijos de cada nodo es igual al grado del
árbol. Si alguno de los nodos del árbol no cumple con la condición se incorporan nodos
especiales tantos como se requieran para cumplirla.

Dado este tipo de árboles, se puede conseguir la longitud de camino externo de un árbol
que es la suma de las longitudes de camino de todos los nodos especiales del árbol.

Árboles Binarios

Un árbol ordenado es aquel que la distribución de las ramas sigue un cierto orden. Los
ordenados de grado 2 son conocidos como árboles binarios.

En estos árboles cada subárbol puede tener como máximo dos subárboles, llamados hijo
izquierdo e hijo derecho según su ubicación respecto de la raíz.

Los árboles ordenados de grado mayor a dos se conocen con el nombre de árboles
multicaminos.

Dos árboles binarios son distintos si su estructura (distribución de arcos) es diferente.

Dos árboles son similares si su estructura es igual, pero la información de sus nodos es
distinta.

Los árboles equivalentes tienen igual estructura e información.

 Un árbol completo o lleno es aquel que todos los nodos, excepto en el último nivel, tienen
los dos hijos.

Representación de árboles generales a binarios

1) Enlazar los hijos de cada nodo de forma horizontal (los hermanos).

2) Relacionar de forma vertical en nodo padre con el hijo que se encuentra más a la
izquierda. Se debe eliminar el vínculo de ese padre con el resto de los hijos.
3) Rotar el diagrama a 45° a la izquierda y así obtendrá el árbol binario.

Se debe cumplir:

- Si la rama derecha de cada nodo, excepto el nodo raíz, es distinta de vacío se

encuentra un nodo que era hermano de este en el árbol general.
- En la rama izquierda de cada nodo, si esta es distinta de vacío, se encuentra un nodo
que era hijo de este en árbol general.

Representación de árboles binarios en memoria

Los nodos de un árbol binario se representan como registros con tres campos, uno para la
información del nodo y los otros dos para apuntar a los subárboles.

Recorrer un árbol es visitar todos sus nodos de forma ordenada. Existen tres formas de
recorrido, que son recursivas por naturaleza:

- Recorrido en preorden: visita la raíz, recorre hijo izquierdo, recorre hijo derecho
- Recorrido en inorden: recorre hijo izquierdo, visita la raíz, recorre hijo derecho
- Recorrido posorden: recorre hijo izquierdo, recorre hijo derecho, visita raíz

Árboles binarios de búsqueda

Es un tipo especial de árboles en los que los nodos mantienen un cierto orden. Todos los
valores almacenados en el subárbol sean menores o iguales a la información guardada en el
nodo padre. De igual manera los valores del subárbol derecho deben ser mayores o iguales al
del nodo padre.

Operaciones

La operación de búsqueda en este tipo de árboles es mas eficiente que en otros, ya que al
comprar el valor con el que posee el nodo, si no es igual, se deberá seguir buscando solo por
una rama del árbol.

Para la inserción de nuevos nodos en los árboles binarios de búsqueda se debe comparar la
clave a insertar con la raíz, si es mayor debe seguir con la rama derecha si es menor por la
izquierda; se deberá continuar con ese paso hasta que se cumpla:

- Que el subárbol izquierdo o derecho es igual a vacío y se deberá insertar el nodo en el

lugar que corresponde.
- La clave que se quiere insertar esta en el nodo analizado, no se lleva a cabo la insertar
sino se permiten claves repetidas o se insertara según lo dispuesto con anterioridad.

La eliminación es más complicada ya que no se debe violar los principios que definen a un
árbol binario de búsqueda. Se debe distinguir los siguientes casos:
 - Si el elemento a eliminar es terminal se suprime redefiniendo el puntero de su
predecesor.
- Si el elemento a eliminar tiene un descendiente, entonces tiene que sustituirse por ese
descendiente.
- Si el elemento a eliminar tiene dos hijos, entonces se tiene que sustituir por el nodo
más a la izquierda en el subárbol derecho o por el nodo más a la derecha del subárbol
izquierdo.

Árboles balanceados o AVL

Para mantener la eficiencia de los árboles antes mencionados, se hacen reacomodos o

balanceos, después de inserciones y eliminaciones dando lugar a los árboles balanceados.

Formalmente se los define como un árbol binario de búsqueda, en el cual se debe cumplir la
siguiente condición: para todo nodo T del árbol, la altura de los subárboles izquierdo y derecho
no debe diferir en más de una unidad.

|HRI - HRD | <= 1 donde HRI es la altura de la rama izquierda y HRD de la derecha.

Para determinar si un árbol esta balanceado o no, se debe calcular el factor de equilibrio de un
nodo que se define como la altura del subárbol derecho menos la altura del subárbol izquierdo

FE= HRD - HRI

Los valores que puede tomar FE son -1, 0, 1. Si FE llegara a tomar los valores -2 o 2, entonces
debería reconstruirse el árbol.

En proceso de inserción en un árbol balanceado primero se debe seguir el camino de búsqueda

del árbol, hasta encontrar el lugar para insertar el elemento. Luego, se calcula el FE que
obviamente será 0, regresamos por el camino de búsqueda calculando los FE de todos los
nodos, si alguno viola el criterio de equilibrio se deberá reestructurar el árbol. El proceso
termina cuando se llega a la raíz o cuando se reestructura el árbol.

Reestructurar el árbol es rotar los nodos para que se cumpla con el equilibrio. La rotación
puede ser simple o compuesta. En la simple se involucran dos nodos y en la segunda se afecta
a tres. La simple puede realizarse por las ramas derechas (DD) o por las izquierdas (II). La
compuesta se puede realizar por las ramas derecha e izquierda (DI) o izquierda y derecha (ID).

En la operación de eliminación de los árboles AVL se deben distinguir los siguientes pasos:

- Si el elemento a eliminar es terminal simplemente se suprime.

- Si el elemento tiene un solo descendente entonces se tiene que sustituir por ese
descendente.
- Si el elemento tiene dos descendentes entonces se tiene que sustituir por el nodo que
se encuentra mas a la izquierda en la rama derecha o mas a la derecha en el subárbol
izquierdo.

Se regresa por el camino de búsqueda calculando el FE de los nodos visitados. Si en algunos de

los nodos se viola el criterio de equilibrio se debe reestructurar el árbol, el proceso termina
cuando se llega a la raíz del árbol.

Árboles multicaminos
Son árboles organizados en páginas (nodos) con varios elementos, almacenados en memoria
secundaria, hace que se disminuya el acceso a disco siendo eficiente trabajando con
volúmenes importantes de información.

Árboles B

En estos, un grupo de nodos recibe el nombre de página. En cada página se almacena

información de los nodos que la forman y se identifica por medio de una clave o llave.

Cada página de un árbol B de orden d contiene 2d claves como máximo y d como mínimo.
Cada página de un árbol B de orden d tiene 2d+1 hijos como máximo y d+1 hijos como mínimo,
excepto la raíz que puede contener como mínimo un dato y como consiguiente 2 hijos.

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

1) Cada página, excepto la raíz, contiene entre d y 2d elementos, siendo d el grado del
árbol.
2) La raíz puede almacenar entre 1 y 2d elementos.
3) Cada página, excepto raíz y hojas, tiene entre d+1 y 2d+1 hijos. Se utilizará m para
expresar el número de elementos por página.
4) La página raíz tiene al menos dos hijos.
5) Las páginas hojas están todas al mismo nivel.

La búsqueda es similar a los árboles binarios de búsqueda, se utiliza NIL para indicar que la
página está vacía.

Se debe tener en memoria la pagina sobre la cual se quiere trabajar, se debe verificar si la
clave buscada se encuentra en dicha página. Si m es pequeña se usa búsqueda secuencial, sino
binaria.

Todas las hojas de estos árboles están al mismo nivel y por lo tanto cualquier camino desde la
raíz hasta alguna de las hojas tienen la misma longitud. Además, crecen de abajo hacia arriba,
es decir, desde las hijas hacia la raíz. Los pasos de la inserción son los siguientes:

1) Localizar la página donde se debe insertar la clave.

2) si (m < 2d) el número de elementos de la página es menor a 2d entonces la clave se inserta

en el lugar que corresponde, sino se divide la página en 2 y se distribuyen las m+1 claves
equitativamente entre las mismas, la clave del medio sube a la página antecesora. Este
proceso puede repetirse hasta llegar a la raíz, en dicho caso la altura del árbol se incrementa
una unidad.

En la operación de eliminación se deben distinguir los siguientes casos:

1) Si la clave a eliminar se encuentra en una pagina hoja solo se suprime. Se verifica que
el número de elementos en la página sea válido (m>=d), sino es, se debe bajar la clave
adyacente de la página antecesora y sustituir esta clave por la que esta mas a la
derecha en el subárbol izquierdo o por la que este mas a la izquierda en el subárbol
derecho. Si esto no es posible, por las m de las páginas involucradas, se deben fusionar
las páginas que son descendientes directas de la clave que se baja.
2) Si la clave a eliminar no se encuentra en una pagina hoja entonces se debe sustituir
por la clave que se encuentra mas a la izquierda en el subárbol derecho o por la más a
la derecha del subárbol izquierdo. Se verifica que el número de elementos en la página
 sea válido (m>=d), si es se borra, sino se debe bajar la clave adyacente de la página
antecesora y fusionar las paginas que son descendientes directas de dicha clave.

El proceso de fusión de paginas se puede propagar incluso hasta la raíz, en cuyo caso la altura
del árbol disminuye una unidad.

Árboles B+

Estas estructuras son muy utilizadas para archivos indexados. La información se encuentra en
las hojas, mientras que en la raíz y nodos interiores se almacenan claves que se usan de índice.

Formalmente se define a los árboles B+ de la siguiente manera:

- Cada página, excepto la raíz, contiene m elementos, donde m es un valor entre d y 2d.
- La raíz contiene de 1 a 2d elementos.
- Cada página, excepto la raíz tiene entre d+1 y 2d+1 hijos.
- La página raíz tiene al menos 2 hijos.
- Las páginas hojas están todas al mismo nivel.
- Toda la información se encuentra en las páginas hojas.
- Las claves de la raíz e interiores se usan como índices.

La búsqueda es similar a los B, solo que si al buscar una clave se encuentra en la raíz o página
interior no se debe detener el proceso ya que dichas páginas funcionan como índices. La
búsqueda debe continuar por la rama derecha de dicha clave.

La inserción es similar a los árboles B, la dificultad esta en querer insertar una clave en una
página que se encuentra llena (m =2d), se debe dividir la pagina en 2 distribuyendo las d
primeras claves en la página izquierda y las restantes en la derecha. Una copia de la clave del
medio sube a la página antecesora, puede que esta se vuelva a desbordar y se repite el
proceso anterior, esto se puede propagar hasta la raíz y el árbol se incrementa una unidad.

La eliminación es mas sencilla que en los árboles B, ya que las claves a eliminar siempre se
encuentran en las hojas. Se deben distinguir los siguientes pasos:

1) Si al eliminar una clave m >= d, entonces se termina el borrado. Las claves de raíz e
internas no se modifican.
2) Si al eliminar una clave m< d, entonces se debe realizar una redistribución de claves,
tanto en el índice como en las hojas. Cuando se cambia la estructura del árbol se
quitan aquellas claves que quedaron en los nodos interiores luego de haber borrado su
correspondiente información en las hojas.

Puede suceder que al eliminar una clave y realizar la redistribución, la altura del árbol
disminuya una unidad.

Métodos de ordenación

Ordenar significa permutar elementos de tal manera que queden de acuerdo con una
distribución preestablecida.

Los métodos de ordenación interna a su vez se pueden clasificar en dos tipos:

- Métodos directos (n2)

- Métodos logarítmicos (n*log n)
Los métodos directos son sencillos de implementar, aunque son ineficientes cuando n es de
tamaño mediano o grande.

Los métodos logarítmicos son más complejos sin embargo son más eficientes ya que requieren
menos comparaciones y movimientos para ordenar los elementos.

La eficiencia se da por el tiempo de ejecución del algoritmo y depende fundamentalmente del

número de comparaciones y movimientos que se realizan. Por lo que cuando n es pequeño se
utilizarán métodos directos y cuando n es mediano o grande se utilizarán métodos
logarítmicos.

Los métodos directos más conocidos son:

- Ordenación por intercambio

- Ordenación por inserción
- Ordenación por selección

El método por intercambio directo o conocido como burbuja es el más conocido, pero quizás
el más ineficiente. Lleva los elementos más pequeños hacia la parte izquierda del arreglo o
traslada los elementos más grandes hacia la parte derecha, el algoritmo consiste en comparar
pares de elementos adyacentes e intercambiarlos entre sí hasta que se encuentren todos
ordenados. Se realizan (n-1) pasadas transportando en cada una de ellas el menor o mayor
elemento, según el caso, a su posición ideal. Al final de todas las pasadas los elementos del
arreglo quedan ordenados. El tiempo de ejecución es proporcional a n 2, O(n2), donde n es el
número de elementos.

El método de intercambio directo con señal es similar al anterior, con la idea de utilizar una
marca o señal para indicar que no se ha producido ningún intercambio en la pasada. Es decir,
que si se comprueba que el arreglo está totalmente ordenado después de la pasada terminar
la ejecución.

El método de la sacudida es una optimización del intercambio directo. la idea de este

algoritmo consiste en mezclar las dos formas de realizar el método burbuja. Cada pasada tiene
dos etapas, en la primera, de derecha a izquierda, se trasladan los elementos más pequeños
hacia la izquierda y se almacena en una variable la posición del último el elemento
intercambiado. En la segunda pasada, de izquierda a derecha, se trasladan los elementos más
grandes hacia la derecha, almacenando en otra variable la posición del último elemento
intercambiado. Las sucesivas pasadas trabajan entre las posiciones almacenadas en las
variables auxiliares. El algoritmo termina cuando en una etapa no se producen intercambios o
bien, cuando el contenido de la variable que guarda el extremo izquierdo es mayor que el
contenido de la variable que almacena el extremo derecho.

La ordenación por inserción directa tiene como idea insertar un elemento del arreglo en su
parte izquierda, que ya se encuentra ordenada. este proceso se repite desde el segundo hasta
el enésimo elemento.

El método por inserción binaria es una mejora del anterior. consiste en realizar una búsqueda
binaria el lugar de una búsqueda secuencial, para insertar un elemento en la parte izquierda
que se encuentra ordenada. el proceso al igual que en el método anterior se repite desde el
segundo elemento hasta el enésimo.
El método de ordenación por selección directa es más eficiente que los antes mencionados. El
algoritmo consiste en buscar el menor elemento del arreglo y colocarlo en la primera posición.
Luego buscar el segundo más pequeño del arreglo y colocarlo en la segunda posición. El
proceso continúa hasta que el arreglo esté ordenado.

El método de Shell es una versión mejorada de la inserción directa, es también conocido como
inserción con incrementos decrecientes. Shell propone que las comparaciones entre
elementos se efectúen con saltos de mayor tamaño, pero con incrementos decrecientes; así,
los elementos quedarán ordenados en el arreglo más rápidamente.

El método ordenación quicksort es actualmente el más eficiente y veloz de los métodos de

ordenación interna, también conocido como método rápido y de ordenación por partición. La
idea de este algoritmo consiste en lo siguiente:

- Se toma un elemento X de una posición cualquiera del arreglo.

- Se trata de ubicar X en la posición correcta del arreglo, de tal forma que los que están
a la izquierda sean menores o iguales que X y los de la derecha sean mayores o iguales.
- Se repiten los pasos anteriores, pero ahora para los conjuntos de datos que se
encuentran a la izquierda y a la derecha de la posición de X en el arreglo.
- El proceso termina cuando todos los datos se encuentran en su posición correcta en el
arreglo.

El método de ordenación heapsort se conoce como montículo. Es el más eficiente de los

métodos de ordenación que trabajan con árboles. La idea central de este algoritmo se basa en
dos operaciones:

1) construir un montículo
2) eliminar la raíz del montículo en forma repetida

Es importante señalar que un montículo se define cómo: para todo nodo del árbol se debe
cumplir que su valor sea mayor o igual que el valor de cualquiera de sus hijos.

Ordenación externa

La intercalación de archivos donde dos o más archivos ordenados de acuerdo con un

determinado campo clave, en un solo archivo.

La ordenación de archivos se entiende por la ordenación o clasificación de estos, ascendente o

descendentemente, de acuerdo con un determinado campo al que se denomina campo clave.

El algoritmo de ordenación por mezcla directa consiste en la realización sucesiva de una

partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor en la
primera pasada la partición es de longitud 1 (elemento por medio) y la fusión o mezcla
produce secuencias ordenadas de longitud 2. En la segunda pasada la partición es de longitud
dos y la fusión o mezcla produce secuencias ordenadas de longitud 4. El proceso se repite
hasta que la longitud de la secuencia para la partición sea: Parte entera ((n+1) /2). Donde n es
el número de elementos del archivo original.

El método por mezcla equilibrada conocido como mezcla natural, consiste en realizar
particiones tomando secuencias ordenadas de máxima longitud, en lugar de secuencias de
tamaño fijo. Luego se realiza la fusión de las secuencias ordenadas en forma alternada sobre
dos archivos. Aplicando estas soluciones de forma repetida se logrará que el archivo quede
ordenado. Para la realización de este proceso se necesitan cuatro archivos, el original y 3
auxiliares. El proceso termina cuando la realización de la función partición el segundo archivo
quede vacío.

Pagina 402

hash