Blog del sitio: Tecnológico

Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...119   ()
Imagen de Erick García Estrada
de Erick García Estrada - miércoles, 11 de junio de 2014, 15:47
Todo el mundo

 
Imagen de Roger De Jesus Muñoz Villalobos
de Roger De Jesus Muñoz Villalobos - miércoles, 11 de junio de 2014, 15:32
Todo el mundo
  • ¿Que son ?

Los Arboles de expresiones son arboles binarios que se uilizan que se usan para evaluar expresiones aritmeticas en estos arboles las hojas son los operando y el resto son los operadores.

  • Ejemplo

Arbol

 

A

No

B

No

C

Si

D

No

E

No

[ Modificado: miércoles, 11 de junio de 2014, 15:33 ]
 
Imagen de Roger De Jesus Muñoz Villalobos
de Roger De Jesus Muñoz Villalobos - miércoles, 11 de junio de 2014, 15:19
Todo el mundo
  • Recorrido

 

Actividades

Recorridos

combinación

Visitar raíz

Pre-orden

1,2,3

Recorre subárbol izq

In-orden

2,1,3

Recorre subárbol der

Pos-orden

2,3,1

 
Imagen de Jean Carlos Robles Atencia
de Jean Carlos Robles Atencia - miércoles, 11 de junio de 2014, 15:17
Todo el mundo

ARBOLES

IMPLEMENTACION 

 

Arboles subclasificados

Arboles binarios: tiene una restriccion, maximo dos hijos por nodos 

Aplicaciones: evalucaion de expresion aritmeticas, busqueda y ordenamiento , etc.

terminologia:

COMPLETO:todos los nodod, dos hijos exacto als hojas 

BALANCEADO:  para todos los nodos la diferencia entre las alturas de subarboo izquierdo y derecho es menor a dos 

LLENO: todos los niveles de arbol tiene el maximo de nodos 2^h-1 es la cantidad del arbol lleno 

DEGENERADO:todos los nodos tienen solo un hijo excepto las hojas 

public class nodoArbolBin <T> {

private T dato;

Private NodoArbolBin izq;

Private NodoArbolBin Der;

public nodoarbolBin(){

publi nodoArbolBin (5 dato){       //Atributos 

this.dato =dato;

izq =der =null;

}

--------

--------

--------

}

 

publi class principal{

public static void main (String []arg){

nodoArboolBin vait

raiz= new nodoArbolBin ("A");

raiz.set izq (new nodoArbolBin("B"));

raiz.set der(new nodoArbolBin("C"));

nodoArbolBin a= raiz.get izq();

a.set izq (new nodoArbolBin("D"));

a= raiz.get der();

a.set izq (new nodoArbolBin("E"));

a.set Der (new Nodo ArbolBin("F"));

-----

-----

}

RECORRIDOS : combinacion de actividades para visitar todos los nodos y hacer las respectivas operaciones

Actividades (recursiva)

1. vista raiz 

2. recorer subarbol izquierdo (R)

3. recorer subarbol derecho (R)

Combinaciones              Recorridos

[1]  2  3                           preorden

2  [1]  3                           inorden

2  3  [1]                           posorden

 
Imagen de Cindy Paola Castilla Bahoque
de Cindy Paola Castilla Bahoque - miércoles, 11 de junio de 2014, 15:14
Todo el mundo

Los ABB solo mantienen eficiencia en el proceso de búsqueda se están balanceado pero cuando tiene una tendencia degenerada.

la eficiencia en el proceso de búsqueda hoja. un algoritmo AVL propone chequear en cada operación de inserción o eliminar el balance del árbol y reestructurarlo en caso que este se pierda.

 

Se debe saber que un árbol binario esta balanceado para todos los nodos si (FE>-2y FE<2) de esta manera el árbol estará balanceado. Si no árbol no balanceado.

 

Operaciones:

1) INSERTAR: inicialmente se aplica la misma regla del ABB pero adicionalmente se calcula FE en los nodos de la misma rama de la inserción, comenzando por el nodo insertado así mismo la raíz un nodo a parte de la hoja  tiene FE igual a cero o se llega a la raíz y ninguno FE esta fuera de rango de balance, se separa el proceso porque todo está bien; si no cuando el FE esta fuera de balance, se reestructura el árbol es un proceso llamado ROTACION que comprende 3 nodos principalmente y puede ser de varios casos:

1) Rotación (II):

De izquierda. Izquierda (insertar A.B.C)

 

 

[ Modificado: miércoles, 11 de junio de 2014, 15:14 ]
 
Imagen de LINDA NIEVES VILLADIEGO MONTES
de LINDA NIEVES VILLADIEGO MONTES - miércoles, 11 de junio de 2014, 14:56
Todo el mundo

Arboles ABB: permiten ordenamiento y eficiencia en el proceso de busqueda mucho mejor que las estructuras antes vistas( areeglos y listas enlazada)

operaciones: insercion: para insertar para todos las claves en el subarbol izquierdo deben ser menore y las del subarbol derecho mayores. la insercion se hace en la misma forma en que se consiguen las claves 

