26 de mayo de 2009

Definiciones Básicas

2° Estructuras:

- Lineales (listas, colas, bicolas, pilas...)

- No Lineales (árboles)

3° Estructuras Recursivas

4° Estructuras Relacionales

5° Ordenamiento y Búsqueda

Mapa Conceptual


-Arboles


- Clase Nodo Binario

- Clase Árbol Binario

- Tamaño

- Altura




Exposición Ordenamiento por HeapSort










29 de abril de 2009

Programa Recorrido Arbol

public class Test
{
public static void main(String args[])
  {
  CArbolBinarioDeBusqueda arbolbb=new CArbolBinarioDeBusqueda();
  String nombre;
  double nota;
  int i=0,cod;
  System.out.println("Introducir datos. Finalizar con Ctrl+z.");
  System.out.println("nombre: ");
  while((nombre=Leer.dato())!=null)
 {
  System.out.print("nota: ");
  nota=Leer.datoDouble();
  cod=arbolbb.insertar(new CDatos(nombre,nota));
  if(cod==CArbolBinarioDeBusqueda.YA_EXISTE)
  {
  CDatos datos=(CDatos)arbolbb.buscar(new CDatos(nombre,nota));
   if(nota>=0)
   datos.asignarNota(nota);
    else
   {
   if(arbolbb.borrar(new CDatos(nombre,nota))==null)
  System.out.println("nodo borrado porque no existe");
  else
  System.out.println("nodo borrado");
 }
  }
  System.out.print("nombre: ");
  }
   System.out.println("\n");
               
  System.out.println("\nArbolInorden: ");

 arbolbb.visitarInorden();
 System.out.println("\nArbol posorden: ");

 arbolbb.visitarPosorden();

 System.out.println("\nArbol preorden: ");

 arbolbb.visitarPreorden();
                }
}

SeudoCodigo Recorrido Arbol




 

Mapa Conceptual Arboles

Arbol B+

Arbol B+

     Caracteristicas:
  • Nodos internos solo contienen las claves o apuntadores
  • Todas las hojas se encuentran al mismo nivel
  • Nodos hojas se encuentran ligadas como una lista enlazada para permitir la busqueda mas eficiente 
  • El minimo numero de Claves es 2
EJEMPLO:

Construir TB+[37,48,55,61,73,77,80,87,92]



Arbol B

Arbol B

   Caracteristicas:
  •  Conserva las caracteristivas del arbol binario, AVL, ABB
  • Se busca la clave a insertar
  • Si no esta en el arbol se comienza a insertar
  • ¿ Esta llena la Pagina?
  • Se divide la pagina en 2 paginas el mismo nivel , extrayendo la clave media 
  • Con esta medida se sube por el camino de busqueda y se comienza el proceso nuevamente
EJEMPLO: 
Construir el arbol B  TB=[55,77,37,48,61,73,80,87,87,92]



Recorridos

Preorden

void preorder (){
System.out.println(d);
if (izq != null)
izq.preorder();
if (der != null)
der.preorder();
}

Postorden

void postorder (){
if (izq != null)
izq.postorder();
if (der != null)
der postorder();
der.System.out.println(d);
}

Inorden

void inorder (){
if (izq != null)
izq.inorder();
System.out.println(d);
if (der != null)
der.inorder();
}

Algoritmo Basico

Algoritmo Basico
  • Tamaño (número de nodos)
  • Profundidad de un nodo
  • Altura
  • Recorridos
  • Euler
  • Pre-, in- y post-orden
  • Suponemos árboles binarios para simplifica
Clase Nodo binario

Class NodoB {
Object d;
NodoB izq;
NodoB der;
NodoB() {this(null);}
NodoB(Object o) {this(o,null,null);}
NodoB(Object o, NodoB i, NodoB d)
{d=o; izq=i; der=d;}
static int size ( NodoB a){...;}
static int height (NodoB a){...;}
void preorder (NodoB a){...;}
void inorder (NodoB a){...;}
void postorder (NodoB a){...;}
}

Clase Árbol binario

protected NodoB raiz;
ArbolB() {raiz=null;}
ArbolB(Object o){raiz=new NodoB(o);}
public int size()
{return NodoB.size(raiz);}
public int height()
{return NodoB.height(raiz);}
public void preorder ()
p p {if (raiz!=null) raiz.preorder();}
public void inorder ()
{if (raiz!=null) raiz.inorder();}
public void postorder ()
{if (raiz!=null) raiz.postorder();}
}

 Tamaño

static int size (NodoB a){
if (a==null)
return 0;
else
return 1+size(a.izq)+size(a.der);
}

Altura
 
static int height (NodoB a){
if (a==null)
return (-1);
else
return 1+Math.max(height(a.izq),
height(a.der));
}

27 de abril de 2009

Estructuras Recursivas

ÁRBOLES

Árboles: Es un conjunto de nodos, en cada nodo hay información.

Características:

  • Árbol vacio T = 0
  • Raíz: se desprenden los subárboles.
  • Longitud: cantidad de ramas o aristas desde la raíz hasta el nodo de referencia.
  • Profundidad: niveles de árbol, desde la raíz hasta nodo más profundo.
  • Grado: la cantidad de ramas en una sola raíz.
  • Recorrido: ancho, preorden, inorden y postorden.
  • Tamaño: el número de nodos que tiene el árbol.
  • Árbol binario: es cuando el grado del árbol es 2.
  • Árbol de busqueda: contiene un factor de equilibrio dado por la altura del hijo derecho menos (-) el hijo izquierdo. FE <= 1

