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 **
}
}
No hay comentarios:
Publicar un comentario