Árbol AVL

Este es el código de un árbol AVL, para utilizarlo se debe de sobrecargar el método toString de los clases que se van a insertar <<You should override toString function on your custom classes>>. También se debe usar la clase StringHandler que afina las comparaciones de modo que no existan excepciones por caracteres inválidos o errores por mayúsculas, todo esto se aplica en la sobrecarga del método toString <<Also, you need to use (in toString function) StringHandler class to prevent any exception if a string has a non-valid character (for example ñ,.,é)>>. Este ejemplo incluye un método para obtener la cadena que sirve para graficar en el árbol en Graphviz. <<This example includes a function that returns a string useful to draw AVL Trees using Graphviz>>. De último hay un ejemplo de uso <<At the end, there is a how to use example>>

Archivo: StringHandler.java

package edd;

import java.text.Collator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @author julian
 * 
 */
public final class StringHandler {

 public static String clearString(String cadena) {
  return clearTildes(
    clearBlankSpaces(replaceBlankSpaces(clearChars(cadena))))
    .toLowerCase();
 }

 public static String replaceBlankSpaces(String cadena) {
  return cadena.replaceAll("\\s+", "_");
 }

 public static String clearBlankSpaces(String cadena) {
  return cadena.trim();
 }

 public static String clearTildes(String cadena) {
  String cleanString = "";
  Collator comparador = Collator.getInstance();
  comparador.setStrength(Collator.PRIMARY);
  for (int i = 0; i < cadena.length(); i++) {
   String caracter = String.valueOf(cadena.charAt(i));
   if (comparador.compare(caracter, "a") == 0)
    cleanString += "a";
   else if (comparador.compare(caracter, "e") == 0)
    cleanString += "e";
   else if (comparador.compare(caracter, "i") == 0)
    cleanString += "i";
   else if (comparador.compare(caracter, "o") == 0)
    cleanString += "o";
   else if (comparador.compare(caracter, "u") == 0)
    cleanString += "u";
   else
    cleanString += caracter;
  }

  return cleanString;
 }

 public static String clearChars(String cadena) {
  Pattern p = Pattern.compile("\\W+");
  Matcher m = p.matcher(cadena.trim());
  if (m.find()) {
   cadena = m.replaceAll("_");
   return cadena;
  }
  return cadena;
 }

 public static boolean check(String cadena) {
  Pattern p = Pattern.compile("\\W+");
  Matcher m = p.matcher(cadena.trim());
  if (m.find()) {
   cadena = m.replaceAll("_");
   return false;
  }
  return true;
 }
}

Archivo: ArbolAVL.java

package edd;

import java.util.ArrayList;

/**
 * @author julian
 * 
 */
class NodoAVL implements java.io.Serializable {
 /**
  * 
  */
 private static final long serialVersionUID = -5229739760615431800L;
 Object dato;
 ArbolAVL izq;
 ArbolAVL der;
 int altura;

 NodoAVL(Object dato) {
  this.dato = dato;
 }
}

public class ArbolAVL implements java.io.Serializable {
 /**
  * 
  */
 private static final long serialVersionUID = 5154638182557428732L;
 private NodoAVL raiz;
 private final int izq, der;

 public ArbolAVL() {
  // TODO Auto-generated constructor stub
  this.raiz = null;
  izq = -1;
  der = 1;
 }

 private int compare(Object newObj, Object obj) {
  if (obj == null)
   return -1;

  if (obj instanceof Integer && newObj instanceof Integer) {
   int a = Integer.parseInt(newObj.toString());
   int b = Integer.parseInt(obj.toString());
   return a - b;
  } else
   return StringHandler.clearString(newObj.toString()).compareTo(
     StringHandler.clearString(obj.toString()));
 }

 private String getInfo() {
  if (this.raiz.dato == null)
   return "<nulltype>";
  else
   return this.raiz.dato.toString();
 }

 /**
  * Este método setea un árbol left como sub-árbol izquierdo y right como
  * sub-árbol derecho.
  * 
  */
 private void set(Object data, ArbolAVL left, ArbolAVL right) {
  this.raiz = new NodoAVL(data);
  raiz.izq = left;
  raiz.der = right;
 }

 public void limpiar() {
  this.raiz = null;
 }

