Arboles Binarios De Busqueda Balanceados (AVL) (4 - junio - 2015)

Proponen un algoritmo Mejorado para Recuperar la eficiencia Que se pierde por la Tendencia degenerada en los arboles ABB en Operaciones de insercion y eliminacion.

Nota; Las Operaciones de FE se Realizan restando dependiendo los Niveles del nodo.


OPERACIONES:

Insercion: Inicialmente es El Mismo Proceso del ABB adicionalmente por Cada insercion se Calcula el FE Para Todos los nodos en la rama de la insercion, Partiendo de la hoja insertada y Subiendo Hacia la raiz, El Proceso se Detiene Si:
* Uno de los nodos Tiene FE = 0, Por Encima de la hoja.
* Llegamos a la raiz y no se presento FE Que muestren desbalances no / FE /> 1
* FE de un nodo presenta /FE/ > 1 , el arbol esta desbalanceado y necesita reestructuracion en un proceso llamado rotacion que recupera el balance y puede ser de 4 tipos:

Nota: En un proceso de rotacion se comprometen 3 nodos directamente.

Arboles Binarios De Busqueda (ABB) (4 - junio - 2015)

Su estructura permite implementar un algoritmo para ordenamiento y busqueda mas Eficiente Que Los que se pueden implementar en las ESTRUCTURAS vistas anteriormente. (ESTRUCTURAS  Lineales, Vectores Y Listas).

EFICIENCIA:
Dado por el menor numero de  comparaciones al Hacer Una Búsqueda.

Nota:. Aqui VEMOS Como este metodo de ordenamiento es mucho mas Eficiente frente a Otros metodos



OPERACIONES:

Nota: aqui todos los nodos mayores estan en La Derecha y Los Menores a la izquierda.


EJERCICIO:

Insertar: 24, 17, 33, 9,

ELIMINAR: 40, 9, 24, 1

Nota: Para Hacer Estós Procesos de Insertar y ELIMINAR, DEBEMOS Tener Presentes las reglas de las Operaciones vistas arriba.

Arboles Binarios De Expresion (22-mayo-2015)

Se USAN para representar y evaluar Expresiones aritmeticas
Son arboles binarios completos, Donde las hojas hijos hijo operandos y El Resto de nodos los Operadores.

Aqui VEMOS Como la pila Contiene 3 Elementos a, b, c.
El ultimo Elemento es colocado en la parte Derecha del nodo y el siguiente en la parte izquierda.

Arboles Binarios (21-mayo-2015)

Arboles binarios: Árbol Que restringe ONU Máximo Dos Pilas Descendientes por Cada Nodo.

Aplicaciones:
Representación y Evaluación de Expresiones aritméticas, búsqueda y ordenamiento.

Terminología:

Completo: Todos los nodos Tienen 0 o 2 hijos.
Lleno: Todos los Niveles Tienen De El Máximo de nodos (2h - 1 nodos).
Balanceados:  Todos los nodos con baño La Diferencia de las alturas del subárbol izquierdo y derecho es 0 y 1.
Degenerado: Todos los nodos Tienen Solo Un hijo EXCEPTO La Hoja.

Implementacion:
Estatica (Arreglos)

Clase pública NodoArbolBin <T> {

         Dato T Privado;

         Privada Izq NodoArbolBin;

         NodoArbolBin der privada;

         NodoArbolBin Pública (T dato, NodoArbolBin izq, der NodoArbolBin) {

             This.dato = dato;

             This.iq = izq;

            This.der = der;

          }

          ___

}

Dinamica (Nodos)

'

Clase pública Principal {

    Public static void main (String ... arg) {

        NodoArbolBin raiz = null;

        raiz = new NodoArbolBin ("A", nuevo NodoArbolBin ("B", null, null), nuevo NodoArbolBin ("C", null, null));

        NodoArbolBin P = raiz.getIzq ();

        p.setIzq (nueva NodoArbolBin ("D", null, null));

        p = raiz.getDer ();

        p.setIzq (nueva NodoArbolBin ("E", null, null));

        p.setDer (nueva NodoArbolBin ("F", null, null));

        Recorre (raiz);

     }

Static public void Recorre (NodoArbolBin r) {

    Si (r! = Null) {

       System.out.println (r.getDato ());

       Recorre (r.getIzq ());

       Recorre (r.getDer ());

     }

  }

}


