Estructuras de datos dinámicas/Texto completo

Estructuras de datos dinámicas/Texto completo

Objetivo

Este libro está dirigido principalmente a estudiantes de la carrera de Ingeniería en Sistemas. Está basado en el temario de la materia "Diseño e Implementación de Estructuras de Datos", de la Universidad Tecnológica Nacional, Facultad Regional Santa Fe, Argentina.

Contenido

1. Soporte teórico
2. Estructuras lineales
3. Árboles
4. Colas de prioridad y montones
5. Tablas Hash
6. Grafos
7. Algoritmos de optimización
8. Algoritmos de búsqueda
9. Algoritmos de ordenamiento

---

• Texto completo 
  Aquí se encuentra todo el texto del libro: Estructuras de datos dinámicas

Cantidad de nodos en un árbol

Sea un árbol n-ario completo de altura h.

En el nivel 0 tendrá un solo nodo: la raíz. En el segundo tendrá $n$ nodos, en el tercero $n^{2}$; en general, en el nivel h tendrá $n^{h}$ nodos.

Para saber la cantidad total C de nodos que tiene el árbol completo de altura h, tendremos que sumar la cantidad de nodos de cada uno de los niveles:

$C=\sum _{k=0}^{h}n^{k}$

Simplificando la expresión

$C=\sum _{k=0}^{h}n^{k}=n^{0}+n^{1}+n^{2}+\cdots +n^{h-1}+n^{h}$

Multiplicando ambos lados por n:

$n.C=n^{1}+n^{2}+\cdots +n^{h-1}+n^{h}+n^{h+1}$

Restando miembro a miembro:

$n.C-C=n^{1}+n^{2}+\cdots +n^{h-1}+n^{h}+n^{h+1}-(n^{0}+n^{1}+n^{2}+\cdots +n^{h-1}+n^{h})$

$n.C-C=-n^{0}+n^{h+1}$

$(n-1).C=n^{h+1}-1$

$C={\cfrac {n^{h+1}-1}{n-1}}$

Estructuras lineales

Secuencias

Una secuencia es una estructura lineal de uno o más elementos. Al número n de elementos se le llama longitud de la secuencia.

Si n = 0, se tiene una secuencia vacía.

Es una estructura lineal generalizada:

Lineal: si n ≥ 1, $a_{1}$ es el primer elemento y $a_{n}$ el último, $a_{i}$ precede a $a_{i+1}$ y sucede a $a_{i-1}$. Sus elementos están ordenados por sus posiciones.

Generalizada: permite accesos, inserciones y borrados en cualquier posición, a diferencia de otras estructuras lineales (como pilas y colas), que sólo lo permiten en determinadas posiciones.

Secuencias

Una secuencia es una estructura lineal de cero o más elementos. Al número n de elementos se le llama longitud de la secuencia.

Si n = 0, se tiene una secuencia vacía.

Es una estructura lineal generalizada:

Lineal: si n ≥ 1, $a_{1}$ es el primer elemento y $a_{n}$ el último, $a_{i}$ precede a $a_{i+1}$ y sucede a $a_{i-1}$. Sus elementos están ordenados por sus posiciones.

Generalizada: permite accesos, inserciones y borrados en cualquier posición, a diferencia de otras estructuras lineales (como pilas y colas), que sólo lo permiten en determinadas posiciones.

Secuencias por índice: Vectores

Sea S una secuencia con n elementos. Podemos referirnos a cada elemento e de S usando un entero en el rango [0, n - 1] que denominamos índice. El índice de un elemento puede cambiar cuando se actualiza la secuencia.

Operaciones

BuscarEn(r)

Devuelve el elemento en la posición r. Se ejecuta en un tiempo de O(1).

ModificarEn(r, e)

Coloca el elemento e en la posición r. Se ejecuta en un tiempo de O(1).

InsertarEn(r, o)

Requiere desplazar hacia delante (n – r) elementos. En el caso peor (r = 0) el costo en tiempo es de O(n).

EliminarEn(r)

Requiere desplazar hacia atrás (n – r – 1) elementos. En el caso peor (r = 0) el costo en tiempo es de O(n). Para poder realizar inserciones y eliminaciones en ambos extremos con costo en tiempo de O(1), puede utilizarse un arreglo circular.

Secuencias por posición: Listas

Una posición proporciona una forma unificada de referirse al “lugar” en el que están almacenados los elementos. Una lista es un contenedor de objetos, la cual almacena cada elemento en una posición y mantiene esas posiciones dispuestas en orden lineal. En cambio, una posición no es un contenedor, puesto que almacena un único elemento y no una colección, y sólo soporta la operación recuperar(), que devuelve el objeto almacenado en esta posición. Una posición siempre se define de manera relativa, es decir, en función de los vecinos. En una lista L, una posición p estará siempre después de alguna posición q y delante de alguna posición s (excepto cuando p es la primera o la última posición de la lista). Una posición p, la cual está asociada con algún objeto o de la lista L, no cambia, incluso aunque el orden lógico de o cambie (por ejemplo, un nodo está asociado a su contenido independientemente de su posición relativa con respecto a otros).

Operaciones

Recorrido

Consiste en visitar cada uno de las posiciones de la lista. Tendrá, naturalmente, una complejidad de O(n).

Inserción

Consiste en agregar un nuevo elemento a la lista.

Insertar Al Inicio

Tendrá complejidad de O(1).

InsertarDespuésDe(Elemento e)

Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n). Puede implementarse también InsertarAntesDe(Elemento e).

InsertarAlFinal

Dependiendo de la implementación, puede ejecutarse con costo en tiempo de O(1) (aquí solo hace falta añadir un puntero al final). ===== Borrado =====cfcf Consiste en quitar una posición de la lista.

EliminarPrimero

Tendrá complejidad de O(1).

EliminarÚltimo

Dependiendo de la implementación, puede ejecutarse con costo en tiempo de O(1) (para restaurar la información adicional con complejidad constante, una posición no podrá tener solamente una referencia al siguiente, sino también al anterior).

Eliminar(Elemento e)

Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n).

EliminarAnteriorA(Elemento e)

Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n). Puede implementarse también EliminarPosteriorA(Elemento e).

Búsqueda

Consiste en visitar cada una de las posiciones, hasta ubicar una con determinada característica, y devolverla.

Listas circulares

Todos los contenedores tienen una referencia al siguiente, de manera que no hay uno primero ni uno último, y la información de estado se limita a un contenedor actual.

Pilas

En estas estructuras de datos, el acceso está limitado al elemento más recientemente insertado.

Operaciones

Todas las operaciones naturales de una pila pueden ser ejecutadas en tiempo de O(1).

Apilar (push)

Inserta un elemento en la cima de la pila.

Desapilar (pop)

Elimina la posición en la cima de la pila y devuelve el objeto que contiene.

Cima (top)

Devuelve el elemento que hay en la cima de la pila sin eliminarlo.

Colas

En estas estructuras de datos, el acceso está limitado al elemento más antiguamente insertado.

Operaciones

Todas las operaciones naturales de una cola pueden ser ejecutadas en tiempo de O(1).

Encolar (enqueue)

Inserta un elemento al final de la cola.

Desencolar (dequeue)

Elimina la posición en el frente de la cola y devuelve el objeto que contiene.

Ver (peek)

Devuelve el elemento que hay en el frente de la cola sin eliminarlo.

Colas dobles

Es una estructura similar a una cola, excepto que está permitido el acceso por ambos extremos. Así como en las listas, para restaurar las referencias con complejidad constante luego de una eliminación al final, una posición no podrá tener solamente una referencia al siguiente, sino también al anterior.

Nodos cabecera

Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista estará diferenciado de los demás. Una lista con nodo cabecera satisface el requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías. Se simplifica el código y aumenta la velocidad a cambio de un despreciable aumento de espacio.

Iteradores

Un iterador es un patrón de diseño de software que abstrae el proceso de recorrer una colección de elementos. Un iterador consta de una secuencia S, una posición actual en S y una forma de avanzar a la siguiente posición, convirtiéndola en su posición actual.

Operaciones

TieneSiguiente

Determina si hay un elemento siguiente.

Siguiente

Devuelve el elemento siguiente.

EliminarActual

Elimina el elemento actual de la secuencia.

Secuencias por posición: Listas

Una posición proporciona una forma unificada de referirse al “lugar” en el que están almacenados los elementos. Una lista es un contenedor de objetos, la cual almacena cada elemento en una posición y mantiene esas posiciones dispuestas en orden lineal. En cambio, una posición no es un contenedor, puesto que almacena un único elemento y no una colección, y sólo soporta la operación recuperar(), que devuelve el objeto almacenado en esta posición. Una posición siempre se define de manera relativa, es decir, en función de los vecinos. En una lista L, una posición p estará siempre después de alguna posición q y delante de alguna posición s (excepto cuando p es la primera o la última posición de la lista). Una posición p, la cual está asociada con algún objeto o de la lista L, no cambia, incluso aunque el orden lógico de o cambie (por ejemplo, un nodo está asociado a su contenido independientemente de su posición relativa con respecto a otros).

Operaciones

Recorrido

Consiste en visitar cada uno de las posiciones de la lista. Tendrá, naturalmente, una complejidad de O(n).

Inserción

Consiste en agregar un nuevo elemento a la lista.

InsertarAlInicio

Tendrá complejidad de O(1).

InsertarDespuésDe(Elemento e)

Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n). Puede implementarse también InsertarAntesDe(Elemento e).

InsertarAlFinal

Dependiendo de la implementación, puede ejecutarse con costo en tiempo de O(1) (aquí solo hace falta añadir un puntero al final). ===== Borrado =====cfcf Consiste en quitar una posición de la lista.

EliminarPrimero

Tendrá complejidad de O(1).

