Conceptos Fundamentales

Inserción por la Cabeza

• Creamos el nuevo nodo (reservar memoria).
• Almacenar el dato en el campo correspondiente (datos).
• Como el nuevo nodo será el primero, su campo enlace apuntará al hasta
  ahora primer nodo.

• El enlace externo (lista), deberá apuntar ahora al nuevo nodo.

Inserción por el Final

• Creamos el nuevo nodo (reservar memoria).
• Introducimos los nuevos datos en el campo de datos.
• Se asigna NIL a su campo enlace (ya que será el último).
• Iniciamos el puntero auxiliar Actual para que apunte al primer elemento de la lista.
• Hacemos avanzar este puntero hasta que alcance el final.
• Realizamos el enlace entre el último elemento de la lista y el nuevo nodo.

Suprimir por la Cabeza

• Almacenamos la dirección del primer elemento, apuntando por la variable lista, en un puntero auxiliar (actual), actual:=lista
• Asignamos el parámetro formal dato, el valor almacenado en el elemento auxiliar.
• Se realiza la asignación de la lista al nuevo primer elemento (lista:=lista.enlace)
• Se libera la memoria del nodo que ya no pertenece a la lista.

Suprimir por el Final

• Iniciamos los punteros.
• Recorrido de la lista hasta alcanzar el final.
• Recuperamos el dato almacenado en el último nodo.
• Eliminamos el nodo y marcación del nuevo último nodo.
• Liberamos la memoria del nodo.

Clasificacion en la Memoria Principal

Clasificación por Inserción Directa

• Tomar un elemento en la posición 'i' (i = 2, 3, 4, 5, ...)
• Buscar si hay un lugar en las posiciones anteriores (parte ordenada).
• Mover hacia la derecha los restantes.
• Insertarlo.

Compara 1 y corre, compara 2 y corre, compara 3 y ...

Clasificación por Inserción Binaria

• Tomar un elemento de la posición 'i'.
• Buscar dicotómicamente su lugar en las posiciones anteriores.
• Mover hacia la derecha los restantes.
• Insertarlo.

Cogemos el elemento central de la parte ordenada y se compara con el elemento a insertar. Si es mayor se descarta la parte izquierda, si no, al contrario.

Clasificación por Selección Directa

• Selecciona el elemento menor de la parte del arregle no ordenada.
• Colocarlo en la primera posición de la parte no ordenada del arreglo.

Buscas el pequeño y lo cambias

Clasificación por Intercambio Directo o Burbuja

• Se comparan pares de elementos contiguos y se intercambian si estas desordenados.

Clasificación por Sacudida o Vibración

• Mejora el método de la clasificación por burbuja alternando la dirección de pases consecutivos.
• El segundo pase comienza en las posiciones finales y se recorre en sentido inverso al anterior.

Inserción por Incremento Decreciente (SHELL)

• Eliges un rango y vas disminuyéndolo hasta que al final terminará con la inserción directa

Clasificación por Partición (Quick Sort)

• Elegimos un valor al azar (pivote), se recorre todo el arreglo desde la izquierda hasta encontrar una llave mayor que el pivote, y desde la derecha hasta encontrar un menor.
• Se intercambian y se repite el proceso hasta que los índices de incremento y decremento se cruce. Así tendremos las particiones menores que el pivote a la izquierda y mayores que el pivote a la derecha.
• Después 'partimos' y a ordenar de la misma forma.

Clasificacion en la Memoria Secundaria

Mezcla Directa

• Tomamos como fuente la secuencia original C1.
• Dividimos la fuente en dos mitades, en las cintas de destino C2 y C3.
• Mezclamos C2 y C3 combinando cada elemento accesible en pares ordenados en C1.
• Repetimos el proceso, se obtienen un cinta con cuádruplos ordenados.
• Repetimos el proceso hasta que toda la cinta este ordenada.

Clasificación Polifásica