Recorridos:
Visitar todos los nodos para hacer operaciones requeridas.

Arboles (15-mayo-2015)

Arboles: Son estructuras no lineales de tipo jerárquico.

Utilidad:
Aplican cuando se requiere representar estructuras con niveles y se pueda distinguir entre datos con mayor o menor valor.

Aplicaciones:
Organigramas, directorios, arboles geneologicos, etc.

Terminología:

Nodo: Cada elemento del arbol, solo tienen un padre, solo conocen la direccion de sus decendientes.

altura: cantidad de niveles: 3
peso: cantidad de hojas: 7
orden: cantidad de nodos: 10


Implementacion

Estática (Arreglos):

Dinamica (Nodos):

Recursividad (7-Mayo-27512015)

Propiedad de las funciones (Metodos), para autollamarse.

Utilidad:  Como alternativa a procesos interativos->(for,while,do.while), muy complejos.

Aplicaciones:  Recorrido de estructuras no lineales.

Ventajas:

Recursividad

* Reduce codigo

* Simplifica la logica

* Se da en metodos

* Consumo excesivo de memoria (Por cada autollamado se hace una copia del metodo y se guarda en la pila de llamado a subprogramas del sistema operativo).

Iteracion:

* No reduce codigo

* No simplifica, sino que tiene logica compleja

* No necesariamente en metodos con uso de (for,while,do-while)

* Muy bajo consumo de memoria.

Implementacion:

Iterativo:

Public static tipo nombreMetodo(args){

         _______

         _______

        for ( );

        _______

        _______

        while ( );

        _______

        _______

        do while( );

        _______

        _______

} 

Ejemplo:

factorial

5!= 1x2x3x4x5

public static long factorial (int n){

        long f=1; 

            for (int i=1; i<=n; i++){

                  f*=i;

            }

            return f;

}

Recursivo:

public static nombreMetodo (arg){

         if (condicion para autollamado){

         _______

         _______

         _______

        

         nombre Metodo(arg)

         _______

         _______

}

Ejemplo:

factorial
n!= n*(n-1)!

5! = 5*4! = 120
4! = 4*3! = 24
3! = 3*2! = 6
2! = 2*1! = 2
1! = 1*0! = 1
0! = 1

public static long factorial (int n){
           if (n==0){
                return 1;
           }else{
                    return n*factorial (n-1);
             }
}

Solucion Parcial #2 (7-mayo-2015)

1) Desarrole una funcion que intercambie los datos de los extremos de una pila (p).


Analisis:

Public static void intercambiarExtremos(Pila p){

      Pila q=new Pila( );

      Object aux  = p.quitar( );

      while (! p.vacia( )){

                q.poner(q.quitar( ));

      }

      p.poner(aux);

      aux=q.quitar( );

      while (! q.vacia( )){

                p.poner(q.quitar( ));

      }

      p.poner(aux);

}

Nota: aqui vemos como solamente cambian los extremos de la pila, notando que la parte del centro que igual.

2) Defina la clase pila en base a la grafica a continuacion

Nota: recuerde que las operaciones de pila son poner(por el fin), quitar(por el fin), cima(consulta fin), y vacia(no elementos).