 public boolean isEmpty() {
  return this.raiz == null;
 }

 /**
  * @return Sub-árbol izquierdo;
  */
 public ArbolAVL getIzq() {
  return this.raiz.izq;
 }

 /**
  * @return Sub-árbol der.
  */
 public ArbolAVL getDer() {
  return this.raiz.der;
 }

 public Object getDatoRaiz() {
  return this.raiz.dato;
 }

 public int getAltura() {
  if (this.isEmpty())
   return -1;
  else
   return raiz.altura;
 }

 /**
  * Este método actualiza la altura del árbol
  */
 public void actualizarAltura() {
  if (!this.isEmpty())
   raiz.altura = (raiz.izq.getAltura() > raiz.der.getAltura() ? raiz.izq
     .getAltura() : raiz.der.getAltura()) + 1;
 }

 private void rotacionSimple(int direccion) {
  ArbolAVL t1 = new ArbolAVL();

  if (direccion == izq && !this.raiz.izq.isEmpty()) {
   t1.raiz = this.raiz.izq.raiz;
   this.raiz.izq.raiz = t1.raiz.der.raiz;
   t1.raiz.der.raiz = this.raiz;
  } else if (!this.raiz.der.isEmpty()) {
   t1.raiz = this.raiz.der.raiz;
   this.raiz.der.raiz = t1.raiz.izq.raiz;
   t1.raiz.izq.raiz = this.raiz;
  }

  this.actualizarAltura();
  t1.actualizarAltura();

  this.raiz = t1.raiz;
 }

 private void rotacionDoble(int hijoARotar) {
  if (hijoARotar == izq) {
   this.raiz.izq.rotacionSimple(der);
   this.rotacionSimple(izq);
  } else {
   this.raiz.der.rotacionSimple(izq);
   this.rotacionSimple(der);
  }
 }

 /**
  * Este método hace cálculos del factor de equilibrio en el árbol.
  */
 private void balancear() {
  if (!this.isEmpty()) {
   if (this.raiz.izq.getAltura() - this.raiz.der.getAltura() == 2)
    if (this.raiz.izq.raiz.izq.getAltura() >= this.raiz.izq.raiz.der
      .getAltura())
     this.rotacionSimple(izq);
    else
     this.rotacionDoble(izq);
   else if (this.raiz.der.getAltura() - this.raiz.izq.getAltura() == 2)
    if (this.raiz.der.raiz.der.getAltura() >= this.raiz.der.raiz.izq
      .getAltura())
     this.rotacionSimple(der);
    else
     this.rotacionDoble(der);
  }
 }

 /**
  * Este método inserta el objeto data en el nodo raíz (root) del árbol
  * 
  * @param dato
  *            La información a insertar.
  */
 public void insertar(Object dato) {
  if (this.isEmpty())
   this.set(dato, new ArbolAVL(), new ArbolAVL());
  else {
   if (this.compare(dato, this.raiz.dato) == 0)
    return;
   else if (this.compare(dato, this.raiz.dato) < 0)
    this.raiz.izq.insertar(dato);
   else if (this.compare(dato, this.raiz.dato) > 0)
    this.raiz.der.insertar(dato);

   this.balancear();
   this.actualizarAltura();
  }
 }

 /**
  * Este método busca el objeto data en el árbol t especificado
  * 
  * @param dato
  *            La información a buscar
  * @param t
  *            El árbol en el que se desea buscar
  * @return El objeto si lo encuentra, o null si no.
  * 
  */
 public Object buscar(Object dato, ArbolAVL t) {
  if (!this.isEmpty())
   if (this.compare(dato, t.raiz.dato) == 0)
    return this.raiz.dato;
  if (this.compare(dato, t.raiz.dato) < 0)
   if (!t.raiz.izq.isEmpty())
    return t.buscar(dato, t.raiz.izq);
  if (this.compare(dato, t.raiz.dato) > 0)
   if (!t.raiz.der.isEmpty())
    return t.buscar(dato, t.raiz.der);

  return null;
 }