EliminarÚltimo

Dependiendo de la implementación, puede ejecutarse con costo en tiempo de O(1) (para restaurar la información adicional con complejidad constante, una posición no podrá tener solamente una referencia al siguiente, sino también al anterior).

Eliminar(Elemento e)

Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n).

EliminarAnteriorA(Elemento e)

Deberá realizarse la búsqueda de e, por lo que tendrá complejidad de O(n). Puede implementarse también EliminarPosteriorA(Elemento e).

Búsqueda

Consiste en visitar cada una de las posiciones, hasta ubicar una con determinada característica, y devolverla.

Listas circulares

Todos los contenedores tienen una referencia al siguiente, de manera que no hay uno primero ni uno último, y la información de estado se limita a un contenedor actual.

Pilas

En estas estructuras de datos, el acceso está limitado al elemento más recientemente insertado.

Operaciones

Todas las operaciones naturales de una pila pueden ser ejecutadas en tiempo de O(1).

Apilar (push)

Inserta un elemento en la cima de la pila.

Desapilar (pop)

Elimina la posición en la cima de la pila y devuelve el objeto que contiene.

Cima (top)

Devuelve el elemento que hay en la cima de la pila sin eliminarlo.

Colas

En estas estructuras de datos, el acceso está limitado al elemento más antiguamente insertado.

Operaciones

Todas las operaciones naturales de una cola pueden ser ejecutadas en tiempo de O(1).

Encolar (enqueue)

Inserta un elemento al final de la cola.

Desencolar (dequeue)

Elimina la posición en el frente de la cola y devuelve el objeto que contiene.

Ver (peek)

Devuelve el elemento que hay en el frente de la cola sin eliminarlo.

Colas dobles

Es una estructura similar a una cola, excepto que está permitido el acceso por ambos extremos. Así como en las listas, para restaurar las referencias con complejidad constante luego de una eliminación al final, una posición no podrá tener solamente una referencia al siguiente, sino también al anterior.

Nodos cabecera

Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista estará diferenciado de los demás. Una lista con nodo cabecera satisface el requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías. Se simplifica el código y aumenta la velocidad a cambio de un despreciable aumento de espacio.

Iteradores

Un iterador es un patrón de diseño de software que abstrae el proceso de recorrer una colección de elementos. Un iterador consta de una secuencia S, una posición actual en S y una forma de avanzar a la siguiente posición, convirtiéndola en su posición actual.

Operaciones

TieneSiguiente

Determina si hay un elemento siguiente.

Siguiente

Devuelve el elemento siguiente.

EliminarActual

Elimina el elemento actual de la secuencia.

Árboles

Árbol: estructura no lineal y dinámica de datos. Dinámica: puede cambiar durante la ejecución de un programa. No lineal: a cada elemento del árbol pueden seguirle varios elementos. Están formados por un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.

Definición no recursiva

Conjunto de nodos y conjunto de aristas que conectan pares de nodos con las siguientes características:

Se distingue un nodo raíz (no tiene padre).

A cada nodo c (excepto la raíz) le llega una arista desde exactamente un nodo p diferente a c, al cual se le llama padre de c.

Hay un único camino desde la raíz hasta cada nodo. La misma longitud del camino es su número de aristas.

Definición recursiva

Un árbol es o bien vacío o consiste en una raíz y cero o más subárboles no vacíos $T_{1}$, $T_{2}$,…, $T_{n}$, cada una de cuyas raíces está conectada por medio de una arista con la raíz.

Definiciones

Los nodos que no tienen hijos se denominan hojas.

Un árbol con N nodos debe tener (N-1) aristas.

La profundidad de la raíz es 0 y la de cualquier nodo es la de su padre más 1.

La altura de un nodo es 1 más que la mayor altura de un hijo suyo. La altura de un árbol es la altura de la raíz.

Los nodos que tienen el mismo padre son hermanos.

Si hay un camino del nodo u al nodo v, u es ascendiente de v y v es descendiente de u. Si u $\neq$ v son propios.

El tamaño de un nodo es el número de descendientes (incluido él mismo). El tamaño de un árbol es el tamaño de su raíz.

Operaciones básicas

Insertar

Buscar

Eliminar

Ir a la raíz

Recorrer

Implementación primer hijo - siguiente hermano

Consiste en mantener los hijos de cada nodo en una lista enlazada. Cada nodo tiene dos referencias: una a su hijo más a la izquierda y otra a su hermano de la derecha.

Árboles binarios

Un árbol binario es o bien vacío o consta de una raíz, un hijo árbol binario izquierdo y otro derecho. Los árboles binarios de búsqueda permiten inserciones y acceso a los elementos en tiempo logarítmico. Los árboles binarios llamados colas con prioridad soportan acceso y eliminación del mínimo de una colección de elementos.

Árboles binarios de búsqueda

Para todo nodo A del árbol:

Todos los valores de los nodos del subárbol izquierdo de A deben ser menores al valor del nodo A.

Todos los valores de los nodos del subárbol derecho de A deben ser mayores o iguales al valor del nodo A. Un recorrido en inorden del árbol proporciona una lista en orden ascendente de los valores almacenados en los nodos. Para describir las operaciones, se considera que estas se enmarcan dentro de la clase NodoBinario. El lenguaje utilizado es JAVA.

Operación “buscar”

  buscar(Object o)
 {
   if (o.equals(valor)) 
     return true;
   else if (o.compareTo(valor)<0) 
     return buscar(getIzq(),o); 
   else return buscar(getDer(),o); 
 }

Operación “insertar”

 public NodoBinario insertar(Comparable o){ 
   if (o.compareTo(valor)<0) 
     setIzq(insertar(getIzq(),o)); 
   else setDer(insertar(getDer(),o)); 
   return this;
 }

Dentro de la clase NodoBinarioVacio:

 public NodoBinario insertar(Comparable o)
 {
   return new NodoBinario(o);
 }

Operación “recorrer”

Los recorridos pueden ser en preorden, postorden o inorden (orden simétrico). Todos son O(N).

 public void preOrder(SList aList)
 {
   aList.addElement(value);
   left.preOrder(aList);
   right.preOrder(aList);
 }

 public void inOrder(SList aList)
 {
   left.inOrder(aList);
   aList.addElement(value);
   right.inOrder(aList);
 }

 public void posOrder(SList aList)
 {
   left.posOrder(aList);
   right.posOrder(aList);
   aList.addElement(value);
 }

Los recorridos no necesitan obligatoriamente recursividad, se puede emplear una pila para realizarlos iterativamente.

Operación “borrado”

El nodo a borrar debe ser reemplazado por el nodo más a la derecha en el subárbol izquierdo o el nodo más a la izquierda en el subárbol derecho (el nodo más a la derecha del subárbol izquierdo será mayor o igual que cualquier otro nodo de ese subárbol y menor que todos los del subárbol derecho, y el nodo más a la izquierda del subárbol derecho será menor que todos los demás nodos de ese subárbol y mayor que todos los del subárbol izquierdo). Para el caso en el que el nodo elegido tengo un subárbol, hay por lo menos tres soluciones posibles:

La primera consiste en conservar la estructura del subárbol, y colgar del elemento ubicado en el extremo (el elemento menor o mayor) correspondiente al subárbol donde se encuentra el elemento a promover hacia la raíz (en este ejemplo, el subárbol izquierdo, por lo cual se buscará el elemento más a la izquierda), lo cual es consistente, porque todos los elementos en el subárbol promovido serán mayores que los del subárbol del cual estaban colgados a la derecha. El inconveniente que presenta esta solución es que debe utilizarse una función encontrarMínimo() o encontrarMáximo().

La segunda solución consiste en colgar del padre del nodo promovido hacia la raíz, el subárbol remanente. Esto es consistente, porque todo elemento del subárbol derecho de un nodo será mayor que el valor de ese nodo, y viceversa. Estas soluciones aprovechan la ventaja de contar con que el nodo promovido tiene, a lo sumo, un subárbol.

Un hueco dejado por un nodo promovido también puede pensarse como una eliminación. un arbol es un arbol jajaja

Árboles binarios perfectamente equilibrados

La eficiencia de las operaciones depende exclusivamente de la altura del árbol. Para un árbol de N nodos perfectamente equilibrado el coste de acceso es de orden logarítmico: O(log N). Sin embargo, se dice que si el árbol crece o decrece descontroladamente, el rendimiento puede disminuir considerablemente, siendo para el caso más desfavorable (insertar un conjunto de claves ordenadas en forma ascendente o descendente) el coste de acceso: O(N). En un árbol binario perfectamente equilibrado, el número de nodos en el subárbol izquierdo y el número de nodos en el subárbol derecho, difieren como mucho en una unidad, y los subárboles son también equilibrados

Árboles equilibrados

Un procedimiento de inserción que siempre restaure la estructura del árbol a un equilibrio perfecto es poco eficiente. Se usa una formulación menos estricta de “equilibrio”: Un árbol está equilibrado si para cada uno de sus nodos ocurre que las alturas de sus dos subárboles difieren como mucho en 1(Árboles AVL).

Factor de equilibrio (FE) de un nodo

El FE es la altura del subárbol izquierdo menos la altura del subárbol derecho. Los valores que puede tomar son -1, 0, 1. Si llegara a tomar los valores -2 o 2 debe reestructurarse el árbol. Todos los árboles perfectamente equilibrados son AVL. La longitud de camino media es prácticamente idéntica a la de un árbol perfectamente equilibrado. En un AVL se puede realizar con complejidad del O(log N) las siguientes operaciones:

Encontrar un nodo con una clave dada.

Insertar un nodo con una clave dada.

Borrar un nodo con una clave dada. Un árbol AVL de altura H tiene por lo menos (Fibonacci(H+3) -1) nodos. Los pasos necesarios para insertar un nodo en un árbol AVL son:

