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 ...139   ()
Imagen de Miguel Angel Cano Dakin
de Miguel Angel Cano Dakin - martes, 9 de diciembre de 2014, 16:45
Todo el mundo

Árboles de búsqueda (ABB o Arboles binarios de búsqueda)

Su construcción se basa en un algoritmo que ordena y hace más eficiente el proceso de búsqueda en relación con la estructura lineal vista anteriormente.

 

Eficiencia: menor número de comparaciones al buscar la eficiencia es mayor.

Con los árboles de búsqueda binarios se hace más eficiente la búsqueda ya que hace un descuento de 50% de lo que se está buscando omitiendo buscar en esa cantidad.

Al aplicar el recorrido InOrden en los Arboles de búsqueda se obtiene una lista ordenada.

Operaciones:

1 Inserción: Las claves se insertan en la medida que llegan pero teniendo en cuenta que cada nodo solo tiene valores mayores a la derecha y valores menores a la izquierda.

2 Eliminación: pare este se dan los siguientes casos:
Caso 1: si es una hoja simplemente se suprime.

Caso 2: si tiene sub árbol se remplaza por su descendiente.

Caso 3: si tiene dos sub árbol se remplaza por el nodo más a la izquierda del sub árbol derecho o por el nodo más a la derecha del sub árbol izquierdo.

Si insertamos el árbol quedaría de la siguiente manera:
37, 44, 18, 23, 12, 33, 28, 58, 7, 4, 9, 16, 29, 41, 63

si eliminamos los siguientes datos: 29

si eliminamos el 23

si eliminamos el 18

si eliminamos el 44

 

si eliminamos el 37

[ Modificado: martes, 9 de diciembre de 2014, 16:45 ]
 
Imagen de Luis Enrique Ayin Arias
de Luis Enrique Ayin Arias - martes, 9 de diciembre de 2014, 15:51
Todo el mundo

1/12/2014

Arboles binarios:

Cada nodo tiene dos hijos máximos

Aplicación:

Representación y evaluación de expresiones aritméticas, búsqueda y ordenamiento.

Terminología:

Dos árboles diferentes en cada nodo (tiene que haber inclinación)

 

Completo: cada nodo tiene dos o cero descendientes

Balanceado: para cada nodo la diferencia entre las alturas del SubDer y el SubIzq debe ser menos que 2.

Degenerado: cada nodo solo tiene un hijo exceptuando la hoja

Lleno: cada nivel tiene le máximo de nodos que soporta

 

Implementacion

 

Arrreglos

 

Nodos

 

Para el código:
public class NodoArbolBin<T>{

 Private T dato;
 private NodoArbolBin izq;
 private NodoArbolBin der;

 Public NodoArbolBin(T dato){

  This.dato=dato;
  izq=der=nul;

 }

 ………..

}

Public class Prinsipal{

 Public static void main (String arg[]){

  NodoArbolBin raíz;
  raíz = new NodoArbolBin(“A”);

  Raíz.setIzq(new NodoArbolBin (“B”));

  Raiz.setDer(new NodoArbolBin(“C”));

  NodoArbolBin p=raíz.getIzq();

  p.setIzq(new NodoArbolBin(“D”));

  p= raíz.getDer();

  p.setIzq(new NodoArbolBin(“E”));

  p.setDer(new NodoArbolBin(“F”));

 }

}

Recorrido de los arboles binarios

Actividades

1 visitar raíz (mostrar)

2 recorrer subArbol izquierdo

3 recorrer subArbol derecho

Recorridas                                                  Combinación de actividades

preOrden                                                                    1,2,3

InOrden                                                                       2,1,3

posOrden                                                                    2,3,1

 

PreOrden: ABDCEF

InOrden: DBAECF

PosOrden: DBEFCA

Funciones recursiva

Public static void preOrden (NodoArbolBin r){

 If(r!= null){

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

  preOrden(r.getIzq());

  preOrden(r.getDer());

 }

}

[ Modificado: martes, 9 de diciembre de 2014, 15:51 ]
 
Imagen de Luis Enrique Ayin Arias
de Luis Enrique Ayin Arias - martes, 9 de diciembre de 2014, 14:56
Todo el mundo

28/11/2014

Recursividad – Implementación

Se implementa en métodos como se observa a continuación:

Public static tipo nombre(parámetro ){

 If (expresión ){

  ……..

  Nombre(argumentos);

  ……….

 }

}

