Tarea #1 Arboles y Hash Table

Árbol
El arbol como estructura de datos es una de las las estructuras de datos más avanzadas, consiste en nodos organizados de manera jerárquica.

Cuando uno usa una base de datos hay un 99 % de probabilidad que un index esté involucrado. El simple tipo de index es una lista ordenada de un campo de llave. Esto provee una búsqueda rápida porque uno puede usar una búsqueda binaria para localizar cualquier artículo sin tener que que ver a cada uno.

Ejemplo de un árbol binario completo:


El problema viene cuando uno quiere añadir uno nuevo elemento y mantener la lista ordenada.



Ejemplo:

Código Java
Este es un ejemplo de Nodo:

public class Nodo{
    protected Object data;
    protected Nodo left,right;

    public Nodo(){
        data = null;
        left = right = null;
    }
    public Nodo(Object d){
        data = d;
        left = right = null;
    }
    public void setLeft(nodo l){
        left = l;
    }
    public void setRight(nodo r){
        right = r;
    }
    public void setData(Object d){
        data = d;
    }
    public Nodo getLeft(){
        return left;
    }
    public Nodo getRight(){
        return right;
    }
    public Object getData(){
        return data;
    }
    public String toString(){
        return ""+data;
    }
}

Utilizaremos el anterior nodo en el esqueleto del siguiente árbol binario:

import Nodo;

public abstract class ArbolBinario{
    private Nodo root;

    protected Nodo getRoot(){
        return root;
    }
    protected void setRoot(Nodo r){
        root = r;
    }
    public ArbolBinario(){
        setRoot(null);
    }
    public ArbolBinario(Object o){
        setRoot(new Nodo(o));
    }
    public boolean isEmpty(){
        return getRoot() == null;
    }
    public Object getData(){
        if(!isEmpty())
            return getRoot().getData();
        return null;
    }
    public Nodo getLeft(){
        if(!isEmpty())
            return getRoot().getLeft();
        return null;
    }
    public Nodo getRight(){
        if(!isEmpty())
            return getRoot().getRight();
        return null;
    }
    public void setData(Object o){
        if(!isEmpty())
            getRoot().setData(o);
    }
    public void insertLeft(Nodo p,Object o){
        if((p != null) && (p.getLeft() == null))
            p.setLeft(new Nodo(o));
    }
    public void insertRight(Nodo p,Object o){
        if((p != null) && (p.getRight() == null))
            p.setRight(new Nodo(o));
    }
    public void print(int mode){
        if(mode == 1) pretrav();
        else if(mode == 2) intrav();
        else if(mode == 3) postrav();
    }
    public void pretrav(){
        pretrav(getRoot());
    }
    protected void pretrav(Nodo p){
        if(p == null)
            return;
        System.out.print(p.getData()+" ");
        pretrav(p.getLeft());
        pretrav(p.getRight());
    }
    public void intrav(){
        intrav(getRoot());
    }
    protected void intrav(Nodo p){
        if(p == null)
            return;
        intrav(p.getLeft());
        intrav(p.getRight());
    }
    public void postrav(){
        postrav(getRoot());
    }
    protected void postrav(Nodo p){
        if(p == null)
            return;
        postrav(p.getLeft());
        postrav(p.getRight());
        
    }
}

La anterior clase contiene métodos importantes como lo son:

isEmpty() -> método para encontrar si el esta vacío el árbol.

getData() -> el cual retorna datos de el nodo raíz

getLeft() , getRight(), setData() , para manipular los nodos.

Tenemos otros métodos importantes como lo son post orden, inorden, pre orden, llamados en esta clase como:

pretrav()-> pre orden.

intrav()-> in orden.

postrav()->pos orden.

Los cuales necesitan ser en forma recursiva por facilidad de lectura y elegancia en el código, por lo cual se llama a sí mismas hasta que el nodo sea nulo.

Ejemplo de salida:

Numeros insertados:
500 315 219 359 259 816 304 902 681 334
Pre-order:
500 315 219 259 304 359 334 816 681 902
In-order:
219 259 304 315 334 359 500 681 816 902
Post-order:
304 259 219 334 359 315 681 902 816 500

Referencias:

Estructuras de datos en Java, Luis Joyanes Aguilar, Ignacio Zahonero Martínez, Mc Graw Hill, 2da Edición.

Hash Table

Básicamente esto se refiere a una tabla que asocia llaves y valores.

HashTable son muy sencillos de programar usando python porque se usan dictionaries, gracias a que es un lenguaje de alto nivel nos permite realizar un programa rápido y muy legible casi como pseudocódigo.

Lo que veeremos a continuación es cómo:
Inicializar
Mostrar
Copiar
Acceder a un elemento
Eliminar un elemento
Añadir un elemento

Código python

 
#inicializamos un diccionario
phoneNumbers = {'Johny': 88765643,
                       'Pedro': 77898765,
                       'Maria': 34543234,
                       'Alma':  43223456}

#copiamos todo a un nuevo dicccionario
newPhoneNumbers = phoneNumbers.copy() 

#Nos muestra el diccionario completo
print phoneNumbers

#Nos muestra las llaves o indices 
print phoneNumbers.keys()

#Para acceder a un elemento especifico
print newPhoneNumbers['Alma']

#Para eliminar un elemento especifico
del phoneNumbers['Pedro']

#Para insertar un nuevo elemento
phoneNumbers['nuevoamigo']=998987876
phoneNumbers['nuevoamigo2']=29898732

Referencias:

http://docs.python.org/2/tutorial/datastructures.html
http://mail.python.org/pipermail/python-list/2000-March/048085.html
http://es.wikipedia.org/wiki/Tabla_hash