• ver pag. 121. libro
• C5 (n+1)= C1 (n)
• C4 (n+1)= C1 (n) + C5 (n)
• C3 (n+1)= C1 (n) + C4 (n)
• C2 (n+1)= C1 (n) + C3 (n)
• C1 (n+1)= C1 (n) + C2 (n)

Arboles

Árboles Perfectamente Balanceados

Es aquel en el que para cada nodo en sus subárboles derecho e izquierdo difieren como máximo en 1.

Si conocemos los nodos (teórico):

Si no tenemos ni idea de la colocación de los nodos; se colocan de derecha a izquierda.

Árboles Binarios Ordenados según el Recorrido
Es aquel que para cada nodo se visita el nodo, su subárbol izquierdo y derecho en un orden establecido.

• Preorden: Visitar nodo antes que los subárboles.
• En orden: Visitar nodo después de un subárbol y antes que otro.
• Postorden: Visitar nodo después de los subárboles.

Árboles de Búsqueda Binarios
Es un árbol binario en el que dadas dos condiciones mutuamente excluyentes para cada nodo, todas las llaves de su subárbol izquierdo satisfacen una condición y todas las de su subárbol derecho la otra.

• Inserción: Se consulta si el dato es mayor o menor que la llave, decidiendo así si se prosigue la búsqueda por la izquierda o por la derecha. El procedimiento termina cuando se alcanza el puntero NIL, ya que esto querrá decir que el elemento no se ha encontrado y hay que insertarlo.
• Eliminación: Sustituir el nodo eliminado por el mayor menor, o sustituir el nodo eliminado por el menor mayor.

Árboles de Búsqueda Balanceados (AVL)
Todos los árboles perfectamente balanceados son AVL.

El árbol AVL cumple que en cada nodo las alturas de sus 2 subárboles difieren como máximo en 1

• Inserción en árboles AVL: Al insertar un nuevo nodo, hay que tener en cuenta el rebalanceo RR, RL, LR, LL
• Eliminación en árboles AVL: Se eliminan igual que los arboles binarios, pero con una diferencia, tenemos que hacer rebalanceo.

Arboles B

Un árbol B de orden 'n' es aquel árbol de búsqueda que satisface las siguientes propiedades:

• Cada página contiene como máximo '2n' llaves.
• Cada página contiene como mínimo 'n' llaves, excepto la raíz que puede contener sólo una
• Cada página o es una página de hoja o tiene 'm+1' descendientes, siendo 'm' el número de llaves en esta página.
• Todas las páginas de hoja aparecen al mismo nivel.

Búsqueda
La búsqueda se realiza con los siguientes criterios:

• Si el argumento de búsqueda se encuentra entre dos llaves de la página, entonces la búsqueda sigue en la página apuntada por el puntero entre ellas.
• Si el argumento de búsqueda es mayor que la última llave de la página, entonces se sigue la búsqueda en la página apuntada por el último apuntador.
• Si el argumento de búsqueda es menor que la primera llave de la página, entonces se sigue la búsqueda en la página apuntada por el primer apuntador.
• Si en cualquier caso el apuntador a la página en la que hay que seguir la búsqueda es NIL entonces el argumento de búsqueda 'x' no está en el árbol y finaliza la búsqueda.

Inserción
Se realiza buscando el lugar donde debe insertarse de la misma manera en que se realiza la operación de búsqueda. Localizada dicha posición si la página correspondiente tiene 'm>2n' llaves se inserta en ella en la posición dada por el criterio de búsqueda, pero si la página está llena (m=2n) entonces el árbol debe reorganizarse.

• La página se divide en dos nuevas páginas.
• La llave que se encontraba en la mitad, se sube en un nivel colocándola en la página madre. A la hora de determinar la llave central se tiene en cuenta también la nueva llave que se pretende insertar.
• Las páginas que se encontraban a la izquierda se distribuyen en la página nueva apuntada por la izquierda de la llave mitad y las que se encontraban a la derecha se distribuyen en la página nueva apuntada por la derecha de la llave mitad.

Eliminación
Debes tener en cuanta la subocupación y la sobreocupación.