 /**
  * Borra el árbol t específicado.
  * 
  * @param data
  *            El dato a borrar.
  * @param t
  *            El árbol donde se desea borrar el nodo.
  */
 public void borrar(Object data, ArbolAVL t) {
  try {
   if (this.compare(data, t.raiz.dato) < 0)
    t.borrar(data, t.raiz.izq);
   else if (this.compare(data, t.raiz.dato) > 0)
    t.borrar(data, t.raiz.der);
   else if (t.raiz.izq.isEmpty() && t.raiz.der.isEmpty())
    t.raiz = new ArbolAVL().raiz;
   else if (t.raiz.izq.isEmpty())
    t.raiz = t.raiz.der.raiz;
   else if (t.raiz.der.isEmpty())
    t.raiz = t.raiz.izq.raiz;
   else
    t.raiz.dato = borrarConPredecesor(t.raiz.der);
   // El caso más pizado hehehe
   t.balancear();
   t.actualizarAltura();
  } catch (NullPointerException e) {
   System.out
     .println("No se borró el nodo porque no existe en el árbol");
  }
 }

 private Object borrarConPredecesor(ArbolAVL t) {
  if (t.isEmpty())
   System.out.println("No se va a borrar nada");
  else if (!t.raiz.izq.isEmpty()) {
   Object data = borrarConPredecesor(t.raiz.izq);
   t.balancear();
   t.actualizarAltura();
   return data;
  } else {
   Object data = t.raiz.dato;
   t.raiz = t.raiz.der.raiz;
   t.balancear();
   t.actualizarAltura();
   return data;
  }

  return null;
 }

 /**
  * Este método imprime los datos en recorrido Pre-Orden
  * 
  * @param t
  *            El arbol a recorrer
  */
 public synchronized void printPreOrden(ArbolAVL t) {
  if (!t.isEmpty()) {
   if (!t.raiz.izq.isEmpty())
    System.out.print(String.format("\n%s -> %s;", t.raiz.dato,
      t.raiz.izq.raiz.dato));
   if (!t.raiz.der.isEmpty())
    System.out.print(String.format("\n%s -> %s;", t.raiz.dato,
      t.raiz.der.raiz.dato));
  }

  if (!t.raiz.izq.isEmpty())
   t.printPreOrden(t.raiz.izq);
  if (!t.raiz.der.isEmpty())
   t.printPreOrden(t.raiz.der);
 }

 String str = "";

 @Override
 public String toString() {
  str = "\n";
  this.getGraphvizString(this);
  if (str.length() == 0)
   return this.getInfo();
  return str;
 }

 /**
  * Este método concatena los datos debe ser usado para sobreecargar
  * toString();
  * 
  * @param t
  *            El arbol a recorrer
  */
 private synchronized void getGraphvizString(ArbolAVL t) {
  if (!t.isEmpty()) {
   if (!t.raiz.izq.isEmpty())
    str += (String.format("%s -> %s;\n", "\"" + t.getInfo() + "\"",
      "\"" + t.raiz.izq.getInfo() + "\" "));

   if (!t.raiz.der.isEmpty())
    str += (String.format("%s -> %s;\n", "\"" + t.getInfo() + "\"",
      "\"" + t.raiz.der.getInfo() + "\" "));

   getGraphvizString(t.raiz.izq);
   getGraphvizString(t.raiz.der);
  }
 }

 /**
  * Agregue todos los nodos a un ArrayList.
  * 
  * @param t
  *            El arbol principal.
  * @param al
  *            Un ArrayList donde hacer las inserciones.
  */
 public void getAlltoList(ArbolAVL t, ArrayList<Object>

al) {
  if (!t.isEmpty()) {
   if (t.raiz.dato != null)
    al.add(t.raiz.dato);

   getAlltoList(t.raiz.izq, al);
   getAlltoList(t.raiz.der, al);
  }
 }
}

Ejemplo de Uso | How to Use

import edd.StringHandler;

public class MyClass {
    private String id; // Es un atributo único **THIS IS A UNIQUE ATTRIBUTE**
        
    public MyClass(String id) {
        this.id = id;
    }

    @Override
    public String toString(){
        return StringHandler.clearString(id);
    }

    public static void main(String[] args) {
        ArbolAVL t = new ArbolAVL();
        t.insertar(new MyClass("Barça"));
        t.insertar(new MyClass("Barça")); //No se agrega ** THIS IS NOT LINKED **
    }
}