Árbol roji-negro gráfico en Java.

Otro de mis proyectos de la época universitaria, otro árbol roji-negro, en una entrada de hace tiempo publique un árbol roji-negro en c ahora me he encontrado este en java y modo gráfico.




Tal como se puede apreciar en la imagen este programa implementa las acciones de insertar y buscar un nodo, además de mostrar el arbol en modo gráfico. El programa consta de dos clases principales y algunas clases internas, a continuación el código fuente, el cual tiene varios comentarios, donde se habla de casos se refiere a los mostrados en la entrada árbol roji-negro en c

public class Nodo{

  public int numero; // el numero del nodo
  public boolean rojo; // indica true es rojo; false es negro
  public Nodo izquierdo; // apuntador al nodo hijo izquierdo
  public Nodo derecho; // apuntador al nodo hijo derecho
  public Nodo padre; // apuntador al nodo padre
  public String texto; // texto del nodo

  // contruye un nuevo nodo asignadole numero, texto y su color
  public Nodo(int numero, String texto, boolean rojo){
    this.numero=numero;
    this.texto=texto;
    this.rojo=rojo;
    izquierdo=null;
    derecho=null;
    padre=null;
  }
}

// version del compilador java 1.6.0_13
import java.awt.*;
import java.awt.event.*;

public class Window extends Frame implements ActionListener{

  private TextField textoNumero; // campo para ingresar el numero del nuevo nodo que se desea insertar
  private TextField textoString; // campo para ingresar el texto del nuevo nodo que se desea insertar
  private Button botonInserta; // boton para la accion de insertar un nuevo nodo
  private TextField texto2Numero; // campo para ingresar el numero del nodo que se desea buscar
  private Button botonBusca; // boton para la accion de buscar un nodo
  private TextField textoMensaje; // campo para mandar mensajes al usuario
  private Nodo primerNodo; // nodo raiz del arbol
  private ScrollPane scrollpane; // area para desplegar el arbol graficamente
  private Label grafica; // control utilizado para graficar el arbol
  private Nodo nodEncontrado; // para busquedas guarda la referencia del nodo encontrado para resaltarlo

  // constructor de la clase crea la ventana y sus controles
  public Window(){
    // creando los controles y sus caracteristicas
    Panel pan1=new Panel(new GridLayout(3,0));
    Panel reg1=new Panel(new FlowLayout());
    textoNumero = new TextField(5);
    textoString = new TextField(35);
    Button botonInserta = new Button("Insertar");
    botonInserta.addActionListener(this);
    Panel reg2=new Panel(new FlowLayout());
    texto2Numero = new TextField(5);
    botonBusca = new Button("Buscar");
    botonBusca.addActionListener(this);
    Panel reg3=new Panel(new FlowLayout());
    textoMensaje = new TextField(65);
    textoMensaje.setEditable(false);
    grafica=new Label(){ // sobrecarga del metodo paint del control para hacer que dibuje el arbol
      public void paint(Graphics grph){
        dibujaArbol(grph);
      };
    };
    scrollpane=new ScrollPane(ScrollPane.SCROLLBARS_AS_NEEDED);
    scrollpane.add(grafica);
    pan1.add(reg1);
    pan1.add(reg2);
    pan1.add(reg3);
    reg1.add(botonInserta);
    reg1.add(new Label("Numero:"));
    reg1.add(textoNumero);
    reg1.add(new Label("String:"));
    reg1.add(textoString);
    reg2.add(botonBusca);
    reg2.add(new Label("Numero:"));
    reg2.add(texto2Numero);
    reg3.add(new Label("Mensaje:"));
    reg3.add(textoMensaje);
    add(pan1,BorderLayout.NORTH);
    add(scrollpane,BorderLayout.CENTER);
    addWindowListener(new WindowAdapter(){
      public void windowClosing(WindowEvent e){
        System.exit(0);
      }
    });
    primerNodo=null;
    nodEncontrado=null;
    // dandole caracteristicas a la ventana
    setTitle("Arbol roji-negro");
    setSize(666,578);
    setVisible(true);
  }

  // realiza lass opciones de los botones
  public void actionPerformed(ActionEvent e){
    Button fuente=(Button)e.getSource();
    int numero=0;
    String textonum="";
    textoMensaje.setText("");
    nodEncontrado=null;
    try{
      if(fuente.getLabel().equals("Insertar")){
        // inserta un nuevo nodo si el numero ingresado es un entero valido y la string no esta vacia
        if(textoString.getText().length()==0){
          // si la cadena string no fue ingresada enviar mensaje de error
          textoMensaje.setText("String vacia");
          return;
        }
        textonum=textoNumero.getText();
        numero=Integer.parseInt(textonum);
        insertaUnNodo(numero,textoString.getText());
        textoMensaje.setText("Insertado "+numero);
      }
      else if(fuente.getLabel().equals("Buscar")){
        // busca un nodo si el numero ingresado es un entero valido
        textonum=texto2Numero.getText();
        numero=Integer.parseInt(textonum);
        nodEncontrado=buscaUnNodo(numero);
        if(nodEncontrado==null) textoMensaje.setText("No se encontro");
        else textoMensaje.setText("Encontrado: ["+nodEncontrado.numero+","+nodEncontrado.texto+"]");
      }
    }
    catch(NumberFormatException ex){
      // si el numero no es valido enviar mensaje de error
      textoMensaje.setText("Error numero: ["+textonum+"]");
    }
    grafica.repaint();
  }