Agregar el nodo como en un árbol binario de búsqueda.

En el regreso por el camino de búsqueda se comprueba el FE de los nodos.

Si un nodo presenta un FE incorrecto (2 o -2) se reestructura el árbol y se continúa el ascenso hasta llegar a la raíz. Casos en situación de reestructurar:

1. Una inserción en el subárbol izquierdo del hijo izquierdo de X.
2. Una inserción en el subárbol derecho del hijo izquierdo de X.
3. Una inserción en el subárbol izquierdo del hijo derecho de X.
4. Una inserción en el subárbol derecho del hijo derecho de X.

Inserciones en los “márgenes”

1 y 4: inserciones en los “márgenes”: rotación simple: intercambia los papeles de los padres y de los hijos, manteniendo la ordenación.

 // Rotación izquierda - izquierda
 private static NodoAVL rotarConHijoIzq(NodoAVL A)
 {
   NodoAVL B = (NodoAVL) A.getIzq(); //Asigna nombre
   A.setIzq(B.getDer());
   B.setDer(A);
   return B;
 }

Inserciones por “dentro”

2 y 3: inserciones por “dentro”: rotación doble. Notar que una rotación simple no resuelve el problema, ya que la rama que provocó el desequilibrio se descuelga del nodo promovido y se cuelga al nodo que desciende un nivel, de manera que se mantiene con la misma profundidad, que es la que provocó el desequilibrio. Por lo tanto, antes de rotar, debe desplazarse el desequilibrio a la rama correspondiente, es decir, transformamos el caso de una inserción por dentro, a un caso de inserción en el margen, utilizando una rotación.

 // Rotación izquierda - derecha
 private static NodoAVL rotarDobleConHijoIzq(NodoAVL A)
 {
   NodoAVL B = (NodoAVL) A.getIzq(); //Asigna nombre
   A.setIzq(rotarConHijoDer((NodoAVL) B));
   return rotarConHijoIzq(A);
 }

Como se ve, el problema se convirtió en un problema igual al del primer caso. Los pasos necesarios para suprimir un nodo en un árbol AVL son:

Suprimir el nodo como en un árbol binario de búsqueda.

En el regreso por el camino de supresión se comprueba el FE de los nodos.

Si un nodo presenta un FE incorrecto (2 o -2) se reestructura el árbol y se continúa el ascenso hasta llegar a la raíz. La reestructuración se efectúa cuando al regresar por el camino de búsqueda después de una inserción o una supresión se comprueba que la condición del FE se ha violado. Una supresión puede provocar varias reestructuraciones. En la práctica se utilizan otros esquemas de equilibrio como los árboles rojinegros: como en los AVL las operaciones son logarítmicas en el peor caso. La ventaja es que las inserciones y eliminaciones pueden realizarse con un único recorrido descendente.

Árboles rojinegros

Árbol binario de búsqueda, donde cada nodo está coloreado con los colores rojo o negro, y se verifican las siguientes propiedades:

1. La raíz es negra.

2. Si un nodo es rojo, sus hijos deben ser negros.

3. Todos los caminos desde un nodo a un nodo vacío deben contener el mismo número de nodos negros.

Las condiciones (2) y (3) aseguran que el árbol nunca esté demasiado desbalanceado. (2) asegura que no puedan haber demasiados nodos rojos, y (3) dice que, despreciando el número de nodos rojos, que es limitado, el árbol es perfectamente balanceado. La condición (1) es trivial: si la raíz es roja, simplemente se colorea negra, ya que esto no violará ninguna regla. En los ARN la operación eliminar se complica. Cuando se necesitan árboles equilibrados y se requieren muchas eliminaciones se emplean los AA-Árboles que añaden una condición adicional a las impuestas por los ARN:

4. Los hijos izquierdos no pueden ser rojos.

Altura de un ARN

En un ARN con n nodos, la altura h será: $h\leq 2log_{2}(n+1)$

Demostración

La condición (3) nos permite asegurar que, despreciando el número de nodos rojos, el árbol es perfectamente balanceado, y, en virtud de esa característica, su altura $h\leq 2log_{2}(n+1)$. La condición (2) evita que haya nodos rojos consecutivos, como máximo, la mitad de los nodos de un camino -que constituirán una altura- serán rojos.

Operaciones

Se pueden realizar operaciones de búsqueda con complejidad O(log N), por lo expuesto anteriormente. Al realizar una inserción, la complejidad de búsqueda será O(log N), pero aparece un problema: el resultado será un árbol de búsqueda binario, pero no necesariamente un ARN. Si coloreamos el nuevo nodo rojo, el balance de negros quedará intacto, pero se puede incurrir en una violación rojo-rojo. Si lo coloreamos negro, no se incurrirá en una violación rojo-rojo, pero en este caso, siempre alteraremos el balance de negros. Al eliminar, si el nodo a eliminar es negro, ambas violaciones pueden aparecer.

Reparación del balance del árbol

Una vez detectada una violación, se deben tomar medidas que reparen el balance del árbol. Estas medidas utilizan dos herramientas: rotaciones y cambios de color.

Inserción ascendente

Sea X la nueva hoja añadida, P su padre, S el hermano de P (si existe) y G el abuelo.

1. Los nuevos nodos se insertan en el árbol como hojas de color rojo.

2. Si el padre es negro, hemos acabado.

3. Si el padre es rojo violamos la regla 2, entonces debemos modificar el árbol de forma que se cumpla la regla (2) sin introducir violaciones de la propiedad (3).

4. Si el padre P es la raíz, se colorea negro. La altura negra aumenta en 1, pero el balance se preserva. Hemos acabado.

Reparación del balance

Asumiendo que P no es la raíz

5. Si S es rojo, se puede aplicar un cambio de color: Se elimina así la violación, y el balance de negros se mantiene. ¿Qué pasa si el padre de G es también rojo? Solución: propagar este procedimiento hacia arriba hasta conseguir que no haya dos nodos rojos consecutivos o alcanzar la raíz. Esta propagación es análoga a la que se hace en los árboles AVL.

6. Si S es negro, tenemos dos casos, con sus simétricos asociados: violación en el margen, y violación por dentro.

7. Si es una violación es por dentro, la convertimos a una violación en el margen haciendo una rotación: Como X y P son rojos, no añaden nada en el balance de negros a los caminos que pasan por g, de manera que el balance se preserva.

8. Teniendo el caso de violación por dentro, se efectúa una rotación simple. La rama izquierda de desbalancea, le falta un nodo negro para todos sus caminos, y aún tenemos la violación rojo-rojo. Solucionamos ambos problemas haciendo un cambio de color.

Inserción descendente

Objetivo: garantizar que en el momento de la inserción S no sea rojo, de manera que sólo haya que añadir una hoja roja y, si fuere necesario, realizar una rotación (simple o doble). En el camino descendente, si un nodo X tiene dos hijos rojos, el color de X cambia a rojo y el de sus dos hijos a negro. El número de nodos negros en los caminos por debajo de X permanece inalterable. Si X es la raíz, la convertiríamos en roja, hay que volver a negro (esto no puede violar ninguna de las reglas). Si el padre de X es rojo, hay que aplicar rotación simple o doble. ¿Qué pasa si el hermano del padre de X es también rojo? Esta situación NO puede darse, gracias al proceso efectuado en el camino descendiente.

Árboles B

Mientras que la altura de un árbol binario completo es, aproximadamente, $log_{2}N$, la altura de un árbol M-ario completo es, más o menos, $log_{M}N$. Un B-árbol de orden M es un árbol M-ario que verifica:

Cada página, excepto la página raíz y las páginas hojas, tienen entre M/2 y M descendientes, y entre (M/2 -1) y (M-1) elementos.

La página raíz, o es una hoja o tiene entre 2 y M descendientes.

Las páginas hojas están todas al mismo nivel.

Relación entre los árboles B y los árboles rojinegros

Si juntamos un nodo negro con sus hijos rojos, si los hubiere, en un mismo nodo, se obtiene un árbol no binario con altura igual a la altura negra, con un máximo de 3 elementos y 4 hijos, y un mínimo de un elemento; en definitiva, es un árbol B de orden 4.

Búsqueda

Debe tenerse en memoria principal la página sobre la cual vamos a buscar. Considérese el elemento a buscar x. Si la búsqueda es infructuosa dentro de la página se estará en una de las siguientes situaciones:

$k_{i}<x<k_{i+1}$ para 1 ≤i < n. La búsqueda continúa en la página $r_{i}$.

$k_{n}<x$. La búsqueda continúa en la página $r_{n}$.

$x<k_{1}$. La búsqueda continúa en la página$r_{0}$. Si en algún caso la referencia es nula, es decir, si no hay página descendiente, entonces no hay ningún elemento x en todo el árbol y se acaba la búsqueda.

Inserción

Siempre se inserta en los nodos hojas. Primero se comprueba que la clave no se encuentre en el árbol. Si la cantidad de elementos es menor que 2n:

Se inserta en forma secuencial la clave. Si la cantidad de elementos es 2n:

Los 2n+1 elementos se dividen en dos páginas, excluyendo la clave del medio.

La clave del medio se inserta en el nodo padre.

Borrado

Si la clave a ser borrada no está en una hoja, su predecesor inmediato tiene que estar en una hoja (esto se debe a que todas las hojas tienen el mismo nivel, de manera que si existe un valor menor en un nodo más abajo, también tiene que haber uno mayor), y se puede promover, y así borrar el espacio que estaba en la hoja. Si la hoja queda con menos de n elementos, se comprueba si se puede promover un elemento de un hermano adyacente a su padre, y bajar el del padre a la hoja. Si el hermano tiene sólo n elementos, las dos hojas y la clave del medio se unen, y la clave del medio se elimina del nodo padre.

