Estrategias de Búsqueda, Ordenación y Estructuras de Árboles en Programación

Algoritmos de Búsqueda y Ordenación

Algoritmos de Búsqueda

Existen principalmente 2 tipos:

• Lineal: Se recogen todos los datos y se hallan las posiciones en la (o las) que se encuentra el elemento. Su eficiencia es $O(n)$ y se implementa mediante un bucle for.
• Binario: Los elementos tienen que estar ordenados por algún criterio. Se compara el elemento con el central y, según sea mayor o menor, se detiene la búsqueda o se repite la operación en la sublista izquierda o derecha. Su eficiencia se reduce a la mitad: $O(\log n)$.

Algoritmos de Ordenación

Se dividen en 2 tipos:

• Interna: Orden de datos que se encuentran en la memoria del programa. Puede ser directa o algorítmica.
• Externa:
  • Fase 1 (Búsqueda): Se busca el registro.
  • Fusión: Reúne varios archivos en uno solo intercalando los registros.
  • Ordenación: Clasificación de registros en memoria auxiliar en función de un campo.

Métodos Especificos de Ordenación

Selección

Alta eficiencia en tiempo de ejecución $O(n^2)$. Es muy fácil de codificar y apropiado para pequeños arrays. Dado un array A de tamaño N, por cada $i$ de $0$ a $N-2$, se intercambia $A[i]$ con el elemento mínimo del subtabla $A[i+1], \dots, A[N]$.

Inserción

Tiempo de ejecución $O(n^2)$. Cuanto más ordenado esté, más rápido será ($O(n)$). Se suele usar semi-ordenando la entrada con otro algoritmo más rápido. Dado un array A de tamaño N, se recorre todo A desde la posición 2 hasta $p=N$. Para cada $p$, se ubica correctamente el elemento $A[p]$ entre los elementos anteriores.

Burbuja

Menor eficiencia. Consiste en comparar elementos adyacentes del vector e intercambiarlos si están desordenados. Se van realizando pasadas $(n-1)$.

Shell

Intercambia elementos distantes y deshace más de una inversión en cada intercambio, resultando más veloz. Es adecuado para ordenar cadenas grandes.

Heapsort

Usa propiedades de montículos binarios. Un montículo máximo es un árbol binario cuyos elementos están ordenados de forma que, para cada subárbol, la raíz es mayor que sus hijos (el montículo mínimo funciona al revés). El orden de ejecución es $O(n \cdot \log(n))$. Consiste en meter todos los elementos del array en un montículo máximo y luego ejecutar eliminar_max() N veces.

Mergesort

Es un algoritmo recursivo con un número mínimo de comparaciones. Su tiempo de ejecución es $O(N \log(N))$. Sus desventajas son que trabaja sobre un array auxiliar (requiriendo uso extra de memoria y procesamiento). Sigue la estrategia de divide y vencerás: en cada recursión se toma el array desordenado, se divide en dos mitades, se aplica recursión a cada una y se intercalan.

Quicksort

Otra resolución basada en divide y vencerás. Se divide la lista en dos partes separadas por un pivote, de manera que los elementos de una sublista sean menores que los de la otra. Es el más rápido, con un tiempo de ejecución medio de $O(N \log(N))$ y un peor caso de $O(N^2)$. Su funcionamiento consiste en:

1. Elegir un elemento pivote.
2. Particionar el array en tres partes ($A_1$ elementos menores que el pivote, $A_2$ el pivote, y $A_3$ elementos mayores).
3. Aplicar recursión sobre $A_1$ y $A_3$.

Mezcla Directa

Un método simple que consiste en separar los registros individuales del archivo original en dos archivos auxiliares, los cuales se mezclan formando pares ordenados. Posteriormente, se separan los pares del archivo original en dos nuevos archivos y se mezclan formando cuádruplos y octuplos ordenados.

Estructuras de Árboles

El primer nodo de un árbol se denomina raíz. Un nodo es denominado padre si de él cuelgan otros.

Tipos de Árboles

• Equilibrado: Todos los niveles están completos salvo el último.
• Equilibrado perfectamente: Todos los niveles son simétricos.

Árbol Binario

Los nodos no pueden tener más de 2 hijos. Se caracterizan por su factor de equilibrio: la diferencia entre la profundidad de los subárboles derecho e izquierdo. Está perfectamente equilibrado cuando su factor de equilibrio es cero y también lo es el de sus subárboles. Se considera equilibrado cuando su factor de equilibrio difiere como máximo en 1 unidad (puede valer -1, 0 o 1) y también lo son los subárboles que lo componen.

Árbol Binario Completo de Profundidad n

Tiene todos los niveles, excluido el $n$, llenos de nodos. Los nodos del nivel $n$ ocupan las posiciones más a la izquierda del árbol.

Recorridos en Árboles

Tipos de recorrido:

• En Profundidad: Todos los descendientes de un hijo se procesan antes del siguiente hijo. Se subdivide en:
  • Preorden: La raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho.
  • Inorden: La raíz se recorre entre los recorridos de los árboles izquierdo y derecho.
  • Postorden: La raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho.
• En Anchura: Cada nivel se procesa antes de pasar al siguiente nivel.

Árbol Binario de Búsqueda

Dado un nodo, todos los nodos del subárbol izquierdo tienen datos menores que el dato del nodo nombrado; los del subárbol derecho serán mayores. Un recorrido inorden de dicho árbol nos arrojará una secuencia ordenada de los valores contenidos en él.

Para eliminar un nodo:

1. Encontrar el nodo a eliminar.
2. Rajustar los punteros para mantener la estructura del árbol:

• Si es hoja, se borra directamente.
• Si tiene 1 hijo, se conecta el padre con él.
• Si tiene 2 hijos, se escoge el elemento más a la derecha del subárbol izquierdo.

Árboles Equilibrados de Búsqueda

Un árbol totalmente equilibrado o balanceado se caracteriza porque las ramas izquierda y derecha de cualquier nodo tienen la misma longitud.

Árbol AVL

Un árbol AVL es un árbol binario de búsqueda en el que las alturas de los subárboles izquierdo y derecho de cualquier nodo difieren como máximo en 1. La inserción o eliminación en un árbol AVL se realiza de manera similar a un árbol binario de búsqueda, pero al modificar datos puede romperse el criterio de equilibrio. En este caso, es necesario reestructurar el árbol mediante rotaciones (derecha, izquierda, doble-derecha, doble-izquierda) para que siga manteniendo la condición de equilibrio.

• Búsqueda: Igual que en un árbol binario de búsqueda.
• En inserción: Si se inserta en la rama más corta no se hace nada; si es en la más larga, si la altura del árbol no aumenta, se rebalancea (rota).
• En eliminación: Se elimina el nodo, se comprueba el balanceo y se rebalancea si es necesario.