Tarea 3: Algoritmos de Búsqueda en Java - Nathalia Astorga.-

Estructuras de Datos y Algoritmos de Búsqueda

Dentro del Lenguaje JAVA y de tantos otros encontramos diversas estructuras de datos, estos se originan con la programación estructurada. Una estructura de datos es una forma de organizar un conjunto de datos elementales, con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente.

Una estructura de datos define la organización e interrelación de estos, y un conjunto de operaciones que se pueden realizar sobre él. Las operaciones base de estos son:

• Insertar, agrega nuevos elementos a la estructura.
• Borrar, elimina un valor de la estructura.
• Buscar, encuentra un determinado valor en la estructura para realizar una operación con este. en forma secuencial o binario.
• Ordenamiento, ordena los elementos que pertenecen a la estructuras.

Cada estructura ofrece distintas ventajas y desventajas, siendo unas mas usadas que otras, o mas cómodas de usar dependiendo del objetivo del programa que se desea desarrollar y las funciones que este deba cumplir.

Las estructuras de datos mas usadas en la programación son:

• Array (Vectores y Matrices)
• Listas
• Pilas
• Colas
• Arboles
• Hash
• etc...

Acceso a los datos

Los accesos a los datos en estas estructuras pueden ser de orden Secuencial, Directo o Aleatorio.

• Secuencial. Para acceder a un objeto se debe acceder a los objetos almacenados previamente en el archivo. El acceso secuencial exige elemento a elemento, es necesario una exploración secuencial comenzando desde el primer elemento.
• Directo o Aleatorio. Se accede directamente al objeto, sin recorrer los anteriores. El acceso directo permite procesar o acceder a un elemento determinado haciendo una referencia directamente por su posición en el soporte de almacenamiento.

Estructuras de datos que utilizaremos.

Arreglo

Un arreglo se usa para agrupar, almacenar y organizar datos de un mismo tipo, en un arreglo cada valor se almacena en una posición ennumerada específica dentro del arreglo. El número correspondiente a cada posición se llama índice. Normalmente el primer elemento va en el índice de valor 0. Su forma gráfica se puede apreciar de la siguiente manera:

Arbol

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. También se da una definición recursiva para este  "un árbol es una estructura compuesta por un dato y varios árboles", la forma gráfica se puede apreciar de la siguiente forma:

Los nodos pueden ser hijos, o padres, dependiendo de si tienen un puntero apuntando desde o hacia ellos.

Nodo Hijo: Cualquier nodo apuntado por uno de los nodos del árbol, ejemplo: 7 y 5 son hijos de 2

Nodo Padre: Nodo que contiene un puntero al nodo actual. En el ejemplo 6 es padre de 5 y 11.

Con respecto a la posición dentro del árbol tenemos:

Nodo Raíz: Este es el nodo que usaremos siempre para acceder al árbol, no tiene padre. En el ejemplo es 2.

Nodo Hoja: Nodo que no tiene hijos, en el ejemplo  hay varios, 2, 5, 11 y 4.

Otros conceptos usados en los arboles son:

Orden: es el número potencial de hijos que puede tener cada elemento del árbol.

Grado: es el número de hijos que tiene el elemento con mas hijos dentro del árbol.

Nivel: para cada elemento del árbol se define como la distancia a la raiz, esta se mide en nodos siendo siempre el nivel de la raiz 0.

Altura: es el nivel del nodo de mayor nivel.

Arboles Binarios.

Los árbol de orden o árbol binario requiere una estructura de NODO que permita almacenar el dato correspondiente, además de una referencia al Hijo Izquierdo y una al Hijo Derecho. El árbol sera una alianza al nodo raíz, y a partir de este se podrá acceder al resto de la estructura.

Algoritmos de Búsqueda

Los algoritmos de búsqueda son un conjunto de instrucciónes que permiten que se encuentre un elemento de una estructura de datos, ya sea para verificar su existencia o nulidad de esta. O para desarrollar futuras funciones con esta información.

TAREA 3 :

• En forma individual, investigar e implementar en Java un algoritmo de búsqueda. Se recomienda que desarrolle un programa que permita crear un árbol binario, recorrerlo en diferente orden, y haber búsqueda de un elemento dentro del árbol. También puede usar otra estructura de datos.
• Publicar en su blog y responder esta entrada, indicando su nombre y la url de su tarea en el blog de su grupo. 

Búsqueda en Arreglo

package binario;


public class Binario {


    public static void main(String[] args) {
        int arr1 [] = {1,2,3,4,5,6,7,8,9,10};
        int n = 2;
        int posini = 0;
        int posfin = arr1.length -1;
        int poscen;
        
        while(posini<=posfin)
        {
            poscen = (posfin + posini)/2;
            if(arr1[poscen]== n){
                System.out.println("Dato encontrado entre las posiciones " +posini+ " y "+posfin);
                break;
            }else if(n< arr1[poscen])
            {
                posfin = poscen-1;
            }else{
            
               posini = poscen +1;
            }
        }
    }
}

Búsqueda en árboles

public class singleNode {

    private Object info;
    public singleNode next;

    public singleNode(Object info){
        this.info = info;
        next = null;
    }

    public void setInfo(Object info){
        this.info = info;
    }

    public Object getInfo(){
        return this.info;
    }

    public Object popInfo(){
        Object temp = this.info;
        this.info = null;
        return temp;
    }

}

public class BinaryTreeNode {

    public BinaryTreeNode parent;
    public BinaryTreeNode leftChild;
    public BinaryTreeNode rightChild;

    private String info;

    public BinaryTreeNode(String info){
        this.parent = null;
        this.leftChild = null;
        this.rightChild = null;
        this.info = info;
    }

    public String getInfo(){
        return this.info;
    }

    public void setInfo(String info){
        this.info = info;
    }

}

public class BinarySearchTree {

    private BinaryTreeNode root;

    public BinarySearchTree(){
        this.root = null;
    }

    public void insertNode(BinaryTreeNode node){
        if (this.root == null){
            this.root = node;
        }
        else{
            trackPosition(node, this.root);
        }
    }

    private void trackPosition(BinaryTreeNode node, BinaryTreeNode start){
        String sInfo = start.getInfo();
        if (sInfo.compareTo(node.getInfo()) > 0){
            if (start.leftChild == null){
                start.leftChild = node;
                node.parent = start;
            }
            else{
                trackPosition(node, start.leftChild);
            }
        }
        else{
            if (start.rightChild == null){
                start.rightChild = node;
                node.parent = start;
            }
            else{
                trackPosition(node, start.rightChild);
            }
        }
    }

}

Bibliografía-

Estructura de datos en Java - Luis Joyanes, Ignacio Zahonero (McGraw Hill)