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...!!!");

                    }

}