Arboles

1. Concepto: 

 Estructura de datos no lineal para organización de información por niveles.

2. Utilidad:

 Organización por jerarquía (diferenciación entre elementos mayores y menores).

3. Aplicaciones:

Estructura organizacionales, genealogía, directorias, expresiones aritméticas, búsqueda y ordenadamente.

4. Terminología:

                     

Nodo: cada componente de un árbol, la comunicación es descendente, raíz hacia las hojas.

Tipos

Implementacion 

ÁRBOLES BINARIOS

1. Concepto: 

 Máximo dos hijos por nodo.            

2. Terminología:

Completo: todos los nodos tienen dos o cero hijos.

Balanceado: la diferencia entre las alturas de los subárboles para todos los nodos es de cero o uno.

Degenerado: todos los nodos solo tienen un descendiente excepto la hoja.

Lleno: todos los niveles tienen el máximo de nodos 2^h-1.

Implementación:

Recorrido

REFLEXIÓN: Es posible definir un árbol binario como un conjunto de finitos elementos, el cual consta de una raíz la cual esta conformado por dos subárboles: derecho e izquierdo.

ÁRBOL DE EXPRESIONES

Es un árbol binario completo, que se utiliza para representar y evaluar expresiones aritméticas donde las hojas son los operandos y el resto de nodos los operadores.

REFLEXIÓN: un árbol de expresión tiene una funcionalidad similar a la de una aplicación aritmética de pilas ya que ordenan los elementos teniendo en cuenta las prioridades. 

Nota: el recorrido en un árbol de expresión el preorden produce la expresión prefija, el inorden la infija y el posorden posfija 

ÁRBOLES ABB: ÁRBOL BINARIO DE BÚSQUEDA

1.CONCEPTO:

Contienen un algoritmo que permite ordenar y hacer más eficiente el proceso de búsqueda que en las estructuras vistas anteriormente.

Ventajas: 

- Mayor eficiencia.

- Menor número de comparaciones al buscar un elemento.

-El proceso de búsqueda a medida que se avanza se hace un descarte del 50%.

CRITERIO:

Para todos los nodos, los datos en el subárbol izquierdo deben ser menores y los del subárbol derecho mayores.

OPERACIONES EN ABB:

INSERCIÓN: se debe buscar el sitio de inserción, verificar que no exista el elemento.

ELIMINACIÓN: Buscar y verificar que exista el elemento.

- Si es una hoja solo se debe suprimir.

- Si es un nodo con un subárbol, es reemplazado por su descendiente inmediato.

- Si es un nodo con dos subárboles, se reemplaza con el nodo más a la izquierda del subárbol derecho o con el nodo más a la derecha del subárbol izquierdo.

BUSCAR: Inicia en la raíz comparando el dato si es mayor se desplaza a la derecha si es menor a la izquierda y si es igual el elemento ha sido encontrado.

REFLEXIÓN: Son árboles binarios en los que se cumple que cada nodo, el valor del elemento de la raíz del subárbol izquierdo es menor que el valor del elemento del nodo y también que el valor del elemento de la raíz del subárbol derecho es mayor.

ÁRBOLES BINARIOS BALANCEADOS (AVL)

Insertar: Se aplica inicialmente la misma de los ABB pero adicionalmente se calcula el FE en la rama de inserción, comenzando por la hoja y subimos a la raíz, si se encuentra en un nodo "FE=0" o llegamos a la raíz con FE normal en balance paramos, si un nodo presenta FE fuera de rango de balance, se produce una reestructuración del árbol dependiendo de los siguientes casos.

Eliminar: se aplica la misma regla  ABB pero adicionalmente se calcula el FE en la rama de eliminación e igual que en la inserción si se presenta un caso de rotación se hace la respectiva reestructuración del árbol.

REFLEXIÓN: En conclusión es posible decir que un árbol AVL es aquel que tiene como condición  de que la diferencia entre las alturas de sus subárboles debe ser máximo de 1.

Además el factor de equilibro determina en que momento se debe realizar una reestructuración, es decir si es diferente de -1, 0 ó 1.

Recursividad

Recursividad 

1. Definicion: propiedad de las funciones (metodos) de autollamarse, se constituye una alternativa de los procesos iterativos (for, while, do while).

2. Utilidad: cuando el proceso o solucion iterativa es compleja.

3. Aplicaciones: recorrido de estructuras no lineales, en algunas formulas matematicas.

4.    Recursividad Vs Iteracion.

Recursividad	Iteración
métodos	ciclos
Reducción de código máxima	Reducción de código mínima
Lógica simple	Puede ser muy complejo
Considerable consumo de memoria	Consumo mínimo de memoria

Apreciacion importante y reflexion.

La recursividad consume mas memoria por que en cada autollamado hace una copia de toda la funcion y es guardada el la pila para llamado a subprogramas.

Tener muy en cuenta que siempre que se pueda usar un algoritmo no recursivo resultaria mejor ya que se ejecuta mas rapidamente y ocupa menos memoria ram 

Colas

Concepto: 

es una regla que se aplica a una estructura lineal (arreglos y listas enlazadas) para que tengan un comportamiento FIFO primer elemento en almacenarse , primero en procesarse. 