ejemplo: 7,3,10,5,2,9,1,4

eliminacion:

hoja: simplemente se suprime

nodo con un subarbol:

remplazamos por su descendiente inmediato

nodo con dos cubarboles: remplazamos consu descendiente mas a la izquierda del subarbol derecho o por el descendiente mas a la derecha del sub arbol izquierdo

ejemplo elimar 7,4,1,10

cuando un arbol se degenera la eficiencia en el proceso de busqueda se vuelve nula

Arboles AVL: arboles binarios ABB mejorados ya ue proveen un algoritmo de autobalanceo que evita la tendencia degenerada en las operaciones de insercion y eliminacion

FE: factor de equilibrio 

hsd: altura subarbol derecho

hsi: altura subarbol izquierdo

FE=hsd-hsi

para todos los nodos 

si(FE>-2y FE<2)

arbol balanceado

sino

arrbol no balanceado

fin si

posibles : -1 0 1

criterio de balanceo por altura

operaciones en AVL: 

insercion: incialmente el mismo proceso ABB pero adicionalmente se calcula que en cada insercion el FE. iniciando en la hoja insertada siguiendo la rama hasta la rauz se pueden presentar los sigueintes casos:

  1. llegar a la raiz
  2. el FE = 0 en algun nodo diferente a la hoja
  3. el Fe muestra que hay desbalance en este caso se restructura el arbol en eun proceso llamado rotacion que puede ser de los siguientes tipos

ID: izquierda- derecha  insertar c,a,b

DI: derecha-izquierda  insertar a,c,b

ejemplo de insercion

3,7,1,4,8,9,12,24,33,44,25,11,10,6,2

reglas para eliminar: se aplica la misma regla ABB se calcula el FE en la rama donde se elimina el nodo si hay desbalance se aplica el tipo de rotacion

[ Modificado: miércoles, 11 de junio de 2014, 14:56 ]
 
Imagen de Cindy Paola Castilla Bahoque
de Cindy Paola Castilla Bahoque - miércoles, 11 de junio de 2014, 14:54
Todo el mundo

ABB  permite ordenamiento y eficiencia en el proceso de busqueda, mucho mejor que en estructuras antes vistas tales como arreglos y listas enlazadas.cabe resaltarque entra mas grande y completo sea un arbol es mas facil y eficiente sera.

 
Imagen de Roger De Jesus Muñoz Villalobos
de Roger De Jesus Muñoz Villalobos - miércoles, 11 de junio de 2014, 14:48
Todo el mundo
  • Implementacion Estatica

 

  • Implementacion Dinamica

 

  • Clase nodo Arbol binario

public class Nodoarbolbin<T> { 