  // metodo que inserta el nodo en el arbol recibe el numero y texto del nuevo nodo
  private void insertaUnNodo(int numero, String texto){
    Nodo nuevoNodo;
    boolean esHijoDer;
    if(primerNodo==null) // ve si el arbol esta vacio y crea el nodo como raiz
      primerNodo=new Nodo(numero,texto,false);
    else{
      nuevoNodo=new Nodo(numero,texto,true);
      nuevoNodo.padre=primerNodo;
      while(true){ 
        // recorre los nodos que existan para buscar el lugar del nuevo nodo en base a su numero
        if(numero<nuevoNodo.padre.numero){
          if(nuevoNodo.padre.izquierdo!=null) nuevoNodo.padre=nuevoNodo.padre.izquierdo;
          else{
            nuevoNodo.padre.izquierdo=nuevoNodo;
            esHijoDer=false;
            break;
          }
        }
        else{
          if(nuevoNodo.padre.derecho!=null) nuevoNodo.padre=nuevoNodo.padre.derecho;
          else{
            nuevoNodo.padre.derecho=nuevoNodo;
            esHijoDer=true;
            break;
          }
        }
      };
      // en caso de que se presente que el padre del nuevo nodo es rojo envia al metodo que soluciona esto
      if(nuevoNodo.padre.rojo) casoRojoRojo(nuevoNodo.padre,esHijoDer);
    }
    // actualizar la grafica del arbol
    grafica.repaint();
  }

  // soluciona si al insertar se presenta un caso donde el nodo padre del nuevo nodo es rojo
  private void casoRojoRojo(Nodo n, boolean hijoDer){
    Nodo padreDePadre=n.padre;
    Nodo hermanoDePadre;
    Nodo temporal;
    if(padreDePadre.izquierdo!=null && padreDePadre.derecho!=null){
      // caso uno y dos: volver a colorear
      if(n==padreDePadre.izquierdo) hermanoDePadre=padreDePadre.derecho;
      else hermanoDePadre=padreDePadre.izquierdo;
      if(hermanoDePadre.rojo){
        hermanoDePadre.rojo=false; n.rojo=false;
        if(padreDePadre!=primerNodo) padreDePadre.rojo=true;
        if(padreDePadre.padre!=null){
          if(padreDePadre.padre.rojo) // revisar que no se haya creado un caso rojo-rojo hacia arriba
            casoRojoRojo(padreDePadre.padre,padreDePadre.padre.izquierdo!=padreDePadre);
        }
        return;
      }
    }
    if(!hijoDer && padreDePadre.izquierdo==n){
      // caso tres: reestructurar
      n.rojo=false; padreDePadre.rojo=true;
      temporal=n.derecho; n.derecho=padreDePadre; n.padre=padreDePadre.padre;
      padreDePadre.padre=n; padreDePadre.izquierdo=temporal;
      if(temporal!=null) temporal.padre=padreDePadre;
      if(n.padre!=null){
        temporal=n.padre;
        if(temporal.izquierdo==n.derecho) temporal.izquierdo=n;
        else temporal.derecho=n;
      }
      else primerNodo=n;
    }
    else if(hijoDer && padreDePadre.derecho==n){
      // caso cuatro: reestructurar
      n.rojo=false; padreDePadre.rojo=true;
      temporal=n.izquierdo; n.izquierdo=padreDePadre; n.padre=padreDePadre.padre;
      padreDePadre.padre=n; padreDePadre.derecho=temporal;
      if(temporal!=null) temporal.padre=padreDePadre;
      if(n.padre!=null){
        temporal=n.padre;
        if(temporal.izquierdo==n.izquierdo) temporal.izquierdo=n;
        else temporal.derecho=n;
      }
      else primerNodo=n;
    }
    else if(hijoDer && padreDePadre.izquierdo==n){
      // caso cinco: reestructurar
      hermanoDePadre=n.derecho; temporal=hermanoDePadre.izquierdo; padreDePadre.izquierdo=hermanoDePadre;
      hermanoDePadre.padre=padreDePadre; hermanoDePadre.izquierdo=n; n.padre=hermanoDePadre;
      n.derecho=temporal;
      if(temporal!=null) temporal.padre=n;
      // lleva al caso tres
      casoRojoRojo(hermanoDePadre,false);
    }
    else if(!hijoDer && padreDePadre.derecho==n){
      // caso seis: reestructurar
      hermanoDePadre=n.izquierdo; temporal=hermanoDePadre.derecho; padreDePadre.derecho=hermanoDePadre;
      hermanoDePadre.padre=padreDePadre; hermanoDePadre.derecho=n; n.padre=hermanoDePadre;
      n.izquierdo=temporal;
      if(temporal!=null) temporal.padre=n;
      // lleva al caso cuatro
      casoRojoRojo(hermanoDePadre,true);
    }
  }