Utilidad:

siempre que los recursos de procesamiento sean menores a las demandas de su uso.

Aplicaciones:

cola de procesos, de impresión, de simulación.

Operaciones: 

  Poner, quitar, vacía, llena.

Implementación(arreglos,Nodo/ listas).

Implemetacion 

class ColaVector <T>

poner { fin ++;

             v [ fin ] = dato;

quitar { dato = v [ frente];

              frente ++;

vacía{ frente = = -1;

llena{ fin = = max - 1;

FUNCIONES DE COLAS 

COLAS CIRCULARES

Es una estructura de datos, donde los elementos se encuentran ubicados de manera circular o en forma de anillo (Gráfico).

Al momento de añadir un nuevo elemento, esto solo puede realizar por el primer elemento (indice 0) ya que es una posición distinguida. A continuación una gráfica que representa la alteración de una cola circular, al momento de añadir 3 elementos:

REFLEXIÓN

se obtuvo habilidad para realizar la clase ColaVector porque al conocer la clase pila se facilito la enseñanza de esta nueva estructura de datos, y conocer las operaciones básicas que en ella se utilizan.

 Las colas circulares permiten la insercion y eliminacion de elementos solo por su inicio, mientras que las bicolas lo permiten por ambos extremos y son direccionados  por 2 indices al momento de representarlo en un arreglo.

Parcial Nº2

Copia De Una Pila

Segundo Punto

Aplicacion de Pila. Expresiones Aritmeticas

Aplicación de Pila. Expresiones Aritméticas

Una de las aplicaciones de pila son las expresiones aritméticas  estas facilitan la evaluación quitando paréntesis y ordenando el orden de operación según  prioridad al hacer la evaluación. Existen expresiones Aritméticas como:

infija: son las expresiones que tienen el operador en el medio.

prefija: son las que tienen el operadores antes.

posfija: son las que tienen el operadores después.

Ejemplos

Pilas y Colas

PILA

En la clase, aprendí sobre lo que era una pila, es una regla que se aplica a las estructuras de datos lineales, restringiendo sus operaciones a LIFO (Last In First Out ) ultimo elemento almacenado,  primero en ser procesado.

Utilidades: Es utilizado cuando se quiere invertir, retroceder en un proceso donde quedan tareas pendientes por completar.

Aplicaciones:  Llamadas a subprogramas, Evaluación de expresiones aritméticas, entre otras.

 Operaciones: Se dividen en dos grupos.

  Principales: operaciones como poner, quitar.

  Auxiliares: operaciones como cima,vacía,llena.

Implementacion de Pila.

1. Arreglos: Para realizar la implementacion de una pila por medio de arreglos es necesario definir tres variables las cuales son el vector de clase T (Genérico) y dos variables de clase int las cuales son el máximo y  tope. Se puede realizar operaciones como, poner, quitar, cima, vacía, llena. A continuación la clase PilaVector.

public class Pila <T>{
private T v[];
private int tope, max;
public Pila(){
max = 100;
v = (T[]) new Object[max];
tope = -1;
}
public Pila(int max){
this.max = max;
v = (T[]) new Object[max];
tope = -1;
}
public boolean vacia(){
return tope == -1;
}
public boolean llena(){
return tope == max-1;
}
public void poner(T dato){
if(!llena())
v[++tope] = dato;
else
System.out.println("La Pila Esta Llena");
}
public T quitar(){
T dato = null;
if(!vacia())
dato = v[tope--];
else
System.out.println("La Pila Esta Vacía");
return dato;
}
public T cima(){
if(!vacia())
return v[tope];
else
return null;
}

2. Nodos: Para la implementacion con Nodos se pueden realizar los siguientes métodos.

poner: tope = new Nodo(dato,tope);

quitar: dato = tope.getDato();

  tope= tope.getSig();

cima: dato=tope.getDato();

vacia: tope==null;

CLASE PilaVector y PilaNodo

Class PilaVector <T>
Poner {tope ++;
v[tope]= dato;
Quitar{ dato = v[tope];
        tope--;
Cima { dato =v[tope];
Vacia{tope ==-1;
Llena{tope=max -1;

Class PilaNodo
Poner {tope =new Nodo(dato,tope);
Quitar{ dato = tope.getDato();
        tope =tope.getSig();
Cima { dato =tope.getDato();
Vacia{tope ==null;

Apreciaciones importantes y reflexión: 

Aprendimos en la clase vista lo forma correcta de hacer que un vector se comporte como una pila, y resulta la clase mas funcional porque sirve para cualquier tipo de dato que se quiera guardar.

Parcial

PARCIAL PRIMER CORTE
SOLUCIÓN PRIMER PUNTO

Segundo punto

RetroAlimentacion Parcial
PRIMER PUNTO

SEGUNDO PUNTO

Operaciones entre listas enlazadas

Apreciaciones importantes y reflexión:

Estas instrucciones que se expuso anteriormente fueron de vital importancia para conocer mas sobre la clase Nodo y NodoDoble, saber que validación son las necesarias para que estas instrucciones puedan funcionar correctamente.

Luis Joya, Estudiante Tecnologico Comfenalco, Estructura de Datos.... Todos los derechos reservados ©2014