Operaciones árboles

  • Buscar
  • Insertar
  • Eliminar

"recorrido inorden es el que ordena un árbol"

"árbol de busqueda organizado AVAL"

"árbol degenerado: que queda todo hacia un solo lado"

IMPLEMENTACIÓN DE ÁRBOLES BINARIOS

  • arreglo: estructura estática.
  • como estructuras ligadas se debe definir el tamaño del arreglo y NUNCA cambiarlo.
  • overflow: desborde de información.

Árboles multicaminos

  • árboles B
  • árboles B+

Características

  • árboles binarios
  • AVL
  • ABB
  1. Nodo padre: mínimo un elemento y max. de 2n
  2. páginas intermedias, almacenar entre n (mínimo) y un max. de 2n.
  3. Todas las hojas deben tener la misma altura.

ÁRBOL B+

características:

  • Nodos internos solo contienen claves o apuntadores
  • Todas las hojas se encuentran al mismo nivel
  • Nodos hoja, se encuentran ligadas como una lista enlazada para permitir la busqueda más eficiente.
  • El mínimo número de claves es 2.

operaciones:

  • Buscar
  • Insertar
  • Eliminar

21 de febrero de 2009

Ejercicios

  • Factorial

public class factorial {
private static inout io = new inout();
public static void main (String args[]) throws Exception
{
int a,m,p;a=io.readint();m=factorialrec(a);p=factorial2(a);io.writeln(m);io.writeln(p);
}
public static int factorialrec(int x)
{
int aux;aux=1;if (x==0)aux=1;else aux=aux*factorialrec(x-1);return aux;
}
public static int factorial2(int x)
{
int i,f;i=0;f=1;while (i != x)
{
i=i+1;f=f*i;}
return f;
}
}

  • Fibonacci

public class Fibonacci {

public static long fib(int n)

{

if (n <= 1) return n;

else

return fib(n-1) + fib(n-2);

}

public static void main(String[] args) {

int N = Integer.parseInt(args[0]);

for (int i = 1; i <= N; i++)

System.out.println(i + ": " + fib(i));

}

}

  • Algoritmo Recursivo Torres de Honoi
Hanoi (dim N , palo A, palo B , palo C)
// N, origen, destino , auxiliar
Si N == 1
Imprimir : Pasar disco de A a B
else
Hanoi(N-1 , A , C, B)
Imprimir : Pasar disco de A a B
Hanoi(N-1 , C , B , A)

14 de febrero de 2009

Defeniciones Basicas

  • Dato: Unidad mínima de información. En programación, es la expresión general que describe las características de las entidades sobre las cuales opera un algoritmo.
  • Dato Abstracto (TDA/TAD/ADT): Defino un objeto, propiedad, operación y omito características del objeto como tal
  • Encapsulamiento: Oculta informaión.
  • Recursividad: Es una técnica de programación (puedo invocar una función).
  • Recursividad Directa: Procedimiento, hay una llamada a la misma función.
  • Recursividad Indirecta: Procedimiento que invoca otro procedimiento para llamar a una función.
  • Recursividad Cola: Última instrucción que ejecuta el procedimiento.
  • Algoritmo: Es un conjunto de instrucciones bien definidas, ordenadas y finitas de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución.
  • Pila: Se intoducen o se quitan elementos por el mismo extremo.
  • Lifo: Ultimas en entrar, primeras en salir.
  • Fifo: Primeras en entrar, pimeras en salir.

Estructuras Lineales

  1. Lista: Conjunto de elementos llamados nodos.
  2. Arreglos: Estáticos, tienen un tamaño definido.
  3. Elementos Enlazados: Dinámicos, tamaño indiferente.
  • Operaciones: insertar, borrado, buscar, recorrer, vacio, tamaño.
  • public void insertar ( String Elemento);
  • public boolean eliminar (String elemento);
  • public String eliminar ();
  • public boolean busacr (String elemento);
  • public String recorrer ();
  • public boolean vacio ();
  • puiblic int tamaño ();
  1. Listas Enlazadas:
  • Eliminar:
  1. removeFirst: elimina el primer elemento de la lista.
  2. removeLast: elimina el último elemento de la lista.
  3. remove: elimina un elemento concreto de la lista.
  • Buscar:
  1. First: examina primer elemento de la lista.
  2. Last: examina el último elemento de la lista.
  3. Contains: determina si la lista tiene un elemento en particular.

isEmpty: determina si la lista esta vacia.

Size: determina en número de elementos en la lista.

  1. Pila: Se introducen o se quitan elementos por el mismo extremo.
  • Operaciones: push, pop, peek, IsEmpty, IsFull, Size.
  • Push: añadir a un elemento a la pila (apilar).
  • Pop: Quitar un elemento a la pila (desapilar).
  • Peek: Se mira el tope de la pila.
  • IsEmpty: (Esta vacia) determinar que la pila no tiene elementos.
  • IsFull: (Esta llena) determinar si la pila esta llena.
  • Size: Determinar el número de elementos de la pila.