Bloque III. Tema 8. Estructuras de datos. Tablas, listas y árboles. Algoritmos: ordenación, búsqueda. Grafos. Organizaciones de ficheros

Índice de contenido

Bloque III. Tema 8. Estructuras de datos. Tablas, listas y árboles. Algoritmos: ordenación, búsqueda. Grafos. Organizaciones de ficheros        1

Tablas        2

Listas        2

Árboles        2

Árboles Binarios        2

Árbol Binario de búsqueda        3

Árboles AVL        3

Árboles Rojo-Negro        3

Árbol AA        3

Árboles Multicamino        3

Árboles B        3

Árboles B+        3

Árboles B*        4

Algoritmos de ordenación        4

Método de intercambio o burbuja        4

Método de inserción        4

Método de selección        4

Método de casilleros o cubos (Bucket Sort)        4

Método de Mezcla (Merge Sort)        4

Método de montículos (Heap Sort)        5

Quicksort        5

Algoritmos de búsqueda        5

Búsqueda secuencial        5

Búsqueda binaria        5

Grafos        5

Búsqueda y recorrido en/de grafos        6

 

Recursos wikipedia y un libro de estructuras de datos de Joyanes:

Tablas

Listas

Listas Hash

Una lista de hashes de los bloques de datos en un fichero o conjunto de ficheros. Se usan para múltiples propósitos, como búsqueda rápida en tablas (tablas hash) y bases de datos distribuidas (tablas hash distribuidas).

Un uso actual es en las redes P2P, donde hay una lista de trozos del archivo que se está descargando. Se usa para asegurarse de que los fragmentos recibidos están sin dañar e inalterados.

Árboles

Definiciones:

Árboles Binarios

Un árbol binario es un conjunto finito de cero o más nodos que:

Recorridos de un árbol binario:

Árbol Binario de búsqueda

Los valores del árbol deben ser tales que permitan una relación de orden. En cualquier nodo todos los valores del subárbol izquierdo son menores o iguales que el valor del nodo y todos los valores del subárbol derecho son mayores que los valores del nodo.

Existe la idea de un árbol binario de búsqueda auto-balanceable para corregir el problema de que un o normal pueda escorar hacia un lado o hacia otro. Ésto se realizar con operaciones especiales como rotación de árboles en momentos determinados. Dos tipos de árboles que implementan estas ideas son los AVL, los Rojo-Negro y los árboles AA.

Árboles AVL

Son árboles binarios de búsqueda auto-balanceables que 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. Gracias a ésto la complejidad de la búsqueda se mantiene estabilizada en O(log n).

Árboles Rojo-Negro

Es un árbol binario de búsqueda equilibrado. Las hojas no son relevantes y no contienen datos. Un único nodo, el nodo centinela, hace de nodo hoja para todas las ramas.

Árbol AA

Es otro tipo de árbol binario de búsqueda auto-balanceable. Es una variación del Rojo-Negro.

Árboles Multicamino

Ya no son árboles binarios y en general los nodos y el árbol tienen grado g. Se refiere el multicamino simplemente a que cada nodo tiene un número arbitrario de nodos. Una implementación típica es tener una lista de hijos por cada nodo.

Árboles B

Se encuentran con facilidad en las bases de datos. Hay un tipo de índice de MySQL que es Btree. También se encuentran en implementaciones de sistemas de archivos.

La idea es que pueden tener cualquier número de subárboles, pero dentro de un rango predefinido y cuando se supera el rango, los árboles se parten. Cuando bajan del límite inferior del rango, se juntan. Por ejemplo uno comúnmente usado es un árbol B con rango de 2 a 3, cada nodo puede tener de dos a tres hijos y se le conoce como árbol 2-3. Un árbol B se encuentra balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura.

Árboles B+

Es una variación del árbol-B en la que toda la información se guarda en las hojas. Los nodos internos solo contienen claves y punteros.

Árboles B*

Es una variante del árbol-B usada en los sistemas de ficheros Reiser4 y HFS.

Algoritmos de ordenación