       private T dato; 

private NodoarbolBin izq;

private nodoarbolBin der; 

public NodoarbolBin() { } 

public NodoarbolBin ( T Dato) {

        This.dato=dato;

       }

 

Public class principal {

    prublic Static void static (string ... arg) {

 NodoarbolBin raiz;

  raiz= new nodoarbolBin ("A");

raiz.setizq (new nodoarbolBin ("B");

raiz.setder ( new nodoarbolBin("C");

NodoarbolBin a= raiz.getizq ( );

a.setizq(nodoarbolBin ("D"));

a= raiz.getder( ); 

a.setizq(new nodoarbolBin("E"));

a.setder(new nodoarbolBin("F"));

      }

}

  

[ Modificado: miércoles, 11 de junio de 2014, 14:50 ]
 
....
de JUAN ERASMO PEREZ ALVARADO_12217058 - miércoles, 11 de junio de 2014, 14:35
Todo el mundo

Arboles ABB: 

Un árbol de ordenamiento y eficiencia el proceso de búsqueda es mucho mejor que las estructuras antes vistas tales como(los arreglos y las listas enlazadas).

Operaciones:

Hay dos operaciones:

 

  1. Inserción: para insertar para todos los nodos las claves en el subárbol izquierdo deben ser menores y las del subárbol derecho mayores. La Insercion se hace en la misma forma en que se consiguen las claves.
  2.  Eliminación:

    1. Hojas: simplemente se suprime.
    2. Nodo con un Subárbol: Reemplazo por sus descendientes inmediatos.
    3. Nodos con dos subárboles: reemplazado por sus descendientes más a la izquierda de árbol derecho o por el descendiente más a la derecha del subárbol izquierda.

     

    Arboles AVL:

    Son árboles binarios mejorados, ya que proveen un algoritmo de auto balanceo que evita la tendencia a degenerarse en las operaciones de inserción y eliminación.

Factor de equilibrio:

FE = hsd- hsi

Hsd: altura suba derecho

Hsi: altura suba izquierdo

el siguiente algoritmo es usado para balancear el arbol avl par que al momento de la insercion no quede degenerado

 

Para todos los nodos.

Si (FE> -2 y FE<2)

            Árbol balanceado

Si no

            Árbol no balanceado

Fin sí.

(en el anterior blog se cometio un error el de poner el metodo de eliminacion avl  donde no correspondia)

 
Todo el mundo

Estructura de un método recursivo:

public static tipo/clase nombreMetodoRecursivo (parámetro)  {

                if (expresion lógica) //Ayuda a controlar el auto llamado.

                               ---------------

                               ---------------

                               // nombreMetodoRecursivo(parámetro); //autollamado

                } else {

                               // nombreMetodoRecursivo(parámetro); //autollamado

                }

}

import java.util.Scanner;
 
class Ejercicio{
 
      public static int factorial(int n)
      {
        if(n==0) return 1;
        else return n*factorial(n-1);
      }
 
      public static void main(String args[])
      {
        Scanner in =new Scanner(System.in);
        int num;
        do{
           System.out.print("Ingrese numero :");
           num=in.nextInt();
        }while(num<=0);
  System.out.println("El factorial es : "+factorial(num));
      }
}
el ejemplo de arriba es el ejemplo de recursividad como codigo en el cual se muestra el calculo de un numero factorial
 
otro ejemplo seria

2° = 1

public static int mcd ( int a, int b ) {

                if ( a ==b ) {

                                    return a;

                } else {

                            If( a > b ) {

                                             return mcd ( a-b, b);

                            } else {

                                        return mcd ( a, b-a );

                            }

             }

}

 

Arboles:

Son estructura de datos no lineales, para organización de la información por niveles. (foto #1)

Utilidad: Organización de datos en la forma jerarquía (Distribución entre mayores y menores)

Aplicaciones: Sistema Operativo: directorios, evolución de expresiones aritméticas, búsqueda y ordenamiento etc. 

Terminología:

nodo raiz : es del cual inicia se deriva el arbol

nodo hoja es el nodo que no esta enlazado pero que si lo enlazan

rama: tiene un recorido secuencial desde la raiz hasta 1 hoja

arbol interno o subArbol: tiene tanto decendiente como padre (generalmente es la raiz)

nivel:  Está definido por 1+ el número de conexiones entre el nodo y la raíz

Altura: cantidad de niveles

 pesos: cantidad de hojas

orden: cantidad de nudos.

Arboles binarios

son aquiellos que tienen restriccion maxima de 2 hijos por nodo

estos arboles pueden ser usados en evaluaciones de operaciones aritmenticas, busquedas y ordenamiento

caracteristicas: siempre hay un subArbol izquierdo y uno derecho

estos arboles pueden ser:

completo: todos sus nodos tienen 2 hijos (no aplica para las hojas)

balanceado : cuando la diferencia de todos los nodos esta a la altura del subarbol izquierod y derecho es de >2

lleno: cuando los niveles (todos) del arbol tiene el maximo de nodos  2*h -1 se usa para calcular si el arbol es lleno

degenerado todos los nodos tienen 1 hijo  en sus hojas

 

Clase NodoArbolBinario

 

public class NodoArbolBin {

 

             private T dato;

             private NodoArbolBin izq;

             private NodoArbolBin der;

            

    public NodoArbolBin() { }

   

    public NodoArbolBin(T dato) {

             this.dato = dato;

             izq = der = null;

    }

   

    public void setIzq(NodoArbolBin izq){

             this.izq = izq;

    }

    public NodoArbolBin getIzq(){

             return izq;

    }

    public void setDer(NodoArbolBin der){

             this.der = der;

    }

    public NodoArbolBin getDer(){

             return der;

    }

    public void setDato(T dato){

             this.dato = dato;

    }

    public T getDato(){

             return dato;

    }

 }

 

Clase Principal

 

public class Principal {

    public static void main (String [] arg){

             NodoArbolBin raiz;

             raiz = new NodoArbolBin("A");

             raiz.setIzq(new NodoArbolBin("B"));

             raiz.setDer(new  NodoArbolBin ("C"));

             NodoArbolBin a = raiz.getIzq();

             a.setIzq(new NodoArbolBin("D"));

             a = raiz.getDer();

             a.setIzq(new NodoArbolBin("E"));

             a.setDer(new NodoArbolBin("F"));

             //Otras Instrucciones                   

    }   

}

 

Recorridos:

Son una combinación de actividades para visitar todos los nodos y hacer las respectivas operaciones.

 

Actividades (Recursivas)

Combinaciones

Recorridos

Visita raíz

1

2

3

Preorden

Recorrer subárbol Izq ( R )

2

1

3

InOrden

Recorrer subárbol Der ( R )

2

3

1

PosOrden

 

Pre: A, B, D, C, E, F

Int: D, B, A, E, C, F            IZQ – RAIZ - DER

Pos: D, B, E, F, C, A           IZQ -  DER – RAIZ

Otras subclasificaciónes:

Arboles de expresion: Son arboles binarios completos que se usan para evaluar expresiones aritméticas, en estos arboles las hojas sin los operandos y el resto de nodos los operandos.

 

 

Reglas para Borrar:

Se aplica la misma regla ABB, Se calcula el FE en la rama donde se elimina el nodo, si ha des-balanceo se aplica un tipo de rotación.

 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...119   ()