Public class pilaNodoDoble <T> {

       private NodoDoble <T> tope;

       public boolean vacia( ) {  return tope==null; {

       public void poner (T dato) {

                  if (vacia( )){

                       tope=new NodoDoble(dato,null,null);

                  }else{ 

                           tope.setSig(new NodoDoble(dato,tope,null));

                           tope=tope.getSig( );

                    }

       }

       public T quitar( ){

                  T dato==null;

                  if (! vacia( )){

                       dato=tope.getDato( );

                       tope=tope.getAnt( );

                       if(tope != null){

                           tope.setSig(null);

                       }

                  }else{

                           System.out.print("Pila Vacia...!!!");

                    }

}       

Implementacion De La Cola (17-abril-2015)

Cola: Se realiza por extremos contrarios.

Operaciones: 
* Poner
* Quitar

VERSIÓN ESTATICA. (Arreglo)

 

VERSION DINAMICA. (Arreglo)

Implementacion De La Pila (16-abril-2015)

Pila: Restringe a un Extremo de la Estructura lineal-

Operaciones: 
* Poner (Almacenar un dato en la Estructura)
* Quitar (Recuperar el dato y eliminarlo de la Estructura)
cima
vacia
llena

VERSIÓN ESTATICA. (Base Vector)

tope: de control variable

                         

VERSIÓN DINAMICA. (Listas enlazadas)

Pilas Y Colas (16-abril-2015)

Son reglas Para La restriccion de Operaciones en ESTRUCTURAS lineales Como lo son (Arreglos, Listas enlazadas)

PILA : Se utilizan CUANDO Orden heno inverso.
EE.UU. la forma LIFO (último en el primero en salir), ultimo Elemento almacenado, Primero en Ser Procesado.

COLA : Almacenamiento temporal, MIENTRAS SE Hace un Proceso con la cola.
EE.UU. la forma FIFO (primero en firdt fuera), imprimación Elemento almacenado, Primero en Ser Procesado.

Utilidad 

Pila : Realizar Operaciones En Forma invertida, retroceder pendientes En Un Proceso Parr OPERACIONES Completar.
Cola: Cuando Los Recursos de Procesamiento HIJO Menos Que las Demandas de su USO. 

Aplicaciones 

Pila:  SO, Llamado un subprogramas, compiladores, párr evaluation de Expresiones aritméticas.
Cola: Cola de Procesos, cola de impresión, simulación.

Nota: Las Pilas Pecado no podria Existir modular la programacion.

EJERCICIO

1. CREAR Una Lista (a) de (n) con Nodos Datos Enteros Que contenga Números Positivos y Negativos pedidos desde el teclado y dividir La Lista en dos Nuevas Listas Una (b) Con Los numeros Positivos y Una (c) Con Los numeros 

Real = A;
mientras que (real! = null) {
      si (Actual.getDato> = 0) {
         si (b == null) {
            b = Actual;
            Real = Actual.getSig ();
            b.setSig (null);
            b1 = b;
          } Else {
              b.getSig (real);
              b = b.getsig (); 
              Real = Actual.getSig ();
              b.setSig (null);
            } Else {
                si (Actual.getDato <0) {
                   si (c == null)
                      c = Actual;
                      Real = Actual.getSig ();
                      c.setSig (null);
                      c1 = c;
                    } Else {
                        c.getSig (real);
                        c = c.getSig ();
                        Real = Actual.getSig ();
                        c.setSig (null);
                      }
             }
        }
   }

OPERACIONES CON LISTAS ENLAZADAS - (26-FEBRERO-2015)

INSERTAR

• Al Inicio
• Al Final

ELIMINAR

• Al Inicio 
• Al Final

BUSCAR PARA

• Insertar Antes
• Insertar Después
• Eliminar

___________________//_______________________________________//_________________

OPERACIONES

INSERTAR 

• Al Inicio

____________________________________________//__________________________________
INSERTAR

• Al Final

____________________________________//_________________________________________
ELIMINAR

• Al Inicio

______________________________________//__________________________________________

ELIMINAR

• Al Final

_______________________________//______________________________________________

BUSCAR PARA

• Insertar Despues

Procedimiento buscar
if(actual !=null){

   actual.setSig(new Nodo(xdato,aclave,actual.getSig()));
   if(actual==fin){
      fin=fin.getSig();
   }
}else{
   System.out.print("dato no encontrado");
 }

____________________________________//__________________________________________

BUSCAR PARA

• Eliminar

Procedimiento buscar

if(actual!=null){

    if(actual==inicio){

         inicio=inicio.getSig();

     }else{

            anterior.setSig(actual.getSig());

            if(actual==fin){

                  fin=anterior;

             }

         }

 }else{ 

    System.out.print("dato no encontrado");

}

__________________________________//_____________________________________________

BUSCAR PARA

• Modificar

Para acceder y cambiar el programa este es el codigo:
actual.getDato().setProg("sicologia");


Procedimiento buscar

if(actual != null){
    Estudiante e=actual.getDato();
                       cod(xCod);
         e.set       nom(xNom);
                        prog(xProg);
 }else{
   System.out.print("dato no encontrado");
}

TIPOS DE LISTAS ENLAZADAS - (20-FEBRERO-2015)

OPERACIONES EN LISTAS ENLAZADAS

• Insertar: al inicio, al final.
• Eliminar:al inicio, al final
• Buscar para: insertar antes, insertar después, eliminar
• Listar

    Nota: Al insertar lo primero que se debe hacer es crear el nodo.

¿... Que aprendí ...?

• Que existen diferentes tipos de listas enlazadas.
• Al insertar, primero se debe crear el nodo

LISTAS ENLAZADAS - (19-FEBRERO-2015)

¿Que es una lista enlazada ?
Estructura dinámica compuesta por un conjunto de nodos enlazados con una referencia al nodo inicial. Cada nodo esta compuesto por un atributo referencia dato y un atributo referencia nodo siguiente. El ultimo nodo de una lista enlazada tiene un valor null en el atributo de referencia al nodo siguiente que indica fin de la lista.

Nota: Linea de codigo para obtener el nombre del tercer nodo.

System.out.print (estudiante.getSig().getsetSig().getDato().getNombre());


Cuando una variable apunta hacia un objeto tiene derecho sobre un objeto.

Nodo P= estudiantes;
while (p!=null){
system.out.print(p.getDato().getCod());
system.out.print(p.getDato().getCod());
p=p.getSig();


____________________________________//_________________________________________

Estructura con la clase object que guarde Fraccionario y que imprime el Num y Den.

public class Nodo{
  private Object dato;
private Nodo sig;
________
________
________
}

Fraccionario f=(Fraccionario)fraccionario.getSig().getDato();

System.out.println(f.getNum() + "/" + f.getDen());

Nota:

Se pueden evitar Casting con clases genericas.

ESTRUCTURAS ESTATICAS VS DINAMICAS

La estructura estática, tiene asignado un espacio fijo de memoria en tiempo de compilación. Su tamaño no varía.
La estructura dinámica, obtiene espacio libre en memoria, en ejecución. Su tamaño puede variar a largo de la ejecución del programa.

CARACTERISTICAS:

ESTATICAS

• Menor consumo de memoria para guardar datos.
• Posible sub-utilización de las posiciones.
• Mejor tiempo de proceso al eliminar un dato (físicamente es imposible).
• Acceso directo atravez de un indice a los datos.
• Mayor velocidad en el recorrido de la estructura.
• Rigidez, una vez que se crea la estructura no puede cambiar de tamaño.
• Se recomiendan para eliminar pocos datos o cuando no halla muchas operaciones de intercion y eliminación.

DINAMICAS

• Mayor consumo de memoria porque por cada dato se almacena también una dirección para encontrar al siguiente dato.
• Ocupa la memoria a medida que se requiere almacenamiento de datos.
• No requiere tiempo de procesamiento para almacenar datos. *Al eliminar se desicupa físicamente el espacio de memoria.
• Para acceder al ultimo dato hay que pasar primero por todos los anteriores.
• proceso de recorrido lento.
• El tamaño aumenta o disminuye de acuerdo a las operaciones de intercion o eliminación.
• Se recomiendan cuando el volumen de datos es considerable y se realizan muchas operaciones de intercion y eliminación.