  // metodo para buscar un nodo si no lo encuentra regresa null
  private Nodo buscaUnNodo(int numero){
    Nodo temporal=primerNodo;
    if(temporal==null) return null;
    do{
      if(numero==temporal.numero) return temporal;
      else if(numero<temporal.numero) temporal=temporal.izquierdo;
      else if(numero>temporal.numero) temporal=temporal.derecho;
    }while(temporal!=null);
    return null;
  }

  // funcion que prepara el control grafica para dibujar el arbol
  private void dibujaArbol(Graphics grph){
    // tamaño del nodo 50x50 espacio entre nodos vertical 20 horizontal minimo 20
    // calcular tamaño de toda la grafica
    int altura=calculaProfundidad(primerNodo);
    int anchura=(int)Math.pow(2,(altura-1));
    if(altura==0) return;
    grafica.setPreferredSize(new Dimension((anchura*70)+40,(70*altura)+20));
    grph.setColor(Color.WHITE);
    grph.clearRect(0,0,(anchura*70)+40,(70*altura)+20);
    // enviar a dibujar el nodo raiz y este a su vez enviara al resto de los nodos
    dibujaNodo(grph,primerNodo,25,(int)((70*anchura))/2);
    scrollpane.doLayout();
  }

  // calcula la el numero de nodos de profundidad del arbol para calcular el arrea que ocupara el grafico
  // segun el numero de nodos
  private int calculaProfundidad(Nodo inicial){
    int profIzq=0;
    int profDer=0;
    if(inicial==null) return 0;
    if(inicial.izquierdo!=null)
      profIzq=calculaProfundidad(inicial.izquierdo);
    if(inicial.derecho!=null)
      profDer=calculaProfundidad(inicial.derecho);
    return (profIzq>profDer?profIzq:profDer)+1;
  }

  // dibuja un nodo y si este nodo tiene al menos un hijo tambien lo envia a dibujar
  private void dibujaNodo(Graphics grph, Nodo nodo, int y, int x){
    Color color=(nodo!=null?(nodo.rojo?Color.RED:Color.BLACK):Color.YELLOW);
    int altura=calculaProfundidad(nodo)-1;
    int anchura=(int)Math.pow(2,altura);
    anchura=((anchura*70)+40)/4;
    if(nodo!=null && (nodo.izquierdo!=null||nodo.derecho!=null)){
      grph.setColor(Color.GREEN);
      grph.drawLine(x+25,y+25,x-anchura+25,y+95);
      grph.drawLine(x+25,y+25,x+anchura+25,y+95);
    }
    grph.setColor(color);
    if(nodo!=null && nodo.rojo) grph.fillRect(x,y,50,50);
    grph.fillOval(x,y,50,50);
    if(nodo!=null){
      if(nodo==nodEncontrado){
        grph.setColor(Color.GREEN);
        for(int c=2;c<=3;c++)
          if(!nodEncontrado.rojo) grph.drawOval(x+c,y+c,48-(2*c),48-(2*c));
          else grph.drawRect(x+c,y+c,49-(2*c),49-(2*c));
      }
      grph.setColor(nodo.rojo?Color.BLACK:Color.WHITE);
      grph.drawString(""+nodo.numero,x+20,y+30);
      if(nodo.izquierdo!=null||nodo.derecho!=null){
        dibujaNodo(grph,nodo.izquierdo,y+70,(x-anchura));
        dibujaNodo(grph,nodo.derecho,y+70,(x+anchura));
      }
    }
    else{
      grph.setColor(Color.BLACK);
      grph.drawString("null",x+15,y+30);
    }
  }

  public static void main(String[] args){
    Window win = new Window();
  }
}


Comentarios

  1. Hola, muy buen trabajo, como se podría modificar dicho programa para dar la opción también de eliminar un elemento?

    ResponderEliminar
    Respuestas
    1. Habria que implementar la reestructuracion al momento de eliminar, aca http://es.wikipedia.org/wiki/%C3%81rbol_rojo-negro#Eliminaci.C3.B3n hay una explicacion y algo de codigo de ejemplo (en c), solo seria seguires logica:

      Eliminar

Publicar un comentario

Entradas populares