|
== Contenido ==
= Estructuras lineales =
== 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:
<li>Lineal: si n ≥ 1, <math>a_{1}</math> es el primer elemento y <math>a_{n}</math> el último, <math>a_{i}</math> precede a <math>a_{i+1}</math> y sucede a <math>a_{i-1}</math>. Sus elementos están ordenados por sus posiciones.
<li>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.
====== 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 =====
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.
# [[/Estructuras lineales/]]
=Árboles=
# [[/Árboles/]]
<!-- Faltan imágenes, ejemplos y Apéndices y aclaraciones-->
# [[/Colas de prioridad y montones/]]
Árbol: estructura no lineal y dinámica de datos.
# [[/Tablas Hash/]]
Dinámica: puede cambiar durante la ejecución de un programa.
# [[/Grafos/]]
No lineal: a cada elemento del árbol pueden seguirle varios elementos.
# [[/Algoritmos de búsqueda/]]
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:
<li>Se distingue un nodo raíz (no tiene padre).
<li>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.
<li>Hay un único camino desde la raíz hasta cada nodo. La 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 <math>T_{1}</math>, <math>T_{2}</math>,…, <math>T_{n}</math>, cada una de cuyas raíces está conectada por medio de una arista con la raíz.
==Definiciones==
<li>Los nodos que no tienen hijos se denominan hojas.
<li>Un árbol con N nodos debe tener (N-1) aristas.
<li>La profundidad de la raíz es 0 y la de cualquier nodo es la de su padre más 1.
<li>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.
<li>Los nodos que tienen el mismo padre son hermanos.
<li>Si hay un camino del nodo u al nodo v, u es ascendiente de v y v es descendiente de u. Si u <math>\neq</math> v son propios.
<li>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==
<li>Insertar
<li>Buscar
<li>Eliminar
<li>Ir a la raíz
<li>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:
<li>Todos los valores de los nodos del subárbol izquierdo de A deben ser menores al valor del nodo A.
<li>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” ====
public boolean 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:
<li>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().
<li>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.
<li>Un hueco dejado por un nodo promovido también puede pensarse como una eliminación.
===Á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, 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:
<li>Encontrar un nodo con una clave dada.
<li>Insertar un nodo con una clave dada.
<li>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:
<li>Agregar el nodo como en un árbol binario de búsqueda.
<li>En el regreso por el camino de búsqueda se comprueba el FE de los nodos.
<li>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:
#Una inserción en el subárbol izquierdo del hijo izquierdo de X.
#Una inserción en el subárbol derecho del hijo izquierdo de X.
#Una inserción en el subárbol izquierdo del hijo derecho de X.
#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:
<li>Suprimir el nodo como en un árbol binario de búsqueda.
<li>En el regreso por el camino de supresión se comprueba el FE de los nodos.
<li>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á:
<math>h \leq 2 log_{2}(n+1)</math>
=====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 <math>h \leq 2 log_{2}(n+1)</math>. 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 es 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, <math>log_{2} N</math>, la altura de un árbol M-ario completo es, más o menos, <math>log_{M} N</math>.
Un B-árbol de orden M es un árbol M-ario que verifica:
<li>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.
<li>La página raíz, o es una hoja o tiene entre 2 y M descendientes.
<li>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:
<li><math> k_{i}< x < k_{i+1}</math> para 1 ≤i < n. La búsqueda continúa en la página <math> r_{i}</math>.
<li><math> k_{n}< x</math>. La búsqueda continúa en la página <math> r_{n}</math>.
<li><math>x< k_{1}</math>. La búsqueda continúa en la página<math> r_{0}</math>.
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:
<li>Se inserta en forma secuencial la clave.
Si la cantidad de elementos es 2n:
<li>Los 2n+1 elementos se dividen en dos páginas, excluyendo la clave del medio.
<li>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:
<li>Sólo los nodos hoja apuntan a los registros o cubetas del fichero.
<li>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 <math>k_{i}</math> más pequeño mayor que la clave x.
La búsqueda sigue por el puntero <math>p_{i}</math> 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.
===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.
=Colas de prioridad y montones=
<!-- Faltan imágenes y ejemplos -->
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:
<li>Es completo, con la excepción del nivel inferior, que debe llenarse de izquierda a derecha.
<li>Las hojas están en dos niveles adyacentes.
<li>Para cada nodo X con padre P, se cumple que el dato en P es mayor o igual que el dato en X.
Ventajas:
<li>Soporta las operaciones insertar y suprimir en tiempo O(log N) en el caso peor.
<li>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:
<li>Hijo izquierdo: posición 2i,
<li>Hijo derecho: posición 2i +1
<li>Padre: posición i/2 (parte entera)
Se necesita mantener un entero que indique cuántos nodos hay actualmente en el árbol.
<!-- falta demostración -->
===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 2k 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:
<li>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.
<li>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, <math>2^{3} + 2^{2} + 2^{0}</math>, 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:
<li>Insertar un nuevo elemento
<li>Encontrar el elemento con mayor prioridad
<li>Eliminar el elemento con mayor prioridad
<li>Incrementar la prioridad de un elemento
<li>Eliminar un elemento cualquiera
<li>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=
<!-- Faltan gráficos -->
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". <math>128^3</math> + "o". <math>128^2</math> + "l" . <math>128^1</math> + "a" . <math>128^0</math> = 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; i < clave.length (); index ++)
valorHash = (valorHash * 128 + clave.charAt(i))
% 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 <math>\frac{1}{1- k}</math>. 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 <math>\frac{1}{p}</math> 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 <math>\frac{1}{2} (1 + \frac{1}{(1- k)^2}) </math>.
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: <math>H + 1^2; H + 2^2; H + 3^2;.....; H + i^2</math>
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. 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=
<!-- Falta completar -->
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 ==
<li>Camino: secuencia de vértices v1, v2, v3, ... , vn.
<li>Longitud de camino: número de arcos.
<li>Camino simple: todos sus vértices, excepto tal vez el primero y el último son distintos.
<li>Vértice adyacente: un nodo o vértice v es adyacente al nodo w si existe un arco de w a v.
<li>Arista adyacente: dos aristas de un grafo son llamadas adyacentes si tienen un vértice en común.
<li>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
#E<math>\leq</math>#V<math>^2</math>, 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 de pares 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<math>^2</math>)).
= 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.
=== 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 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.
== Complejidad computacional ==
= 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:
<math>C = \cfrac{i^{n+1} - 1}{i - 1} </math>
= Búsqueda en profundidad iterativa =
= Búsqueda de costo fijo =
== Definición ==
== Complejidad computacional ==
== La función de costo ==
= Búsqueda heurística =
== Definición ==
== Complejidad computacional ==
== La función de costo ==
== La función heurística ==
[[Categoría:Ingenierías]]
| 