Árboles B+

Las diferencias con los árboles B son que:

Sólo los nodos hoja apuntan a los registros o cubetas del fichero.

Existe un orden lineal entre las hojas, que están encadenadas mediante punteros para permitir un eficiente acceso secuencial.

Búsqueda por clave

Buscar en la raíz el valor $k_{i}$ más pequeño mayor que la clave x. La búsqueda sigue por el puntero $p_{i}$ hasta que llegue a un nodo hoja, que será donde esté el puntero al bloque o cubeta (cuando un elemento se encuentre en una página raíz o interior la búsqueda continuará por la rama derecha de dicha clave, hasta llegar a una hoja).

Inserción

Se busca el nodo hoja correspondiente y se inserta la clave si no está allí. Si tiene lugar una partición, se inserta una clave en el nodo padre, que será duplicada si la partición ocurre en una hoja.

1. include<conio.h>
2. include<stdio.h>
3. include<iostream.h>
4. include<stdlib.h>
5. include<dos.h>

struct nodo {

int valor;
struct nodo*sig;

}*cab; void insertar(int num); void mostrar(void); void BorrarTodo(void); void Eliminar(int num); void insertord(int num);

void main (void) { int op, num; cab=NULL;

while(1)
{
clrscr();
printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");
printf("\nElige una opcion: ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertar(num);
break;
case 2:
printf("Dame el valor del nodo a eliminar: ");
scanf("%d",&num);
Eliminar(num);
break;
case 3:
mostrar();
break;
case 4:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertord(num);
break;
case 0:
BorrarTodo();
exit(0);//para usar exit debes declarar stdlib.h
break;
default:
printf("ERROR Opcion incorrecta");
getch();



}
getch();
}

} void insertar(int num) {

nodo *aux,*nuevo;
aux=cab;
nuevo=new nodo;
nuevo->valor=num;
nuevo->sig=NULL;
if(cab==NULL)
cab=nuevo;

else
{
while(aux->sig!=NULL)
aux=aux->sig;
aux->sig=nuevo;

}

}

void mostrar()
{
nodo *aux; //Aux es un apuntador
aux=cab; //En esta line aux toma la direccion de cab
while(aux!=NULL)
{
printf("%d, ",aux->valor);
aux=aux->sig;
}
}

void BorrarTodo(void)

{
nodo *aux;
aux=cab;
while(aux!=NULL)
{
cab=aux->sig;
delete aux;
aux=cab;
}
}

void Eliminar(int num) {

nodo *aux,*aux2, *prev;
int c=0;
aux=cab;

while(c!=1)
{
if(aux->valor==num)
{
c=1;
}
else{
prev=aux;
aux=aux->sig;
}
}

if(c==1)
{
if(prev->sig==NULL)
{
cab=cab->sig;
delete aux;
}
else
{
aux2 = aux->sig;
prev->sig = aux2;
delete aux;
}
}

}

void insertord(int num) {

nodo *aux,*nuevo,*aux2,*prev;
int c=0;
aux2=cab;
nuevo=new nodo;
// nuevo->valor=num;
while(aux2!=NULL)
{
if(aux2->valor>=num)
{

prev->sig=nuevo;
nuevo->valor=num;
nuevo->sig=aux2;
cab=prev;
aux2=NULL;
c=1;
}
prev=aux2;
aux2=aux2->sig;
}
if(aux2==NULL)
if(c==0)
{
insertar(num);
}
else
{
delete aux2;
}

}

Eliminación

Se busca el nodo hoja correspondiente y se elimina la clave. Si al eliminar una clave, n queda menor a (M/2 -1), entonces debe realizarse una redistribución de claves, tanto en el índice como en las páginas hojas.

1. include<conio.h>
2. include<stdio.h>
3. include<iostream.h>
4. include<stdlib.h>
5. include<dos.h>

struct nodo {

int valor;
struct nodo*sig;

}*cab; void insertar(int num); void mostrar(void); void BorrarTodo(void); void Eliminar(int num); void insertord(int num);

void main (void) { int op, num; cab=NULL;

while(1)
{
clrscr();
printf("1.-Insertar un nodo.\n2.-Eliminar un nodo.\n3.-Mostrar\n4.-Insettar nodos en orden\n0.-Salir\n");
printf("\nElige una opcion: ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertar(num);
break;
case 2:
printf("Dame el valor del nodo a eliminar: ");
scanf("%d",&num);
Eliminar(num);
break;
case 3:
mostrar();
break;
case 4:
printf("Valor del nodo que deseas insertar: ");
scanf("%d",&num);
insertord(num);
break;
case 0:
BorrarTodo();
exit(0);//para usar exit debes declarar stdlib.h
break;
default:
printf("ERROR Opcion incorrecta");
getch();



}
getch();
}

} void insertar(int num) {

nodo *aux,*nuevo;
aux=cab;
nuevo=new nodo;
nuevo->valor=num;
nuevo->sig=NULL;
if(cab==NULL)
cab=nuevo;

else
{
while(aux->sig!=NULL)
aux=aux->sig;
aux->sig=nuevo;

}

}

void mostrar()
{
nodo *aux; //Aux es un apuntador
aux=cab; //En esta line aux toma la direccion de cab
while(aux!=NULL)
{
printf("%d, ",aux->valor);
aux=aux->sig;
}
}

void BorrarTodo(void)

{
nodo *aux;
aux=cab;
while(aux!=NULL)
{
cab=aux->sig;
delete aux;
aux=cab;
}
}

void Eliminar(int num) {

nodo *aux,*aux2, *prev;
int c=0;
aux=cab;

while(c!=1)
{
if(aux->valor==num)
{
c=1;
}
else{
prev=aux;
aux=aux->sig;
}
}

if(c==1)
{
if(prev->sig==NULL)
{
cab=cab->sig;
delete aux;
}
else
{
aux2 = aux->sig;
prev->sig = aux2;
delete aux;
}
}

}

void insertord(int num) {

nodo *aux,*nuevo,*aux2,*prev;
int c=0;
aux2=cab;
nuevo=new nodo;
// nuevo->valor=num;
while(aux2!=NULL)
{
if(aux2->valor>=num)
{

prev->sig=nuevo;
nuevo->valor=num;
nuevo->sig=aux2;
cab=prev;
aux2=NULL;
c=1;
}
prev=aux2;
aux2=aux2->sig;
}
if(aux2==NULL)
if(c==0)
{
insertar(num);
}
else
{
delete aux2;
}

}

Colas de prioridad y montones

Una cola de prioridad soporta acceso y eliminación del elemento de mayor prioridad: primero() y suprimir(). Puede implementarse como una lista ordenada por prioridad, cuya complejidad para el caso peor en la operación insertar es O(N), un árbol binario de búsqueda, con complejidad media en las operaciones primero() y suprimir(): O(log N), o un árbol binario de búsqueda equilibrado.

Montículo binario, montón o heap

Un montículo es un árbol binario que satisface las siguientes condiciones:

Es completo, con la excepción del nivel inferior, que debe llenarse de izquierda a derecha.

Las hojas están en dos niveles adyacentes.

Para cada nodo X con padre P, se cumple que el dato en P es mayor o igual que el dato en X. Ventajas:

Soporta las operaciones insertar y suprimir en tiempo O(log N) en el caso peor.

Soporta insertar en tiempo constante en promedio y primero en tiempo constante en el peor caso.

Operaciones

Insertar

El procedimiento comienza con la creación de un hueco en la siguiente posición disponible del vector. El elemento se coloca si no se viola la propiedad de ordenación del montículo. Si no, se desplaza el elemento situado en el padre del nodo a dicho hueco. Se continúa con el proceso hasta que se pueda colocar el elemento.

Suprimir

Suprimir un elemento de la cola de prioridad consiste en eliminar la raíz. La eliminación del elemento con prioridad mayor implica colocar el último elemento en un hueco que se crea en la raíz. El hueco se hunde en el árbol a través de los hijos con prioridad mayor hasta que el elemento se pueda colocar sin violar la propiedad de ordenamiento del montículo.

Método introducir()

Añade un objeto a la cola de prioridad, pero no garantiza que se mantenga la propiedad de ordenación del montículo.

Método privado arreglarMontículo()

Restablece el orden en el montículo. Llama al método hundir(int) sobre cada nodo en sentido inverso al recorrido por niveles, cuando se realice la llamada con el nodo i se habrán procesado todos los descendientes del nodo i con una llamada a hundir(). No hace falta ejecutar hundir sobre las hojas, por lo que se comienza con el nodo de mayor índice que no sea una hoja.

Implementación de un montículo

Un árbol binario completo se puede representar usando un array, colocando la raíz en la posición 1 y almacenando su recorrido por niveles en el vector. Dado un elemento en la posición i del vector:

Hijo izquierdo: posición 2i,

Hijo derecho: posición 2i +1

Padre: posición i/2 (parte entera) Se necesita mantener un entero que indique cuántos nodos hay actualmente en el árbol.

Ordenación mediante montones (Heapsort)

Se puede usar una cola de prioridad para ordenar N elementos insertándolos en un montículo binario y extrayéndolos llamando a suprimir() N veces. O(N log N) en el caso peor.

Montículo binomial

Un montículo binomial es similar a un montículo binario, pero soporta eficientemente la fusión de dos montículos.

Árbol Binomial

Definición recursiva: Un árbol binomial de orden 0 es un nodo. Un árbol binomial de orden k tiene una raíz de grado k y sus hijos son raíces de árboles binomiales de orden k-1, k-2, ..., 2, 1, 0 (en ese orden). Un árbol binomial de orden k tiene $2^{k}$ nodos, y altura k. Por su estructura, un árbol binomial de orden k puede ser construido a partir de dos árboles de orden k-1 en forma trivial, agregando uno de ellos como el hijo más a la izquierda del otro.