Factoriales

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

Para el código:
public static void Factorial(int n){

 If(n==0){

  Return 1;

 }else{

  Return n*fatorial(n-1);

 }

}

 

Arboles: estructura de datos no lineal para organizar información por niveles

Utilidad: organización tipo jerarquico – se diferencia entre valores mayores y menores

Aplicación: organigramas, genealogía, representación y evaluación de expresiones aritméticas, ordenamiento y búsqueda.

Terminología

 

1 raiz: nodo único

2 interno: nodo con ascendente y desendientes

3 sub árbol: desendencia completa de un árbol

4 rama: camino de la raíz hasta la hoja

5 hoja: nodo que no tiene desendientes

Altura: cantidad de niveles = 3

Peso: cantidad de hojas = 7

Orden: cantidad de nodos del árbol = 10

Implementación:
Arreglos

 

Nodos

 
Imagen de Luis Enrique Ayin Arias
de Luis Enrique Ayin Arias - martes, 9 de diciembre de 2014, 14:10
Todo el mundo

24/11/2014

Recursividad

Es una propiedad de las funciones (métodos) para auto llamarse, son una alternativa a los procesos iterativos (for; while; do while)

Utilidad: cuando las soluciones iterativas son muy complejas.

Aplicaciones: recorrido de estructuras no lineales, fórmulas matemáticas complejas.

Iteración

  • Ciclos for; while; do while
  • Puede tener lógica en la solución de algunos problemas
  • Puede aumentar el código en la solución de algunos problemas
  • Muy bajo consumo de memoria

Recursividad

  • Funciones o métodos
  • Simplifica la lógica en la solución de problemas
  • Generalmente se reduce el código del programa
  • Considerable consumo de memoria (por cada auto llamado el sistema operativo hace una copia completa de la función y son guardados en una pila)

Por las razones anteriores, por el simple hecho de ocupar mucho más espacio en la memoria es más utilizados las iteraciones porque es más rápido para realizar procesos muy largos y cortos.

[ Modificado: martes, 9 de diciembre de 2014, 14:10 ]
 
Imagen de Luis Enrique Ayin Arias
de Luis Enrique Ayin Arias - martes, 9 de diciembre de 2014, 14:02
Todo el mundo

21/11/2014

Cola circular

 

Max [5]

Frente [4]

Fin [4]

