Estructura de datos y algoritmos

Competencias: Aplicar modelos y tecnologías para el desarrollo de software utilizando principios de la ingeniería de software.

Estructuras de datos como

Binary Search Tree (BST) y High Binary Left Tree (HBLT)

import java.util.Queue;
import java.util.LinkedList;
public class BST
{
    private NodoBST raiz;
    private NodoBST tmp;
    private NodoBST ant;
    public BST(NodoBST nuevo){
        if(raiz==null){
            raiz = nuevo;
        }
    }

    public BST(int arr[]){
        for(int i=0; i<arr.length; i++){
            insertar(new NodoBST(arr[i]));
        }
    }

    public NodoBST getRaiz(){
        return raiz;
    }

    public void setRaiz(NodoBST raiz){
        this.raiz = raiz;
    }

    public void insertar(NodoBST nuevo){
        if(raiz==null){
            raiz=nuevo;
        } else{
            NodoBST temporal = raiz;
            while(true){
                if(nuevo.getInfo()<temporal.getInfo()){
                    if(temporal.getPunteroI()!=null){
                        temporal=temporal.getPunteroI();
                    } else{
                        temporal.setPunteroI(nuevo);
                        break;
                    }
                }else{
                    if(temporal.getPunteroD()!=null){
                        temporal=temporal.getPunteroD();
                    } else{
                        temporal.setPunteroD(nuevo);
                        break;
                    }
                }
            }
        }
    }

    public void recPreOrden(NodoBST raiz){
        if(raiz!=null){
            System.out.println(raiz.getInfo());
            recPreOrden(raiz.getPunteroI());
            recPreOrden(raiz.getPunteroD());
        }
    }

    public void recOrden(NodoBST raiz){
        if(raiz!=null){
            recOrden(raiz.getPunteroI());
            System.out.println(raiz.getInfo());
            recOrden(raiz.getPunteroD());
        }
    }

    public void recPosOrden(NodoBST raiz){
        if(raiz!=null){
            recPosOrden(raiz.getPunteroI());
            recPosOrden(raiz.getPunteroD());
            System.out.println(raiz.getInfo());
        }
    }

    public void recNivel(){
        Queue<NodoBST> cola = new LinkedList<NodoBST>();
        NodoBST tmp = raiz;
        cola.offer(tmp);
        while(!cola.isEmpty()){
            tmp = cola.poll();
            System.out.println(tmp.getInfo());
            if(tmp.getPunteroI()!=null){
                cola.offer(tmp.getPunteroI());
            }
            if(tmp.getPunteroD()!=null){
                cola.offer(tmp.getPunteroD());
            }
        }
    }

    private int grado(NodoBST nodo){
        int cont = 0;
        if(nodo.getPunteroI()!=null){
            cont++;
        }
        if(nodo.getPunteroD()!=null){
            cont++;
        }
        return cont;
    }

    public NodoBST buscar(int num){
        NodoBST tmp = raiz;
        while(tmp!=null){
            if(tmp.getInfo()==num){
                return tmp;
            }else if(num<tmp.getInfo()){
                ant = tmp;
                tmp = tmp.getPunteroI();//busca a la izq
            } else{
                ant = tmp;
                tmp = tmp.getPunteroD();//busca a la der
            }
        }
        return tmp;
    }
    
    public NodoBST eliminaGrado0(int num){
        NodoBST eliminado = buscar(num);
        if(eliminado==raiz){
            raiz = null;
        }else if(ant.getPunteroI().getInfo()==num){
            ant.setPunteroI(null);
        }else if(ant.getPunteroD().getInfo()==num){
            ant.setPunteroD(null);
        }
        return eliminado;
    }
    
    public NodoBST eliminaGrado1(int num){
        NodoBST eliminado = buscar(num);
        if(eliminado.getPunteroI()!=null){
            tmp = eliminado.getPunteroI();
        }else if(eliminado.getPunteroD()!=null){
            tmp = eliminado.getPunteroD();
        }
        //tmp = hijo del eliminado
        if(eliminado==raiz){
            raiz = tmp;
        }else if(ant.getPunteroI().getInfo()==num){
            ant.setPunteroI(tmp);
        }else if(ant.getPunteroD().getInfo()==num){
            ant.setPunteroD(tmp);
        }
        eliminado.setPunteroI(null);
        eliminado.setPunteroD(null);
        return eliminado;
    }
    
    public NodoBST eliminaGrado2(int num){
        NodoBST eliminado = buscar(num);
        tmp = eliminado.getPunteroI();
        while(tmp.getPunteroD()!=null){
            tmp = tmp.getPunteroD();
        }
        if(eliminado==raiz){
            raiz = tmp;
        }else if(ant.getPunteroI().getInfo()==num){
            ant.setPunteroI(tmp);
        }else if(ant.getPunteroD().getInfo()==num){
            ant.setPunteroD(tmp);
        }
        if(eliminado.getPunteroI()!=tmp){
            tmp.setPunteroI(eliminado.getPunteroI());
        }
        if(eliminado.getPunteroD()!=tmp){
            tmp.setPunteroD(eliminado.getPunteroD());
        }
        eliminado.setPunteroI(null);
        eliminado.setPunteroD(null);
        return eliminado;
    }
}