Estructura de un montículo binomial

Un montículo binomial se implementa como un conjunto de árboles binomiales que satisfacen las propiedades del montículo:

Cada árbol binomial en el montículo cumple la propiedad de montículo: la prioridad de un nodo es menor que la de su padre.

Puede haber como máximo un árbol binomial de cada orden. La segunda propiedad implica que un montículo binomial con n elementos contiene lg(n+1) –logaritmo binario de n+1- árboles binomiales como máximo. de hecho, el número y los órdenes de estos árboles está determinado por n: cada árbol corresponde al dígito menos significativo en la representación binaria de n. Por ejemplo, 13 es 1101 en binario, $2^{3}+2^{2}+2^{0}$, y el montículo binomial con 13 elementos consistirá en tres árboles binomiales de órdenes 3, 2, y 0.

Operaciones

Fusión

Como el nodo raíz tiene el elemento con mayor prioridad del árbol, comparando las claves de las raíces, se obtiene la de mayor prioridad, que será la clave del nodo raíz. Entonces, el otro árbol se convierte en un subárbol del árbol combinado. Si uno solo de los montículos contiene un árbol de orden j, éste árbol se lleva el montículo fusionado. Si ambos montículos contienen un árbol de orden j, ambos árboles son fusionados en uno de orden j+1 de tal manera que la propiedad de montículo se cumpla. Más tarde puede hacer falta fusionar este árbol con otro de orden j+1 presente en alguno de los montículos. En la ejecución del algoritmo, se deben examinar como máximo tres árboles de cada orden (dos provenientes de cada montículo fusionado y uno compuesto de dos árboles más pequeños). Cada árbol tiene como máximo orden lg n, por lo tanto su tiempo de ejecución es de O(lg n).

Inserción

La inserción de un nuevo elemento dentro de un montículo puede realizarse simplemente creando un nuevo montículo que contenga sólo dicho elemento, y fusionar este nuevo montículo con el original en tiempo de O(lg n).

Encontrar Primero

Para encontrar el elemento con mayor prioridad del montículo, simplemente debe buscarse el mínimo entre las raíces de los árboles binomiales, lo cual puede realizarse en un tiempo de O(lg n).

Eliminar Primero

Luego de buscar el elemento entre las raíces de los árboles binomiales, tomar los subárboles del nodo encontrado, reordenarlos de modo de formar otro montículo binomial, y fusionarlo con el montículo original.

Incrementar prioridad

Luego de incrementar la prioridad de un elemento, puede resultar con mayor prioridad que su padre, violando la propiedad de montículo. Si es ese el caso, debe intercambiarse la posición del elemento con la de su padre, sucesivamente hasta que se cumpla la propiedad de montículo. Cada árbol binomial tiene lg n de altura como máximo, de manera que toma un tiempo del O(lg n).

Eliminar

Para eliminar un elemento cualquiera del montículo, debe incrementarse su prioridad de manera que sea la mayor del montículo, y luego ejecutar la operación Eliminar Primero.

Resumen de la complejidad de las operaciones

Las siguientes operaciones se ejecutan en un tiempo de O(log n) en un montículo binomial con n elementos:

Insertar un nuevo elemento

Encontrar el elemento con mayor prioridad

Eliminar el elemento con mayor prioridad

Incrementar la prioridad de un elemento

Eliminar un elemento cualquiera

Fusionar con otro montículo

Implementación

Como ninguna operación requiere acceso aleatorio a las raíces de los árboles binomiales, éstas pueden ser almacenadas en una lista enlazada, ordenada en forma creciente de acuerdo al orden del árbol.

Tablas HASH

Permiten únicamente un subconjunto de las operaciones permitidas por los árboles binarios de búsqueda. Las inserciones, eliminaciones y búsqueda tienen coste medio constante, basado en propiedades estadísticas. Esta mejora se consigue perdiendo gran cantidad de información sobre el orden de los elementos. Este método proporciona acceso muy rápido cuando la condición de búsqueda es de igualdad sobre un solo campo. Se aplica una función sobre el valor del campo y produce la dirección del bloque de disco. Ésta no produce direcciones distintas a todo distinto valor, porque el espacio de direccionamiento calculado suele ser mucho más grande que el espacio de direcciones. Cuando la función devuelve una dirección ocupada, se dice que ocurre una colisión. Si s es una cadena, se puede convertir s a un número entero grande x y después aplicar el operador % para obtener un índice adecuado. La cadena "hola" se puede representar como: "h". $128^{3}$ + "o". $128^{2}$ + "l" . $128^{1}$ + "a" . $128^{0}$ = 224.229.227 Luego, si el tamaño de la tabla es 10000, “hola” se indexaría por 9.227

public final static int hash (String clave, int tamTabla)
{
  int valorHash = 0;
  for(int index = 0; index < clave.length (); index ++)
      valorHash = (valorHash * 128 + clave.charAt(index)  
                                    % tamTabla;
  return valorHash;
}

Métodos para resolver colisiones

Direccionamiento abierto

Partiendo de la posición que especifica la dirección, se examinan las posiciones subsecuentes en orden hasta encontrar una no utilizada. El algoritmo buscar sigue el mismo camino que el insertar: si llega a una casilla vacía, el elemento no está, caso contrario lo busca secuencialmente hasta encontrarlo o hasta que haya una casilla vacía. La eliminación estándar no puede aplicarse, porque podrían fallar operaciones de buscar posteriores. Como consecuencia se implementa la eliminación perezosa, marcando los elementos como borrados. Para estimar la eficiencia de la E. Lineal se supone cada intento en la tabla independiente de los anteriores. Si la fracción de la tabla ocupada es k, entonces cada vez que examinamos una celda, la probabilidad de que esté ocupada es k independientemente de los intentos anteriores. Si se supone independencia entre intentos, el número medio de celdas que se examinan en una inserción es ${\frac {1}{1-k}}$. Siendo (1-k) la probabilidad de encontrar una celda vacía y considerando que si la probabilidad de que un suceso se produzca es p, se necesitan en media ${\frac {1}{p}}$ intentos para que dicho suceso se produzca. Pero la independencia lineal no se cumple: existe un efecto denominado agrupación primaria: la formación de grandes grupos de celdas ocupadas, haciendo que las inserciones dentro de las agrupaciones sean más costosa. Teorema: El número medio de celdas examinadas en una inserción con exploración lineal es cercano a ${\frac {1}{2}}(1+{\frac {1}{(1-k)^{2}}})$. Teorema: Si se emplea exploración cuadrática, el tamaño de la tabla es un número primo, y el factor de carga no excede el 0.5, siempre podemos insertar un nuevo elemento en la tabla, y durante una operación de inserción no se examina ninguna celda dos veces.

Exploración cuadrática

Para reducir el número de intentos se necesita un esquema de resolución de conflictos que evite la agrupación primaria. Si la función da como resultado la celda H y está ocupada, se consultan: $H+1^{2};H+2^{2};H+3^{2};.....;H+i^{2}$ El tamaño de la tabla debe ser un número primo para evitar que se formen ciclos en la función que excluyan celdas potencialmente vacías.

Encadenamiento

Se mantienen áreas de desbordamiento y se agrega un campo puntero a cada posición de registro.

Direccionamiento calculado múltiple

Cuando ocurre una colisión se recurre a más funciones, hasta que una de una dirección libre, o se acaben, en cuyo caso se aplica el direccionamiento abierto.

La función de direccionamiento

El objetivo de una función de direccionamiento calculado es distribuir los registros uniformemente en el espacio de direcciones. Lo mejor suele ser mantener la tabla de direccionamiento ocupada entre el 70% y el 90%, y elegir un número primo para el tamaño del espacio de direcciones si la función utilizada para direccionar es basada en módulo. Otras funciones requerirán que sea una potencia de dos.

Direccionamiento calculado externo para ficheros de disco

Direccionamiento calculado estático

El espacio de direcciones se divide en cubetas (uno o varios bloques contiguos) que contienen varios registros. Este esquema ofrece el acceso más rápido para recuperar un registro arbitrario. Se puede mantener un puntero a una lista enlazada de registros de desbordamiento en cada cubeta para cuando una se llena. La mayoría de las funciones no mantienen el orden de los registros, pero algunas sí lo hacen. El esquema descrito se le llama estático, porque asigna un número M fijo de cubetas. Siendo m el máximo de registros en una cubeta, si (M*m) resulta mucho menor que el número de registros, se estará desperdiciando espacio, si es al revés, habrán muchas colisiones y la recuperación resultará lenta.

Direccionamiento extensible

Si el factor de carga es superior a 0.5, aumenta el tamaño de la tabla al primo siguiente al doble del tamaño.

Si el factor de carga es inferior a 0.5, disminuye el tamaño de la tabla al primo siguiente a la mitad del tamaño.

Un nuevo vector implica una nueva función Hash: se debe buscar cada elemento en la tabla vieja, calcular su nuevo valor hash e insertarlo en la tabla nueva : REHASHING.

Direccionamiento extensible parcial

Si el factor de carga es superior a 0.5, aumenta el tamaño de la tabla al primo siguiente al 50% del tamaño original, luego de hacer dos incrementos sucesivos el tamaño obtenido será el nuevo tamaño original.

Si el factor de carga es inferior a 0.5, disminuye el tamaño de la tabla al primo siguiente a un 50% del tamaño original, luego de hacer dos decrementos sucesivos el tamaño obtenido será el nuevo tamaño original.

Un nuevo vector implica una nueva función Hash: se debe buscar cada elemento en la tabla vieja, calcular su nuevo valor hash e insertarlo en la tabla nueva : REHASHING.

Direccionamiento calculado extensible

Se mantiene un arreglo de 2d direcciones de cubeta (d es la profundidad global). Varias posiciones del directorio que tengan los primeros d’ (profundidad de la cubeta) bits en sus valores de direccionamiento calculado pueden contener la misma dirección de cubeta. El valor de d se puede aumentar o reducir en uno cada vez, duplicando o reduciendo a la mitad el número de entradas del array. Será necesario aumentarlo si una cubeta de profundidad d se desborda. Se podrá reducir si d > d’ para todas las cubetas. El espacio extra para la tabla del directorio es insignificante, y la reorganización es menor, ya que la mayor parte de las veces sólo los registros de una cubeta se distribuyen en dos, siendo costosa solamente cuando cambia d. Una desventaja es que deben realizarse dos accesos a bloque en lugar de uno, pero esta falta de rendimiento se considera leve.

Direccionamiento calculado lineal

Utiliza una función (k mod M). Cuando ocurre una colisión, a la cubeta 0 se le aplica la función (k mod 2M) y así parte de su contenido se depositará en una nueva cubeta M, y así sucesivamente se le irá aplicando a las cubetas 1, 2, 3, …, en orden secuencial, y agregando cubetas al final hasta llegar a (M-1), momento en el cual todas las cubetas se calcularán con la función (k mod 2M). Se debe mantener el número n de divisiones en una variable, y, al momento de recuperar un registro, si la función retorna un número menor a n, se aplicará la segunda función, ya que la cubeta ya estará dividida. La división se puede controlar monitoreando la carga del fichero, pudiendo recombinarse las c cubetas si la carga cae debajo de cierto umbral.

Grafos

Un grafo G consiste en un conjunto de vértices V y un conjunto de arcos o aristas E que unen estos vértices. Si todo arco puede ser recorrido en ambos sentidos, el grafo es no dirigido. Para el caso de grafos dirigidos, cada arco tiene una dirección, generalmente representado por su nodo origen y su nodo destino.

Definiciones

Camino: secuencia de vértices v1, v2, v3, ... , vn.

Longitud de camino: número de arcos.

Camino simple: todos sus vértices, excepto tal vez el primero y el último son distintos.

Vértice adyacente: un nodo o vértice v es adyacente al nodo w si existe un arco de w a v.

Arista adyacente: dos aristas de un grafo son llamadas adyacentes si tienen un vértice en común.

Ciclo simple: es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice.

• Aristas paralelas: aristas con el mismo vértice inicial y terminal.
• Grafo cíclico: contiene por lo menos un ciclo.
• Grafo acíclico: no contiene ciclos.
• Grafo conexo: para cada par de nodos (v,w) existe un camino de v a w y de w a v.
• Grafo fuertemente conexo: para cada par de nodos (v,w) existen por lo menos dos caminos disjuntos de v a w y de w a v, de manera que no exista un vértice tal que al sacarlo el grafo resultante sea disconexo.
• Grafo completo: para cada par de nodos (v,w) existe una arista de v a w y de w a v.
• Grafo unilateralmente conexo: para cada par de nodos (v,w) de g hay un camino de v a w o un camino de w a v (esto tiene sentido sólo en el contexto de un grafo dirigido).
• Grafo pesado o etiquetado: sus aristas contienen datos. Una etiqueta puede ser un nombre, costo o un valor de cualquier tipo de dato. También a este grafo se lo denomina red de actividades, y el número asociado al arco se le denomina factor de peso.
• Longitud de camino con pesos: suma de los pesos de las aristas en el camino.
• Grado de salida de un nodo: es el número de arcos o aristas que empiezan en él.
• Grado de entrada de un nodo: es el número de arcos o aristas que terminan en él.
• Nodo fuente: tiene grado de salida positivo y un grado de entrada nulo.
• Nodo sumidero: tiene grado de salida nulo y un grado de entrada positivo.

En la mayoría de los casos los grafos son dispersos: cuanto mucho una arista entre un vértice y otro

1. E$\leq$#V$^{2}$, más aún: #E = O(#V).

Caso contrario se denominan densos.

Representación de los grafos

Representación por incidencia

Lista de incidencia

El grafo está representado por un arreglo de aristas, identificadas por un par de vértices, que son los que conecta esa arista.

Matriz de incidencia

El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado).