La pila está llena  { (frente == 0 && fin == max-1) || (fin == frente -1)

 

Aplicando las colas circulares en el código obtenemos:

Public class ColaCircularVector<T> implements Regla<T>{

 private T C[];
 private int max;

 private int frente;
 private int fin;

 Public ColaCircularVector(){

  Max = 100;

  Frente = fin = -1;

  C= (T[]) new  object [max];

 }

 Public ColaCircular Vector(int max){

  This.max = max;

  Frente = fin = -1;

  C(T []) new object[max]:

 }

//método utilizado para saber cuándo el vector esta vacio

 Public boolean Vacia(){

  return frente == -1;

 }

 //método utilizado para saber si el vector esta lleno

 Public  boolean llena(){

  return frente == 0 && fin == max – 1;

  fin== frente-1;

 }

 // método utilizado para poner

 Public void poner (T dato){

  If(¡llena()){

   If(vacia()){

    Frente = 0;

   }

   If(fin==max-1){

    Fin = 0;

   }else{

    Fin++;

  }

  C[fin]=dato;

  }else{

  System.out.println(“!cola llena…”);

 }

 }

 Public T quitar(){

  T dato = null;

  If(¡vacia()){

   dato = C [frente];

   if(frente == fin){

    frente=fin= 0;

   }else {

    If(frente == max - 1){

    Frente=0;

   }else{

   Frente++

  }

  }

  }else{

  System.out.println(“!cola vacia…”);

 }

 return dato;

 }

}

 
Imagen de Enrique Alberto Carvajalino Padilla
de Enrique Alberto Carvajalino Padilla - lunes, 8 de diciembre de 2014, 18:39
Todo el mundo

http://kike2014.over-blog.com/2014/12/arboles.html

[ Modificado: lunes, 8 de diciembre de 2014, 18:56 ]
 
Imagen de DAMASO SALGADO CASSIANI
de DAMASO SALGADO CASSIANI - lunes, 8 de diciembre de 2014, 13:20
Todo el mundo

Arboles Binarios:

Para que sea un arbol binario debe tener 2 hijos maximos.

Aplicacion:

Representacion  y evaluacion expreciones aritmeticas, busqueda y ordenamiento.

Terminologia:

Dos SubArboles diferenciados en cada nodo(Esto see conoce como Inclinacion).

Tipo de arboles:

Completo:

Cada nodo tiene dos o cero descendientes.

Balanceado:

Para cada nodo  la diferencia entre las alturas del sub arbol derecho y el sub arbol izquierdo debe ser menor que dos.

Degenerado:

cada nodo solo tiene un hijo, excepto la hoja.

Lleno:

Cada nivel tiene el maximo de nodos que soporta 

 

Practica:

 

 

 

 

Implementacion:

 

 

Arreglos

Nodos

Nota:

D=Dato.

Iz=Izquierda.

Der=Derecha.

 

Ahora realizaremos la codificacion de nuestro programa lo primero que hay que hacer es crear una clase con los atributos principales de nuestro programa. la llamaremos nodoArbolBin.

 

Public class nodoArbolBin<t>{

Private t dato;

Private nodoArbolBin izq;

Private nodoArbolBin der;

Public nodoArbolBin(T dato){

This.dato=dato;

Izq=der=null;

}

___

___              Get y Set

___

}

////////////////////////////////Clase Principal/////////////////////////

/*En esta clase estara la funcionalidad de nuestro programa*/

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 p=raiz.getsig();

raiz.setizq(new nodoArbolBin(“D”);

p=raiz.getDer();

p.setIzq(new nodoArbolBin(“E”);

p.setDer(new nodoArbolBin(“F”);

}

}

 

Recorridos Arboles Binarios. 

Lo que les mostrare ahora es como recorrer nuestro arbol binario utlizando los tipos de recorrido de PreOrden, InOrden, PosOrden los cuales ya los vimos en entradas antiguas del blog.

 

Actividad:

1. Visitar raiz(Mostrar)

2. Recorrer SubArbolIzq

3. Recorrer SubArbolDer

Recorridos

Pre:ABDCEF

In: DBAECF

Pos: DBEFCA

 

 

 

[ Modificado: martes, 9 de diciembre de 2014, 20:02 ]
 
Imagen de Miguel Angel Cano Dakin
de Miguel Angel Cano Dakin - lunes, 8 de diciembre de 2014, 08:33
Todo el mundo

Arboles binarios

En los arboles binarios cada nodo tiene como máximo dos hijos.

Aplicación:

Representación y evaluación de expresiones aritméticas, búsqueda y ordenamiento.

Terminología.

 

Completo: cada nodo tiene dos o cero descendientes.

Balanceado: para cada nodo la diferencia entre las alturas de su sub derecha y sub izquierda debe ser menos que dos.

Degenerado: cada nodo solo tiene un hijo, excepto la hoja.

Lleno: cada nodo tiene el máximo de dos nodos que soporta.

 ü   = verdadero

Arboles

A

B

C

D

Completo

ü   

X

X

ü   

Lleno

X

X

X

ü   

degenerado

X

X

ü   

X

balanceado

ü   

ü   

X

ü   

 

Implementación:

 

Arreglos

 

Para implementar en el código:

Public class nodo ArbolBin <T>{

 Private T dato;

 Private Nodo ArbolBin izq;

 Private Nodo ArbolBin der;

 Public nodo ArbolBin (T dato){

  This.dato = dato;

  Izq = der = null;

 }

}

Public class Principal {

 Public static void main(String arg[]){

  Nodo ArbolBin raíz;

  raíz = new Nodo ArbolBin(“A”);

  raíz.setIzq(new Nodo ArbolBin(“B”));

  raíz.setDer(new Nodo ArbolBin(“C”));

  Nodo ArbolBin p = raíz.getIzq();

  p.setIzq(new Nodo ArbolBin(“D”) );
  p = raíz.getDer();

  p.setIzq(new Nodo ArbolBin (“E”));

  p.setDer(new Nodo ArbolBin (“F”));

 }

}

Con el código anterior se creaban los nodos y se les enlazaba con sus respetivos padres para armar el árbol binario

Recorrido de árboles binario.

Actividades

1. visitar raíz

2. recorrer sub árbol Izquierdo

3. recorrer sub árbol Derecho

Recorrido     Combinación de actividades

Preorden       1,2,3

Inorden         2,1,3    

Posorden      2,3,1

 
Imagen de DAMASO SALGADO CASSIANI
de DAMASO SALGADO CASSIANI - domingo, 7 de diciembre de 2014, 17:38
Todo el mundo

Arboles

Son estructura de datos no lineal para organizar informacion por niveles.t

Utilidad: Organizacion de tipo jerarquico, se diferencia entre valores mayores y menores.

Aplicacion: Organigramas, geneologia, representacion y evaluacion de expresiones aritmetica, ordenamiento y busqueda.

Terminologia:

 

Altura: Es la cantidad de niveles que tiene el nodo, En este caso son 3

Peso: Cantidad de hojas= 7

Orden: Cantidad de nodos del arbol=10

 

Implementacion:

Arreglos

 

Nota: La primera columna de numero es la ubicacion de los vectores la cual utilizamos para guardar los datos en la direccion  "Padres".

 

Nodos

Nota: D=  Dato, H= Hermano, Hi= Hijos, "---"=null,  

 

 

 

[ Modificado: lunes, 8 de diciembre de 2014, 13:08 ]
 
Imagen de ANDRÉS STEVEN VIGOYA PÁJARO
de ANDRÉS STEVEN VIGOYA PÁJARO - domingo, 7 de diciembre de 2014, 17:12
Todo el mundo

 

 

Son arboles Binarios ABB mejorados que proveen un algoritmo de auto balanceo.

  • Criterios de autobalanceo por Altura

 

Existe algo llamado factor de Equilibrio ya que generó varias confusiones durante la explicación del tema, me parecio interesante y favorable compartir esta formula la cual hará mucho mas facil poder entender el factor de equilibrio

  • Operaciones AVL

Inserccion: Primero es el proceso ABB, pero adicionalmente se calcula en cada inserccion el FE Iniciando 

en la hoja insertado siguiendo la rama hasta la raiz, se pueden presentar los sigueintes casos.

1ro Llegar a la raiz

2do El FE=0 en algun nodo diferente a la hoja

3ro El FE muestra que hay desbalance, en este caso se reestructura el arbol en un proceso lladao rotacion.

Rotaciones

Rotacion II ( izquierda - izquierda)

 Rotacion DD (derecha derecha)

Rotacion ID (izquierda derecha)

Rotacion DI(Derecha Izquierda)

 

Eliminacion:

se aplica inicialmente la misma regla ABB, pero adicional mente se calcula el FE en la rama de la eliminación, si se detecta desbalance, se reestructura el árbol dependiendo del caso de rotación.

 

 Reflexion:

Los arboles AVL proponen un algoritmo que reestructura el árbol para recuperar su balance perdido en operaciones de inserción y eliminación.

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

 

 

¿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

 

  • Recorrido

 

 

  • 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"));

      }

}

  • Arboles binarios