import java.util.Queue;
import java.util.LinkedList;
/**
 * High Binary Left Tree
 */
public class HBLT
{
    private Queue<NodoL> cola = new LinkedList<NodoL>();
    public HBLT(int [] arr){
        for(int num : arr){
            NodoL nodo = new NodoL(num);
            nodo.setS(1);
            nodo.setPtrI(new NodoL());
            nodo.setPtrD(new NodoL());
            cola.offer(nodo);
        }
    }
    public NodoL acomodarMayorPrecedencia(){
        while(cola.size()>1){
            NodoL nodo1 = cola.poll();
            NodoL nodo2 = cola.poll();
            NodoL nodoAux;
            if(nodo1.getInfo()<nodo2.getInfo()){
                nodoAux = nodo1;
                nodo1 = nodo2;
                nodo2 = nodoAux;
            }
            if(nodo1.getPtrD().getInfo()==0){
                nodo1.setPtrD(nodo2);
            }else if(nodo1.getPtrD().getInfo()>nodo2.getInfo()){
                nodo1.getPtrD().setPtrD(nodo2);
            }else{
                nodoAux = nodo1.getPtrD();
                NodoL raiz = nodo1;
                while(nodo2.getInfo()>nodoAux.getInfo()){
                    nodo1.setPtrD(nodo2);
                    nodo1 = nodo2;
                    nodo2 = nodo1.getPtrD();
                    nodo2.setS();
                    nodo1.setS();
                }
                nodo1.setPtrD(nodoAux);
                nodoAux.setPtrD(nodo2);
                nodo2.setS();
                nodoAux.setS();
                nodo1.setS();
                if(nodo1.getPtrI().getS()<nodo1.getPtrD().getS()){
                    nodoAux = nodo1.getPtrI();
                    nodo1.setPtrI(nodo1.getPtrD());
                    nodo1.setPtrD(nodoAux);
                    nodoAux.setS();
                }
                nodo1 = raiz;
            }
            if(nodo1.getPtrI().getS()<nodo1.getPtrD().getS()){
                nodoAux = nodo1.getPtrI();
                nodo1.setPtrI(nodo1.getPtrD());
                nodo1.setPtrD(nodoAux);
                nodoAux.setS();
            }
            nodo2.setS();
            nodo1.setS();
            cola.offer(nodo1);
        }
        return cola.poll();
    }
    public NodoL acomodarMenorPrecedencia(){
        while(cola.size()>1){
            NodoL nodo1 = cola.poll();
            NodoL nodo2 = cola.poll();
            NodoL nodoAux;
            if(nodo1.getInfo()>nodo2.getInfo()){
                nodoAux = nodo1;
                nodo1 = nodo2;
                nodo2 = nodoAux;
            }
            if(nodo1.getPtrD().getInfo()==0){
                nodo1.setPtrD(nodo2);
            }else if(nodo1.getPtrD().getInfo()<nodo2.getInfo()){
                nodo1.getPtrD().setPtrD(nodo2);
            }else{
                nodoAux = nodo1.getPtrD();
                NodoL raiz = nodo1;
                while(nodo2.getInfo() != 0 && nodo2.getInfo()<nodoAux.getInfo()){
                    nodo1.setPtrD(nodo2);
                    nodo1 = nodo2;
                    nodo2 = nodo1.getPtrD();
                    nodo2.setS();
                    nodo1.setS();
                }
                nodo1.setPtrD(nodoAux);
                nodoAux.setPtrD(nodo2);
                nodo2.setS();
                nodoAux.setS();
                nodo1.setS();
                if(nodo1.getPtrI().getS()<nodo1.getPtrD().getS()){
                    nodoAux = nodo1.getPtrI();
                    nodo1.setPtrI(nodo1.getPtrD());
                    nodo1.setPtrD(nodoAux);
                    nodoAux.setS();
                }
                nodo1 = raiz;
            }
            if(nodo1.getPtrI().getS()<nodo1.getPtrD().getS()){
                nodoAux = nodo1.getPtrI();
                nodo1.setPtrI(nodo1.getPtrD());
                nodo1.setPtrD(nodoAux);
                nodoAux.setS();
            }
            nodo2.setS();
            nodo1.setS();
            cola.offer(nodo1);
        }
        return cola.poll();
    }
}

Reflexión

Una estructura de datos es una forma particular de organizar datos en una computadora para que puedan ser utilizados de manera eficiente. Diferentes tipos de estructuras de datos son adecuados para diferentes tipos de aplicaciones, y algunos son altamente especializados para tareas específicas.

Las estructuras de datos son un medio para manejar grandes cantidades de datos de manera eficiente para usos tales como grandes bases de datos y servicios de indización de Internet.

Las diferentes estructuras de datos nos proporcionan un orden y un enlace entre todos los datos. Ejemplo más sencillos de estas estructiras son arrays, vectores, matrices; más complejos: Listas enlazadas(simples, dobles, circulares), pilas , colas , árboles binarios, entre otros.