Podemos distinguir la ordenación de arrays y la ordenación de archivos. También se denominan respectivamente ordenación interna ya que se almacena en la memoria interna y ordenación externa por usar un dispositivo de almacenamiento externo.

Método de intercambio o burbuja

Comparar pares de elementos adyacentes entre sí e ir intercambiándolos hasta que queden ordenados. El elemento más pesado va flotando como una burbuja, en cada iteración, porque hacen falta varias. En cada una de ellas el elemento más pesado que quede por colocar quedará en la última posición, en la penúltima, etc. Hacen falta:

Método de inserción

O método de la baraja. Consiste en insertar un elemento en el vector en una parte ya ordenada de éste y comenzar de nuevo con los elementos restantes. El método se basa en comparaciones y desplazamientos sucesivos. Para mejorarlo se recurre a la búsqueda binaria en la parte ordenada en lugar de la búsqueda secuencial.

Método de selección

Es un algoritmo de ordenación inestable. Los algoritmos inestables pueden cambiar el orden relativo de dos elementos que tengan la misma clave de ordenación, mientras que los estables no lo hacen.

Su funcionamiento es el siguiente:

  1. Buscar el mínimo elemento de la lista
  2. Intercambiarlo con el primero
  3. Buscar el mínimo del resto de la lista
  4. Intercambiarlo con el segundo, etc.

Método de casilleros o cubos (Bucket Sort)

Se trata de reducir previamente el número de elementos a ordenar, pasándolos a cubos, que son contenedores de elementos que cumplen algún criterio. Los criterios son excluyentes para que ninguno tenga la posibilidad de ir a dos cubos. Y luego en cada cubo se aplica otro algoritmo de ordenación.

Método de Mezcla (Merge Sort)

Se lo considera de ordenamiento externo, dedicado a grandes cantidades de información como el almacenamiento persistente. Está basado en la técnica de divide y vencerás. Funciona de la siguiente manera:

  1. Dividir una lista desordenada en dos trozos de aproximadamente la mitad del tamaño.
  2. Ordenar cada lista, recursivamente
  3. Mezclar las dos sublistas

Método de montículos (Heap Sort)

Un montículo es una estructura de datos de tipo árbol con información perteneciente a un conjunto ordenado. Puede ser máximo o mínimo, de manera que o bien se sabe que el padre tiene siempre un valor mayor que los hijos o se sabe que el padre tiene un valor menor que los hijos.

Así, el algoritmo consiste en ordenar todos los elementos en un montículo y luego ir extrayéndolos en orden.

Quicksort

Pasos:

  1. Elegir un elemento de la lista a ordenar, al que llamaremos pivote.
  2. Posicionar el resto de elementos de la lista, de manera que todos los elementos menores que él queden a un lado y los mayores al otro.
  3. Repetir este proceso para cada sublista.

La principal optimización por tanto se centra en la elección del pivote.

Algoritmos de búsqueda

Búsqueda secuencial

De to la vida.

Búsqueda binaria

Si sabemos que el vector está previamente ordenado. Se compara el valor a buscar, con una posición, normalmente en el centro, y nos centramos en el trozo en el que estará el elemento.

Grafos

Si se eliminan las limitaciones de que un nodo puede apuntar a dos nodos -o a un rango- y cada uno puede estar apuntado por uno solo, nos encontramos simple y llanamente con un grafo. Terminología:

Búsqueda y recorrido en/de grafos

Estos algoritmos pertenecen a la categoría de los que buscan sub-estructuras específicas dentro de otras estructuras. Es una extensión muy estudiada de este problema la que se aplica a los grafos, con multitud de algoritmos.

El problema del recorrido de grafos (Graph Traversal) es el de visitar todos los nodos del grafo de una manera particular. El recorrido de árboles es un caso especial dentro del recorrido de grafos. Se clasifican en Primero-en-Profunidad y Primero-en-Anchura. El primero visita los hijos primero, antes que los hermanos. El segundo visita primero los hermanos y luego los hijos.

Algunos algoritmos: