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 ...120   ()
Imagen de JHONATAN LEANDRO CORREA MEJIA
de JHONATAN LEANDRO CORREA MEJIA - miércoles, 11 de junio de 2014, 16:11
Todo el mundo

ARBOL DE EXPRESIONES

 

 

arboles binarios que se usan para evaluar expresiones aritmeticas en estos arboles las hojas son los operandos y el resto de nodos los operadores 

 

 

NOTA: el recorrido  en preorden de un arbol de expresion produce la  prefija de la expresion 

ARBOLES ABB

permiten ordenamiento y eficiencia en el proceso de busqueda mucho mejor que las estructuras antes vistas ( arreglos, listas enlazadas) mientras mas crece la estructura de arboles de busqueda hace la busqueda mas eficiente tambien al hacer un recorrido en inorden

 

 

OPERACIONES

 

INSERCCION: para insertar par alos nodos las claves en el subarbol izquierdo deben ser menores y las del subarbol derecho mayores la inserccion se hace en la misma forma en que se consiguen las claves

 EJEMPLO

 

ELIMINAR 

  • 1 HOJA:  simplemente se suprime
  • NODO CON UN SUBARBOL: es reemplazado por su descendiente inmediato
  • NODO CON DOS SUBARBOL:  es reemplazado por e descendienre mas a la izquierda del subarbol derecho o por el descendiente as ala derecha del subarbol izquierdo

 

ARBOLES AVL 

arboles abb mejorados ya uqe proveen un algoritmo de auto balanceo que evita la tendencia degenrada enlas operaciones de inserccion y eliminacion

FACTOR DE EQUILIBRIO

FE=hsd-hsi

si( FE>-2 & FE<2)

arbol balanceado

sino 

arbol no balanceadp

fin si

 

OPERACIONES EN AVL 

INSERCCION: inicialmente el mismo proceso de abb pero adicionalmente se calcula en cada inserccion al fe inicial en la hoja insertada siquiendo  la rama hasta la raiz se puden presentar los siquientes casos 

  • llega a al raiz
  • el fe = 0 en algun nodo diferente a la hoja 
  • el fe muestra que hay desbalance en este caso se reestructura el arbol en un proceso llamado rotacion que puede se de los siquientes tipos

 

 

 

 

 

 

 

 

 

 
Imagen de JHONATAN LEANDRO CORREA MEJIA
de JHONATAN LEANDRO CORREA MEJIA - miércoles, 11 de junio de 2014, 16:11
Todo el mundo

ARBOL DE EXPRESIONES

 

 

arboles binarios que se usan para evaluar expresiones aritmeticas en estos arboles las hojas son los operandos y el resto de nodos los operadores 

 

 

NOTA: el recorrido  en preorden de un arbol de expresion produce la  prefija de la expresion 

ARBOLES ABB

permiten ordenamiento y eficiencia en el proceso de busqueda mucho mejor que las estructuras antes vistas ( arreglos, listas enlazadas) mientras mas crece la estructura de arboles de busqueda hace la busqueda mas eficiente tambien al hacer un recorrido en inorden

 

 

OPERACIONES

 

INSERCCION: para insertar par alos nodos las claves en el subarbol izquierdo deben ser menores y las del subarbol derecho mayores la inserccion se hace en la misma forma en que se consiguen las claves

 EJEMPLO

 

ELIMINAR 

  • 1 HOJA:  simplemente se suprime
  • NODO CON UN SUBARBOL: es reemplazado por su descendiente inmediato
  • NODO CON DOS SUBARBOL:  es reemplazado por e descendienre mas a la izquierda del subarbol derecho o por el descendiente as ala derecha del subarbol izquierdo

 

ARBOLES AVL 

arboles abb mejorados ya uqe proveen un algoritmo de auto balanceo que evita la tendencia degenrada enlas operaciones de inserccion y eliminacion

FACTOR DE EQUILIBRIO

FE=hsd-hsi

si( FE>-2 & FE<2)

arbol balanceado

sino 

arbol no balanceadp

fin si

 

OPERACIONES EN AVL 

INSERCCION: inicialmente el mismo proceso de abb pero adicionalmente se calcula en cada inserccion al fe inicial en la hoja insertada siquiendo  la rama hasta la raiz se puden presentar los siquientes casos 

  • llega a al raiz
  • el fe = 0 en algun nodo diferente a la hoja 
  • el fe muestra que hay desbalance en este caso se reestructura el arbol en un proceso llamado rotacion que puede se de los siquientes tipos

 

 

 

 

 

 

 

 

 

[ Modificado: miércoles, 11 de junio de 2014, 16:11 ]
 