Representación por adyacencia

Listas de adyacencia

El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante.

Matriz de adyacencia

Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contiene un peso) si y solo si existe un arco que vaya del vértice i al vértice j. La inicialización llevaría un tiempo del O ( #(V$^{2}$)).

Algoritmos de optimización

Programación dinámica

Es aplicable cuando los subproblemas (obtenidos a partir de la técnica “dividir y conquistar”) no son independientes, sino que comparten subsubproblemas, cuyas soluciones óptimas sean parte de la solución óptima global.

Pasos a seguir:

1. Caracterizar la estructura de una solución óptima.
2. Definir recursivamente el valor de una solución.
3. Computar el valor de una solución óptima de forma ordenada.
4. Construir una solución óptima a partir de la información computada (este paso puede ser omitido si sólo se requiere el valor y no la solución; de ser realizado, generalmente debe guardarse información adicional).

Ejemplo: Multiplicación de cadena de matrices

Dada una cadena de matrices $[A_{1},A_{2},\ldots ,A_{n}]$, la tarea es obtener el producto $A_{1}\times A_{2}\times \ldots \times A_{n}$.

La cantidad de multiplicaciones necesarias para obtener el resultado de cada una de las multiplicaciones entre una matriz de $n\times m$ y otra de $m\times p$ está dada por:

$n\times m\times p$

Caracterizar la estructura de una solución óptima

Una solución óptima divide la cadena $[A_{1},A_{2},\ldots ,A_{n}]$ en dos subcadenas $[A_{1},A_{2},\ldots ,A_{k}];[A_{k+1},A_{k+2},\ldots ,A_{n}]$. Su costo será el costo de obtener $A_{1}\times A_{2}\times \ldots \times A_{k}$ más el costo de obtener $A_{k+1}\times A_{k+2}\times \ldots \times A_{n}$ más el de multiplicar los resultados entre sí. La solución óptima para la multiplicación de estas particiones es la solución óptima de cada una de las particiones. Habrá un $k$ para el cual la solución sea la solución global del problema, de manera que resolver el problema consistirá en encontrar ese $k$.

Definir recursivamente el valor de una solución

La función $m(i,j)$, que devuelve la mínima cantidad de operaciones para obtener el producto $A_{i}\times A_{2}\times \ldots \times A_{j}$ será:

$m(i,j)=$
 si $i==j$
  $0$
 sino
  $m(i,k)+m(k+1,j)+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})$

Con esta definición se puede escribir un algoritmo recursivo que resuelve el problema.

private Resultado m(int i, int j)
{
  Resultado resultado = new Resultado();
  if(i == j)
  {
    resultado.setValor(0);
    resultado.setK(i);
  }
  else
  {
    for(k=i, menor = $\infty$, mejorK = 0; k<j;k++)
    {
      valorActual = m(i, k) + m(k+1, j) + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
      if(menor > valorActual)
      {
        menor = valorActual;
        mejorK = k;
      }
    }
    resultado.setValor(menor);
    resultado.setK(mejorK);
  }
  return resultado;
}

Si se analiza la complejidad computacional de esta función, se verá que es igual de ineficiente que el método de fuerza bruta. La función será llamada muchas veces con los mismos valores, y deberá recalcularse cada una de esas veces. Una mejora del algoritmo podría valerse de una estructura auxiliar para guardar estos datos.

private Resultado m(int i, int j)
{
  if(calculados.contains(i, j)) return calculados.get(i, j);
  Resultado resultado = new Resultado();
  if(i == j)
  {
    resultado.setValor(0);
    resultado.setK(i);
  }
  else
  {
    for(k=i, menor = $\infty$, mejorK = 0; k<j;k++)
    {
      valorActual = m(i, k) + m(k+1, j) + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
      if(menor > valorActual)
      {
        menor = valorActual;
        mejorK = k;
      }
    }
    resultado.setValor(menor);
    resultado.setK(mejorK);
  }
  calculados.set(i, j, resultado);
  return resultado;
}

Computar el valor de una solución óptima de forma ordenada

En este punto tenemos una solución del problema que utiliza una estrategia de dividir y conquistar, de manera que la resolución del problema global consiste en resolver cada uno de los subproblemas, y además, utilizamos toda la información disponible para no repetir cálculos, entonces, ¿qué le falta a esta solución para ser "dinámica"?

La respuesta se encuentra en el orden en el cual se obtiene la información. Una solución como esta necesita de esa pregunta en la primera línea del método, acerca de si se ha calculado previamente el dato, porque no toma en cuenta para nada el orden en el cual se obtiene cada dato. Si podemos determinar qué datos se necesitan para obtener cuales otros, podríamos procurar obtener antes los primeros, y así poder evitar quedar en espera de que los datos necesarios se obtengan.

¿Cómo podemos hacer esto para este problema en particular? Puede servir de guía tratar de responder algunas preguntas:

• ¿Con qué información se cuenta al comienzo?
• ¿Qué información se puede generar directamente a partir de la información inicial?
• ¿Puede hallarse una regla para generar sucesivamente la información necesaria, desde la información inicial hasta la solución del problema?

Si se presta atención a la función que definimos en el primer punto:

$m(i,j)=$
 si $i==j$
  $0$
 sino
  $m(i,k)+m(k+1,j)+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})$

Se puede ver que se cuenta con el resultado de la función cuando la posición de la matriz de inicio de la cadena es igual a la de fin, que es 0. Para calcular la cantidad de operaciones que requerirá una cadena de dos matrices, se usarán los datos iniciales y las dimensiones de las matrices, que también son datos:

$m(i,k)+m(k+1,j)+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})=0+0+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})$