Tienen una restriccion maxima, maximo dos hijos por nodos.

 

  • Arboles completos

Todos los nodos tienen dos hijos excepto las hojas.

  • Arboles balanceados

Parfa todos los nodos, la diferencia ente las alturas del subarbol izquierdo y derecho es menor a 2

  • Arboles llenos

Todos los niveles del arbol tiene el maximo de nodos 2^h-1. 

  • Arboles degenerados

Todos los nodos tienen un solo hijo excepto las hojas.

  • Ejemplos

  

 

Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son aquellos que se encuentran en el mismo nivel  
 
Padre: Es aquel que tiene hijos y también puede tener o no antecesores.  
 
Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es decir si tienen el mismo padre.  
 
Raíz: Es el nodo principal de un árbol y no tiene antecesores.   
 
Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos finales de un árbol. 
 
Interior: Se dice que un nodo es interior si no es raíz ni hoja. 
Todo el mundo
  • ¿Que Son arboles?

Son estructuras de datos no lineales para la organizacion de informacion con niveles.

  • Utilidad

Organizacion de datos de forma jerarquica (distancia entre mayores y menores)

  •  Aplicaciones

son aplicados en directorios, evaluacion de expresiones aritmeticas, busqueda y ordenamiento.

  • Terminologia. 

 

 

Arboles de expresión (Aplicación de arboles Binarios):

Consiste en la representación de una expresión  aritmética a través de un árbol complejo, donde los operadores son hojas y el resto de nodos los operadores,

Expresión

a+b*c

Posibles representaciones

 

 

[ Modificado: domingo, 7 de diciembre de 2014, 17:41 ]
 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...139   ()