Imagen de Roger De Jesus Muñoz Villalobos
de Roger De Jesus Muñoz Villalobos - miércoles, 11 de junio de 2014, 15:55
Todo el mundo
  • ¿Que Son?

Los arboles ABB nos permiten el ordenamiento y eficiencia en el proceso de busqueda mucho mejor que las estructuras antes vistas (arreglos y lisas enlazadas..

  • operaciones de ABB

- Inserccion: Para insertar, las claves en el subarbol izquierdo deben ser menores y las del subarbol derecho deben ser mayores. 

la inserccion se hace en la misma forma que se consignen las claves.

Ejemplo:

Insertar las siguientes claves  24,33,70,44,57,28,12,19,

 

Arbol resultante 

 

- Eliminacion

  *Hoja: Solamente se suprime.

  *Nodo Con un Subarbol: Es reemplazado por su descendiente de inmediato.

  *Nodo con dos Subarboles: Es reemplazado por su descendiente mas a la izquierda del subarbol derecho o por el descendiente mas a la derecha del subarbol izquierdo.

 Ejemplo: Eliminar las siguientes claves 19, 44, 57

Arbol resultante

[ Modificado: miércoles, 11 de junio de 2014, 16:02 ]
 
Imagen de Jean Carlos Robles Atencia
de Jean Carlos Robles Atencia - miércoles, 11 de junio de 2014, 15:50
Todo el mundo

public static void preOrden (NodoArbolBin){

if(r!=null){

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

preOrden(r.getizq());

preOrden(r.getDer());

}

}

Nota: para el codigo java en in orden el S.O.P. va a la mitad y el posorden va al final 

________________________________________________________________________________________________________________

Investigacion:(el proceso iterativo de recorrido del arbolbinario).

 ITERATIVO DE RECORRIDO DE ÁRBOLES
 
En este tipo de estructuras recursivas, aunque la solución iterativa suele ser más eficiente, el algoritmo que la implementa es típicamente más complicado, y requiere estructuras de datos adicionales. En este caso, se necesita una pila, que le permita a la rutina volver a subir en la estructura, después de visitar los niveles más alejados de la raíz.
 
Recorridos sobre árboles binarios
 
Se consideran dos tipos de recorrido: recorrido en profundidad y recorrido en anchura o a nivel.
 
Recorrido en preorden: consiste en visitar el nodo actual (visitar puede ser simplemente mostrar la clave del nodo por pantalla), y después visitar el subárbol izquierdo y una vez visitado, visitar el subárbol derecho. Es un proceso recursivo por naturaleza.
 
orden siguiente: a,b,d,c,e,f.
void preorden(tarbol *a)
{
if (a != NULL) {
visitar(a);
preorden(a->izq);
preorden(a->der);
}
}
 
Recorrido en inorden u orden central: 
 
serían en este orden: b,d,a,e,c,f.
void inorden(tarbol *a)
{
if (a != NULL) {
inorden(a->izq);
visitar(a);
inorden(a->der);
}
}
 
Recorrido en postorden:
 
quedaría así: d,b,e,f,c,a.
void postorden(arbol *a)
{
if (a != NULL) {
postorden(a->izq);
postorden(a->der);
visitar(a);
}
}
 
Recorrido en amplitud:
 
Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (como mucho hay uno, la raíz), después los nodos de nivel 2, así hasta que ya no queden más.
 
void amplitud(tarbol *a)
{
tCola cola; /* las claves de la cola serán de tipo árbol binario */
arbol *aux;
 
if (a != NULL) {
CrearCola(cola);
encolar(cola, a);
while (!colavacia(cola)) {
desencolar(cola, aux);
visitar(aux);
if (aux->izq != NULL) encolar(cola, aux->izq);
 
_________________________________________________________________________________________________________________
 
 
SUBCLASIFICACION
ARBOLES DE EXPRESION 
Arboles binario completos que se usan para evaluar expresiones aritmeticas. en estos arboles las hojas son los operando y es resto de nodo los operadores.
 
EXPRESIONES ARITMETICAS:
1+2*3  POSFIJA
a+b*c  abc *+
 
 
 
operadores: + - % *
operados: a, b, c // 1, 2, 3
 
 
 
 
[ Modificado: miércoles, 11 de junio de 2014, 15:50 ]
 
Todo el mundo

Clasificación de Arboles (Arboles Binarios) – 28 – 05 – 14

 

El día miércoles 28 de mayo de 2014 vimos un tipo de árbol llamado árbol binario donde su definición es la siguiente:

1.    Definición: Un árbol binario tiene una restricción que cada nodo debe tener un número de dos hijos, de ahí viene el nombre de binario.

2.    Aplicaciones: Las aplicaciones de los árboles binarios se destacan: evaluación de expresiones aritméticas, búsqueda, ordenamiento, entre otras.

En la siguiente gráfica podemos ver la estructura básica de un árbol binario:

 

 

Subclasificación de árboles binarios

1.    Completo: Todos los nodos tienen dos hijos excepto las hojas.

2.    Balanceado: Para todos los nodos, la diferencia entre las alturas del subárbol izquierdo y el subárbol derecho debe ser menor a 2.

3.    Lleno: Todos los niveles del árbol tiene el máximo número de nodos 2h -1 que corresponde a la cantidad total de nodos del árbol.

4.    Degenerado: Todos los nodos tienen solo un hijo excepto las hojas.

 

Implementación de los árboles binarios

 

Vectores                                                  

-1

0

1

-1

3

-1

datos <T>                        izquierdo int                                                  derecho int

 

D

B

A

E

C

F

-1

-1

4

-1

5

-1

 

 

 

Nodos

Esta es la estructura básica de un nodo de un árbol binario:

dato

izquierdo

derecho

 

A continuación procedemos a la parte de programación para armar nuestro árbol binario definimos la clase base llamada NodoArbolBin que a la vez es generica

public class NodoArbolBin <T>{

  private T dato;

  private NodoArbolBin izquierdo;

  private NodoArbolBin derecho;

  public NodoArbolBin(){} // Constructor por defecto

      public NodoArbolBin(T dato){ // El constructor solamente recibe el dato que va a almacenar

          this.dato = dato;

     izquierdo = derecho = null; // Inicializamos los punteros a null cuando el nodo no tiene hijos

}

public NodoArbolBin(T dato, NodoArbolBin izquierdo, NodoArbolBin derecho){ // El constructor recibe el dato que va a almacenar, y las direcciones de los hijos izquierdo y derecho

    this.dato = dato;

    this.izquierdo = izquierdo;

    this.derecho = derecho;

}

Métodos modificadores y analizadores (set y get)

public void setDato(T dato){ this.dato = dato;}

public T getDato(){ return dato;}

public void setIzquierdo(NodoArbolBin izquierdo){ this.izquierdo = izquierdo;}

public NodoArbolBin getIzquierdo(){return izquierdo;}

public void setDerecho(NodoArbolBin derecho){ this.derecho = derecho;}

public NodoArbolBin getDerecho(){return derecho;}

}

Después creamos la clase Principal donde está el método main para armar nuestro árbol binario.

public class Principal{

   public static void main(String[]args){

       NodoArbolBin raiz; // Definimos la raíz que es el primer nodo del árbol

raiz = new NodoArbolBin(“A”); // Creamos el nodo raíz y a la vez guardamos el dato dentro del nodo Nota: Podemos crear un nodo sin pasar el dato enseguida en el nodo pero debemos usar el método setDato para almacenar el dato

raiz.setIzquierdo(new NodoArbolBin(“B”)); // La raíz apunta al nuevo nodo que será su hijo izquierdo y en el nodo nuevo le almacenamos a la vez el dato.

raiz.setDerecho(new NodoArbolBin(“C”)); // La raíz apunta al nuevo nodo que será su hijo derecho y en el nodo nuevo le almacenamos a la vez el dato.

NodoArbolBin a = raiz.getIzquierdo(); // Estamos en el subárbol derecho con dato C, para trasladarnos al subárbol izquierdo o ir al nodo hermano debemos crear una variable para que apunte a subárbol izquierdo llamando al método getIzquierdo() asi obteniendo su dirección.

a.setIzquierdo(new NodoArbolBin(“D”)); // La variable auxiliar a que la dirección de la raiz con el hijo izquierdo apunta al nuevo nodo que será su hijo izquierdo y en el nodo nuevo le almacenamos a la vez el dato.

a = raiz.getDerecho()-, // Estamos en el último nodo del subárbol izquierdo que es una hoja para trasladarnos al nodo cuyo dato es C debemos asignar la dirección de la variable original llamada raíz que quedo apuntando al nodo C llamando al método getDerecho para obtener su dirección

a.setIzquierdo(new NodoArbolBin(“E”)); // // La variable auxiliar a que la dirección de la raiz con el hijo derecho apunta al nuevo nodo que será su hijo izquierdo y en el nodo nuevo le almacenamos a la vez el dato.

a.setDerecho(new NodoArbolBin(“F”)); // // La variable auxiliar a que la dirección de la raíz con el hijo derecho apunta al nuevo nodo que será su hijo derecho y en el nodo nuevo le almacenamos a la vez el dato.

}// Fin del método main

}// Fin de la clase Principal

 

 

 

 

[ Modificado: miércoles, 11 de junio de 2014, 17:10 ]
 
Imagen de Erick García Estrada
de Erick García Estrada - miércoles, 11 de junio de 2014, 15:47
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 ]
 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...120   ()