Para calcular la cantidad de operaciones que requerirá una cadena de tres matrices $A$, $B$ y $C$, $k$ puede estar en dos posiciones: $A\times (B\times C)$ ó $(A\times B)\times C$. Para calcular cualquiera de las dos opciones, deberá utilizarse un valor referente a una cadena de multiplicación de una matriz, uno referente a una cadena de dos matrices, y las dimensiones de las matrices. Sucesivamente, para optimizar cada una de las cadenas de multiplicación, se deberán utilizar los valores óptimos de todas las subcadenas, y esto define un orden posible para los cálculos:

Si calculamos sucesivamente los valores óptimos para las cadenas de $d$ matrices, comenzando desde $d=1$ hasta llegar a $d=n$, en cada uno de los pasos se deberá utilizar información previamente obtenida, es decir que ninguno de los cálculos deberá esperar por el resultado de otro.

//inicialización en 0 para i == j
for(i = 0; i < n; i++)
  calculados.set(i, i, new Resultado(i,0));

for(d = 1; d < n; d++)
//largo de la cadena de matrices
{
  for(i = 0, resultado = new Resultado(); i <= (n - d); i++)
  //inicio de cada una de las cadenas
  {
    for(k = i, j = (i + d), menor = $\infty$; k < (i + d); k++)
    //todos los k posibles, desde el principio hasta el fin de la cadena
    {
      valorActual = calculados.get(i, k).getValor() + calculados.get(k + 1, j).getValor() + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
      if (menor > valorActual)
      {
        menor = valorActual;
        resultado = new Resultado(k, valorActual);
      }
    }
    calculados.set(i, (i + d), resultado);
  }
}

Construir una solución óptima a partir de la información computada

en este punto podría parecer que sólo contamos con parte de la información que necesitamos para construir una respuesta completa: la cantidad mínima de operaciones y el $k$ para la última operación. Sin embargo, debe notarse que los $k$ para las subcadenas $[A_{1},A_{2},\ldots ,A_{k}]$ y $[A_{k+1},A_{k+2},\ldots ,A_{n}]$ se pueden obtener mediante:

calculados.get(i, k).getK()

y

calculados.get(k + 1, n).getK()

Y así sucesivamente se pueden encontrar los valores de $k$ que constituirán la solución completa, recorriendo el denominado 'camino hacia atrás'. Esto se puede hacer, porque en cada paso guardamos el valor de $k$ correspondiente.

Ejemplo: El problema del cambio mínimo

Dado un conjunto de valores de monedas, debe obtenerse la mínima cantidad de monedas que forme determinado monto.

Caracterizar la estructura de una solución óptima

Sea el monto $m$ de monedas, y suponer que uno de los tipos de monedas susceptibles de usar es la unidad, la solución óptima del problema debe ser alguna de las siguientes:

• Juntar por un lado una moneda, y por el otro $m-1$.
• Juntar por un lado dos monedas, y por el otro $m-2$.
• ...
• Juntar por un lado ${\frac {m}{2}}$ monedas, y por el otro ${\frac {m}{2}}$.

Entonces, habrá nuevamente un $k$ tal que juntar por un lado $k$ y por el otro $m-k$ sea la solución óptima del problema, y resolver el problema consistirá en encontrar sucesivamente ese $k$.

Definir recursivamente el valor de una solución

La función $m(t)$, que devuelve la mínima cantidad de monedas para obtener el monto $t$ será:

$m(t)=$
 si $t\in M$
  $1$
 sino
  $m(k)+m(t-k)$

Siendo $M$ el conjunto de monedas posibles.

Con esta definición se puede escribir un algoritmo recursivo que resuelve el problema.

private Resultado m(Integer t)
{
  Resultado resultado = new Resultado();
  if(monedas.contains(t))
  {
    resultado.setValor(1);
    resultado.setK(t);
  }
  else
  {
    for(k=1, menor = $\infty$, mejorK = 0; k < t; k++)
    {
      valorActual = m(k) + m(t-k);
      if(menor > valorActual)
      {
        menor = valorActual;
        mejorK = k;
      }
    }
    resultado.setValor(menor);
    resultado.setK(mejorK);
  }
  return resultado;
}

Obviaremos el paso trivial de utilizar una estructura auxiliar para guardar los datos ya obtenidos.

Computar el valor de una solución óptima de forma ordenada

Para calcular la cantidad de monedas que hacen falta para obtener el monto $t$, deberá contarse con el valor óptimo para todas las combinaciones de valores que suman $t$, que serán combinaciones de valores menores que $t$:

Si calculamos sucesivamente los valores óptimos para los montos menores que $t$, comenzando desde la unidad, en cada uno de los pasos se deberá utilizar información previamente obtenida.

//inicialización en 1 para los valores que tienen cambio exacto
for(Integer i: monedas)
  calculados.set(i.intValue(), new Resultado(i,1));

for(x = 1,resultado = new Resultado(); x < m; x++)
//monto a obtener
{
  for(k = 1, menor = x ; k < x; k++)
  //divisiones posibles de x
  {
    valorActual = calculados.get(k).getValor() + calculados.get(x-k).getValor();
    if (menor > valorActual)
    {
      menor = valorActual;
      resultado = new Resultado(k, valorActual);
    }
  }
  calculados.set(x, resultado);
}

Construir una solución óptima a partir de la información computada

Para construir la solución a partir de la información obtenida, se puede obtener el $k$ de l primer monto:

calculados.get(m).getK()

Y esto significará que la solución será dividir el monto en k y m - k. Luego tendremos que buscar el k óptimo para esos montos:

calculados.get(k).getK()

calculados.get(m - k).getK()

Y así sucesivamente, hasta obtener una a una las unidades necesarias, que irán incrementando la cuenta de cada uno de los tipos de moneda necesarios.

Algoritmos de búsqueda

El proceso de un Algoritmo de Búsqueda es la consecución de ubicar información en una colección de datos. Lo que interesa de su uso, es saber si un elemento pertenece o no a la colección; y en caso de pertenecer, saber el ÍNDICE DE LA LISTA en el cual está el elemento.

Introducción

Los algoritmos de búsqueda que se exponen a continuación se aplican a árboles. Como se verá, muchos problemas de optimización pueden modelarse de manera de generar un árbol cuyos nodos constituyen posibles soluciones o pasos intermedios a la solución del problema; cada uno de estos algoritmos define un orden en el cual se generarán los nodos del árbol, y una forma en la cual se encontrará la solución buscada.

Definiciones

Costo

Los algoritmos de optimización por búsqueda trabajan con el concepto de costo, que es la función que debe ser optimizada. Cada paso en el camino que constituye la solución óptima, tendrá asociado un costo en sí mismo, y el costo global será función de los costos de cada uno de esos pasos.

Criterio de parada

Es el criterio que se toma para decidir que la búsqueda ha llegado a su fin. En este punto se puede devolver una solución, o determinar que no hay solución posible.

Criterio de camino agotado

Es el criterio que se toma para decidir que la búsqueda desde el nodo actual no puede llevar a una solución, de manera que, de quedar otros caminos posibles, debería continuar por alguno de ellos.

Expansión de nodos repetidos

Frecuentemente, en los problemas que se modelan, es posible llegar a una solución posible o intermedia a través de varios caminos. Esto hace que un algoritmo de búsqueda pueda generar más de una vez el mismo nodo. Los problemas que devienen de la expansión reiterada de un mismo nodo van desde una ligera carga extra hasta la no convergencia del algoritmo, dependiendo de la naturaleza del problema y del algoritmo utilizado. Se debe evitar la expansión repetida, deberá guardarse pista de los nodos ya expandidos. En algunos casos, tales como una búsqueda en profundidad que genere un número limitado de nodos, pero que puedan repetirse, pueden generarse bucles en una rama, de manera que para evitarlos, sólo se debe guardar pista de los nodos expandidos en la rama atual.

Aristas de costo negativo

Una arista de costo negativo, en la semántica del problema, significará que uno de los pasos posibles en el camino de una solución, contribuye mejorar solución. Esto es un problema para los algoritmos que evitan caminos del árbol de búsqueda basándose en el costo que tiene alcanzar cada nodo, porque esto no prevé que en futuros pasos la función costo puede mejorar.

Búsqueda en anchura

Definición

Un algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente.

Complejidad computacional

Si la solución se encuentra en el nivel n, y la cantidad máxima de hijos de un nodo es i, habrá que expandir, en el peor de los casos, la cantidad de nodos de un árbol de orden i y de altura n:

$C={\cfrac {i^{n+1}-1}{i-1}}$

Por lo tanto, tanto el tiempo de procesamiento como el requerimiento de memoria tendrán un orden exponencial, tanto si evita o no expansiones repetidas.

Ventajas y desventajas

Expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.

La desventaja principal es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros i y n del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables.

Búsqueda en profundidad

Definición

Un algoritmo de búsqueda en profundidad recorre todos los nodos de un árbol de manera ordenada, pero no uniforme. Consiste en ir expandiendo cada uno de los nodos a medida que los encuentra, empezando siempre por el primer nodo hijo no visitado del nodo actual; cuando ya no quedan más nodos hijos que visitar en el actual, regresa (backtracking), y el padre del nodo pasa a ser el nodo actual. El criterio de camino agotado debe ser elegido cuidadosamente, de manera de evitar la expansión indefinida de nodos. Asimismo, para garantizar la convergencia, en muchos casos debe evitarse la expansión de nodos repetidos, al menos en un mismo camino.

Ventajas y desventajas

Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización. Esto es, si se ha encontrado una solución posible con determinada valoración, no se admitirá expandir nodos con una valoración peor, y así el algoritmo puede ir eliminando ramas sin la carga de procesamiento de recorrerlas. Además, el requerimiento de memoria es limitado, aun si se garantiza que no cicle, ya que sólo hace falta guardar los datos de la rama actual.

Complejidad computacional

La cantidad mínima de nodos a ser expandidos para garantizar la mejor solución es la misma que en la búsqueda en anchura, es decir

$C={\cfrac {i^{n+1}-1}{i-1}}$

La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayan expandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual se encuentra la solución más costosa de todas las ramas.

Búsqueda en profundidad iterativa

Definición

Un algoritmo de búsqueda en profundidad iterativa recorre los nodos de un árbol en profundidad, pero con un valor de profundidad restringido, que aumentará en cada iteración. Esto evita el riesgo de internarse indefinidamente en una rama no finita, y evita también la necesidad de guardar pista de todos los nodos expandidos (sólo hace falta guardar los de la rama actual).

Ventajas y desventajas

La búsqueda en profundidad iterativa aprovecha ventajas de la búsqueda en anchura y de la búsqueda en profundidad:

• El requerimiento limitado de memoria.
• La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna.

Complejidad computacional

La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta una profundidad $d$ (profundidad de la solución con menor profundidad). Resolviendo la serie, la complejidad resulta de $O\left(b^{d}\right)$. En tanto, la complejidad espacial está determinada por la profundidad de la solución, ya que sólo deben guardarse los nodos del camino actual y sus hermanos, que serán $b.d$, de manera que la complejidad espacial será de $O\left(b.d\right)$

Búsqueda de costo fijo

Definición

Un algoritmo de búsqueda de costo fijo tiene asociada una función de costo que se aplica cada nodo, que representará el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo en cuestión. El algoritmo de optimización deberá obtener el mejor camino entre el nodo inicial y un nodo caracterizado como el nodo de destino. En cada iteración, la expansión a realizar será la del nodo cuyo costo resulte menor, excepto si éste fuera una solución, en cuyo caso, se tratará de la solución óptima, por no haber ningún nodo con menor costo que pueda expandirse para encontrar una solución mejor. Si el costo de los movimientos es uniforme, la búsqueda seguirá el mismo orden de expansiones que la búsqueda en anchura ^[1].

La función de costo

La función de costo de un nodo representa el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo. Para el nodo inicial deberá valer 0.

Complejidad computacional

La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta un costo de $C^{*}$ (costo óptimo), es decir, hasta una profundidad de ${\frac {C^{*}}{\epsilon }}$, siendo $\epsilon$ el costo más pequeño aplicable a una acción. Resolviendo la serie, la complejidad resulta de $O\left(b^{\frac {C^{*}}{\epsilon }}\right)$. La complejidad espacial será también de $O\left(b^{\frac {C^{*}}{\epsilon }}\right)$, ya que deben almacenarse al menos todos los nodos de la frontera.

Búsqueda heurística

Definición

El nodo que más conviene expandir es el nodo a través del cual pasa el camino con menor costo. Sería útil contar con la información del costo total del camino que significaría atravesar cada nodo. La búsqueda de costo fijo estima este valor con el costo parcial de llegar a este nodo. En muchos casos, esto no es suficiente. No se puede contar con el valor exacto, esto implicaría tener el problema resuelto. Lo que puede hacerse es estimar el costo desde el nodo actual hasta el nodo final, de manera de expandir primero el nodo a través del cual se estime que se llegará a la solución con costo óptimo.

La función de costo

La función de costo es equivalente a la función de costo en la búsqueda de costo fijo.

La función heurística

La función heurística debe estimar la función de costo desde el nodo actual hasta el nodo objetivo. Debe ser optimista, ya que si la estimación fuera superior al valor real, un nodo que llega a la solución óptima puede quedar excluido de la búsqueda. Mientras más se ajuste la heurística al valor real, se expandirán menos nodos innecesariamente.

Complejidad computacional

Para la búsqueda A*, la complejidad temporal y espacial para el caso peor ($h()=cte.=0$) es la misma que la complejidad de la búsqueda de costo uniforme; esto es evidente ya que en el caso peor, la función heurística devuelve siempre 0, haciendo que la búsqueda sea en todo sentido igual a la búsqueda de costo fijo.

Implementación

El algoritmo de búsqueda genérico

Para implementar tanto la búsqueda en profundidad, como la búsqueda en anchura, la de costo fijo y la heurística, puede utilizarse un algoritmo genérico:

1. Colocar el nodo inicial en la lista abierta.
2. Elegir el próximo elemento de la lista abierta a extraer, y realizar la extracción.
3. Si se corresponde con un estado final, devolver el elemento o la secuencia de acciones correspondiente, si no, continuar.
4. Explandirlo, colocando los descendientes que correspondan en la lista abierta.
5. Colocarlo en la lista cerrada y volver a 2.

De las características de la estructura de datos utilizada como lista abierta, dependerán las características del algoritmo:

Si la estructura es una pila, el algoritmo elegirá siempre el último nodo generado, y a partir de ese nodo generará nuevos nodos, que serán agregados a la pila, y el primero será elegido, y así sucesivamente; es decir que la búsqueda será en profundidad.

Si la estructura es una cola, los nodos se expandirán en el orden que se generen, de manera que todos los nodos de un nivel deberán ser expandidos antes de comenzar a expandir los del siguiente; la búsqueda será en anchura.

Si la estructura es una cola de prioridad, y la función de ordenamiento es la función costo, de manera que el elemento elegido sea siempre el de menor costo, la búsqueda será de costo uniforme. Si la función de ordenamiento combina la función de costo con una función heurística, la búsqueda será heurística.

---

^ Para el caso de la búsqueda de costo fijo, nótese que si se agrega a la lista abierta un nodo correspondiente a un estado que ya está allí, pero con un valor de costo diferente, no habrán expansiones repetidas, ya que una vez en la lista cerrada, cuando se tome de la lista abierta el nodo con estado repetido, será siempre con un mayor valor de costo, y se descartará.

Algoritmos de ordenamiento

Un algoritmo de ordenamiento recibe como entrada una secuencia de elementos, y devuelve una secuencia con los mismos elementos, en la cual el orden relativo de cada elemento respecto de los demás respeta un criterio dado.

Quicksort

Quicksort es un algoritmo de ordenamiento que utiliza la técnica 'divide y vencerás'. Consiste en dividir la secuencia a ser ordenada en dos partes, de tal manera que cada uno de los elementos de una de las partes sea mayor o igual a todos los elementos de la segunda parte. Cada una de las partes se divide y se le aplica a su vez este procedimiento recursivamente, hasta llegar a las secuencias unitarias. Al finalizar este procedimiento, la secuencia completa queda ordenada.

Algoritmo

1. Elegir un elemento de la secuencia, llamado pivote.
2. Reordenar la secuencia de tal manera que los elementos menores que el pivote aparezcan primero, y los mayores después (el orden de los elementos iguales al pivote no importa).
3. Ordenar recursivamente las subsecuencias.

El caso base de esta recursión son las secuencias de un elemento.

El algoritmo se puede expresar de la siguiente forma:

 public static Collection quickSort(Collection secuencia)
 {  
   Collection salida, menores, mayores, iguales;
   if(secuencia.size() == 1) return;
   Iterator iteradorSecuencia = secuencia.iterator();
   Comparable pivote = obtenerPivote(secuencia);
   while (iteradorSecuencia.hasNext())
    {
     Comparable elementoActual=(Comparable) iteradorSecuencia.next();
     if(pivote.compareTo(elementoActual)<0)
       mayores.add(elementoActual);
     else if (pivote.compareTo(elementoActual)>0)
       menores.add(elementoActual);
     else
       iguales.add(elementoActual);
    }
    mayores = quickSort(mayores);
    menores = quickSort(menores);
    salida.addAll(menores);
    salida.addAll(iguales);
    salida.addAll(mayores);
    return salida;
 }

Versión de ordenamiento sin espacio de almacenamiento adicional

La desventaja de la versión precedente es que requiere un almacenamiento extra de $\Omega (n)$. Esto puede evitarse ordenando sobre una misma secuencia:

 public static void quickSort(List secuencia, int indiceInferior, int indiceSuperior)
 {
   int i=indiceInferior, j = indiceSuperior;
   if(indiceInferior == indiceSuperior) return;
   Comparable pivote = obtenerPivote(secuencia);
   for(;i!=j;)
   {
     for(;((Comparable)secuencia.get(i)).compareTo(pivote)<0;i++);
     for(;((Comparable)secuencia.get(j)).compareTo(pivote)<0;j--);
     intercambiar(secuencia,i,j);
     i++;
     j++;
   }
   quickSort(secuencia, indiceInferior, i);
   quickSort(secuencia, i+1, indiceSuperior);
 }
 
  public static List quickSort(List secuencia)
  {
    quickSort(secuencia,0,secuencia.size());
    return secuencia;
  }

Análisis

En el mejor de los casos, en cada paso se dividirá la secuencia en dos partes, de manera que la profundidad del árbol de llamadas iterativas será $\log _{2}n$, y como la cantidad de elementos a ser recorridos en cada nivel del árbol es $n$, el orden de la complejidad del algoritmo será $\Omega (n\log n)$.

En el peor caso, en cada paso se produce una partición completamente desbalanceada, es decir, queda un solo elemento de un lado, y el resto del otro lado, con lo que las iteraciones seguirán la siguientes reglas:

• En el paso número $i$ se debe iterar sobre $(n-i)$ elementos.
• Deberán realizarse $n$ pasos.

Esto requerirá ${\frac {n^{2}+n}{2}}$ iteraciones: el orden de la complejidad del algoritmo será $O(n^{2})$.

Como para una distribución uniforme de los datos, el caso se asemejará mucho más al primero, se dice que el orden de la complejidad promedio del algoritmo es $\Theta (n\log n)$.