Hola a toda la comunidad taringuera, hace tiempo que no posteo nada y espero que este post le sea útil a alguien. En esta ocasión les voy a presentar una estructura de datos que me costó mucho aprenderlo y asimilarlo: los arboles binarios, sobre todo me costó por la implementación pero una vez que le agarré la onda, hasta puedo implementarlo con poca o sin ayuda de libros. Comenzaré con la definición de un árbol binario para luego pasar a la carnesita del asunto: los arboles binarios de búsqueda que es por lo que vinieron. Creo, personalmente que más que los códigos lo que quiero que aprendan son los algoritmos involucrados pues seguramente sus implementaciones (que lo han hecho uds solos) son diferentes a la mía y si entienden los algoritmos podrán adaptarlos fácilmente a sus programas ¿Preparados?
Árboles binarios
Definición
Nota: Esta definición es sacada del libro Algorithms de Cormen.
Un árbol binario es una estructura de datos que o:
- no contiene nodos, o
- está compuesto de tres conjuntos disjuntos de nodos: una raíz, un árbol binario llamado subárbol izquierdo y un árbol binario llamado subárbol derecho.
Si el árbol no contiene nodos, lo llamaremos árbol vacío. Si un árbol binario es no vacío y sus subárboles izquierdo y derecho son vacíos, diremos que el árbol es una hoja.
Para dibujar un árbol binario seguiremos las siguientes reglas:
- Representaremos en general a un árbol binario mostrando solamente su raíz como en la siguiente figura
- Dibujaremos una hoja indicando solamente la raíz
- Cuando el subárbol izquierdo (o derecho) de un árbol binario no sea vacío, dibujaremos una línea que va desde la raíz del árbol binario hasta la raíz de su subárbol izquierdo (o derecho). Así, construiremos y dibujaremos un árbol binario de la siguiente forma recursiva (de la forma que estamos acostumbrados):
así, podemos dejarlo así como está o podemos llegar a todas las hojas si queremos.
Implementación de la definición en Java
Supondremos que el dato almacenado en la raíz de los árboles binarios son enteros. A continuación la clase ABB que moldea a un árbol binario tal como lo hemos definido (más adelante veremos por qué le pongo como nombre ABB)
public class ABB {
Integer raiz;
ABB subABizq;
ABB subABder;
// Constructor de un arbol vacio
public ABB() {
raiz = null;
subABizq = null;
subABder = null;
}
// constructor de una hoja
public ABB( Integer raiz ) {
this.raiz = new Integer( raiz );
subABizq = null;
subABder = null;
}
}
Árboles binarios de búsqueda (ABB)
Definición
Un ABB es un árbol binario en la que se cumplen las siguientes condiciónes:
- La raíz del subárbol izquierdo (si existe) es menor que su raíz.
- La raíz del subárbol derecho (si existe) es mayor que su raíz.
En la siguiente figura se muestra un ejemplo de un ABB:
Operaciones sobre un ABB
Antes de ver las operaciones que podemos realizar sobre un ABB vamos a crear un método "utilitario" para la clase ABB. Este método se llamará esVacio y servirá para saber si un árbol binario es vacío o no. Para saber si un árbol binario es vacío o no sólo tendremos que verificar si la raíz es nula o no, si no es nula entonces el árbol no será vacío. A continuación el código del método esVacio:
// avisa si el arbol es vacío o no
private boolean esVacio() {
boolean vacio = true;
if ( raiz != null )
vacio = false;
return vacio;
}
Insertar
La primera operación que haremos e implementaremos será la inserción. Para empezar no podemos insertar un nuevo nodo en donde nos de la gana. No debemos violar las propiedades de los árboles binarios. El algoritmo de inserción es el siguiente:
- Si el árbol es vacío, entonces el nuevo nodo será la raíz del árbol (obvio) y finalizar.
- Si no,
---- Se compara el valor del nuevo nodo con la raíz del árbol binario.
---- Si es menor entonces el nuevo nodo se inserta en su subárbol izquierdo (aplicar este algoritmo al subárbol izquierdo),
---- Si es mayor entonces el nuevo nodo se inserta en su subárbol derecho (aplicar este algoritmo al subárbol derecho).
---- Si son iguales, ignoramos el valor (así me gusta a mi, no es obligatorio)
La siguiente secuencia de imágenes muestra al algoritmo en acción:
Implementación de la operación de inserción en un ABB
El siguiente método ejecuta la inserción en un ABB.
// insercion de un nuevo nodo en el ABB
public void insertar( Integer nuevo ) {
if( esVacio() ) {
raiz = new Integer( nuevo );
subABizq = new ABB();
subABder = new ABB();
} else {
if( nuevo < raiz ) {
subABizq.insertar(nuevo);
} else if ( nuevo > raiz ) {
subABder.insertar(nuevo);
}
}
}
Buscar
Este método es análogo al método insertar: comparamos el valor a buscar con la raíz del árbol, si es menor buscamos en el subárbol izquierdo, si es mayor buscamos en el subárbol derecho, si no, es decir, si el valor a buscar es igual a la raíz entonces retornamos la referencia al árbol encontrado. Si el árbol es vacío entonces el valor buscado no existe en el árbol y retornamos el valor nulo (null). La siguiente figura muestra un ejemplo de esta operación:
Implementación de la operación de búsqueda en un ABB
El siguiente código muestra la implementación del método buscar:
// devuelve una referencia al árbol con la raiz buscada, si no encuentra retorna null
public ABB buscar( Integer x ) {
ABB buscado = null;
if( !esVacio() ) {
if( x < raiz ) {
buscado = subABizq.buscar(x);
} else if ( x > raiz ) {
buscado = subABder.buscar(x);
} else {
return this;
}
}
return buscado;
}
Eliminar
Este método me gusta (aunque no recuerdo si era el más eficiente, lo dudo). Recuerda que no podemos eliminar por eliminar pues quizás el resultado viole con la definicion de ABB. Antes de ir al algoritmo de eliminación es conveniente crear un par de métodos "utilitarios": los métodos buscarMin y esHoja.
El método buscarMin retorna una referencia (no null) al menor elemento de un ABB. ¿Cuál es el menor elemento de un ABB? Observa los ABBs que utilizamos de ejemplo anteriormente y busca el menor elemento de los árboles ¿te diste cuenta de dónde está el menor elemento? El menor elemento se encuentra en el lado más a la izquierda posible. Así, para encontrar el menor elemento de un ABB deberemos recorrer los subárboles izquierdos hasta que encontremos un árbol vacío. La siguiente figura muestra la manera de hallar el menor elemento en un árbol:
El siguiente código muestra el método buscarMin descrito:
// retorna una referencia al elemento minimo de un arbol
private ABB buscarMin() {
ABB arbolActual = this;
while( !arbolActual.subABizq.esVacio() ) {
arbolActual = arbolActual.subABizq;
}
return arbolActual;
}
El método esHoja nos indica si un árbol es una hoja o no. Su implementación es muy simple, pues por definición un árbol es una hoja si sus subárboles son vacíos.
// indica si el arbol es una hoja o no
private boolean esHoja() {
boolean hoja = false;
if( subABizq.esVacio() && subABder.esVacio() ) {
hoja = true;
}
return hoja;
}
Ahora sí, el método eliminar sigue el siguiente algoritmo:
- Buscar el elemento a eliminar
- Si el elemento a eliminar existe, seguir
---- Si el elemento a eliminar es una hoja, entonces se puede eliminar sin escrúpulos (obvio).
---- Si no es una hoja,
-------- Buscar el menor elemento del subárbol derecho del nodo a eliminar, digamos 'min'.
-------- Reemplazar el valor del nodo a eliminar con el valor de 'min'.
-------- Eliminar el nodo 'min' del ABB recursivamente (aplicar este algoritmo al subárbol derecho).
No estoy seguro de que hayas entendido el algoritmo con palabras, por eso la siguiente figura pretende aclarar ideas
¿entendiste?
Implementación de la operación de eliminación en un ABB
// elimina un nodo del ABB
public void eliminar( Integer a ) {
ABB aEliminar = buscar(a);
if (aEliminar != null) {
if( aEliminar.esHoja() ) {
aEliminar.raiz = null;
} else {
ABB min = aEliminar.subABder.buscarMin();
aEliminar.raiz = min.raiz;
min.eliminar(min.raiz);
}
}
}
Recorrido preorden
Ya pasamos lo más complicado ahora vienen los métodos para mostrar un árbol binario en pantalla. Existen cuatro formas de recorridos en un árbol binario, tres de estos recorridos lo implementaremos sin problemas, para el cuarto recorrido (por nivel) será necesario el uso de colas, y no estoy asumiendo que sepas colas. En caso de que sepas colas, entonces puedes estudiar los 4 recorridos sino estudia los 3 primeros, estudias colas y finalmente vuelves y estudias la cuarta forma (estudiar es una manera de decir pues no es necesario saber la implementación detallada de una cola para saber qué es una estructura FIFO - primero en entrar primero en salir).
En el recorrido preorden:
- Primero se muestra la raíz de un árbol
- luego se hace un recorrido preorden en el subárbol izquierdo y
- finalmente se hace un recorrido preorden en el subárbol derecho
Hay una manera fácil de encontrar los recorridos trazando una envoltura al árbol. El recorrido preorden se logra mediante un trazo que envuelve al árbol y mostrando los nodos cada vez que el trazo toca al lado izquierdo del nodo (este método es solamente visual). Por ejemplo en la siguiente figura el recorrido preorden es:
5 - 3 - 1 - 2 - 4 - 7 - 6 - 10 - 8 - 9 - 15
Implementación del recorrido preorden
// recorrido en preorden
public void preOrden() {
if( !esVacio() ) {
System.out.println( raiz );
subABizq.preOrden();
subABder.preOrden();
}
}
Recorrido enorden
En el recorrido enorden:
- Primero se hace un recorrido enorden en el subárbol izquierdo,
- luego se muestra la raíz del árbol y
- finalmente se hace un recorrido enorden en el subárbol derecho
El recorrido enorden se logra mediante un trazo que envuelve al árbol y mostrando los nodos cada vez que el trazo toca al lado bajo del nodo (este método es solamente visual). Por ejemplo en la siguiente figura el recorrido enorden es:
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 15
Implementación del recorrido enorden
// recorrido enorden
public void enOrden() {
if( !esVacio() ) {
subABizq.enOrden();
System.out.println( raiz );
subABder.enOrden();
}
}
Recorrido postorden
En el recorrido postorden:
- Primero se hace un recorrido postorden en el subárbol izquierdo,
- luego se hace un recorrido postorden en el subárbol derecho y
- finalmente se muestra la raíz del árbol.
El recorrido postorden se logra mediante un trazo que envuelve al árbol y mostrando los nodos cada vez que el trazo toca al lado derecho del nodo (este método es solamente visual). Por ejemplo en la siguiente figura el recorrido postorden es:
2 - 1 - 4 - 3 - 6 - 8 - 9 - 15 - 10 - 7 - 5
Implementación del recorrido postorden
// recorrido postorden
public void postOrden() {
if( !esVacio() ) {
subABizq.postOrden();
subABder.postOrden();
System.out.println( raiz );
}
}
Recorrido por nivel
Y para finlizar (el post). En este tipo de recorrido vamos a presentar primer los nodos que estén en el nivel 0 (la raíz), luego los que están en el lugar 1 (los hijos de la raiz), luego los hijos de estos, y así sucesivamente. Por ejemplo, en la siguiente figura la salida es:
5 - 3 - 7 - 1 - 4 - 6 - 10 - 2 - 8 - 15 - 9
El algoritmo para mostrar por nivel es el siguiente (nota que, sorprendentemente, no es recursivo):
- Comenzamos encolando el árbol.
- Repetir mientras la cola esté vacía.
---- Desencolar un árbol de la cola y mostrar su raíz.
---- Si el subárbol izquierdo es no vacío entonces encolar el subárbol izquierdo en la cola.
---- Si el subárbol derecho es no vacío entonces encolar el subárbol derecho en la cola.
Para ilustrar el algoritmo, la siguiente serie de figuras muestran el algoritmo en acción:
Implementación del recorrido por nivel
// recorrido por nivel
public void porNivel() {
Vector<ABB> cola = new Vector<ABB>();
ABB arbol;
cola.add(this);
while( !cola.isEmpty() ) {
arbol = cola.elementAt(0);
cola.remove(0);
System.out.println( arbol.raiz );
if ( !arbol.subABizq.esVacio() ) cola.add( arbol.subABizq );
if (!arbol.subABder.esVacio() ) cola.add( arbol.subABder );
}
}
A probar nuestro código
Para probar nuestro código, tenemos dos archivos: ABB.java y Main.java
El archivo ABB.java contiene lo siguiente:
import java.util.Vector;
public class ABB {
Integer raiz;
ABB subABizq;
ABB subABder;
// Constructor de un arbol vacio
public ABB() {
raiz = null;
subABizq = null;
subABder = null;
}
// constructor de una hoja
public ABB( Integer raiz ) {
this.raiz = new Integer( raiz );
subABizq = null;
subABder = null;
}
private boolean esVacio() {
boolean vacio = true;
if ( raiz != null )
vacio = false;
return vacio;
}
public void insertar( Integer nuevo ) {
if( esVacio() ) {
raiz = new Integer( nuevo );
subABizq = new ABB();
subABder = new ABB();
} else {
if( nuevo < raiz ) {
subABizq.insertar(nuevo);
} else if ( nuevo > raiz ) {
subABder.insertar(nuevo);
}
}
}
public ABB buscar( Integer x ) {
ABB buscado = null;
if( !esVacio() ) {
if( x < raiz ) {
buscado = subABizq.buscar(x);
} else if ( x > raiz ) {
buscado = subABder.buscar(x);
} else {
return this;
}
}
return buscado;
}
private ABB buscarMin() {
ABB arbolActual = this;
while( !arbolActual.subABizq.esVacio() ) {
arbolActual = arbolActual.subABizq;
}
return arbolActual;
}
private boolean esHoja() {
boolean hoja = false;
if( subABizq.esVacio() && subABder.esVacio() ) {
hoja = true;
}
return hoja;
}
public void eliminar( Integer a ) {
ABB aEliminar = buscar(a);
if (aEliminar != null) {
if( aEliminar.esHoja() ) {
aEliminar.raiz = null;
} else {
ABB min = aEliminar.subABder.buscarMin();
aEliminar.raiz = min.raiz;
min.eliminar(min.raiz);
}
}
}
public void preOrden() {
if( !esVacio() ) {
System.out.println( raiz );
subABizq.preOrden();
subABder.preOrden();
}
}
public void enOrden() {
if( !esVacio() ) {
subABizq.enOrden();
System.out.println( raiz );
subABder.enOrden();
}
}
public void postOrden() {
if( !esVacio() ) {
subABizq.postOrden();
subABder.postOrden();
System.out.println( raiz );
}
}
public void porNivel() {
Vector<ABB> cola = new Vector<ABB>();
ABB arbol;
cola.add(this);
while( !cola.isEmpty() ) {
arbol = cola.elementAt(0);
cola.remove(0);
System.out.println( arbol.raiz );
if ( !arbol.subABizq.esVacio() ) cola.add( arbol.subABizq );
if (!arbol.subABder.esVacio() ) cola.add( arbol.subABder );
}
}
}
Y el archivo Main.java contiene lo siguiente
public class Main {
public static void main(String[] args) {
ABB arbol = new ABB();
arbol.insertar(5);
arbol.insertar(3);
arbol.insertar(7);
arbol.insertar(1);
arbol.insertar(4);
arbol.insertar(6);
arbol.insertar(10);
arbol.insertar(2);
arbol.insertar(8);
arbol.insertar(15);
arbol.insertar(9);
System.out.println("Mostrando por niveles:");
arbol.porNivel();
arbol.eliminar(11);
System.out.println("Mostrando en preorden:");
arbol.preOrden();
arbol.eliminar(6);
System.out.println("Mostrando en postorden (eliminado 6):");
arbol.postOrden();
}
}
Y así será la salida de ejecutar Main (no es lo mas bonito pero uds. lo maquillan):
Mostrando por niveles:
5
3
7
1
4
6
10
2
8
15
9
Mostrando en preorden:
5
3
1
2
4
7
6
10
8
9
15
Mostrando en postorden (eliminado 6):
2
1
4
3
9
8
15
10
7
5
FIN
Espero le haya servido a alguien.
PD: Quisiera crearme un blog donde coloque este tipo de cosas (tutoriales, videos, códigos) ¿Alguien sabe como hacerlo? pero no en blogspot o wordpress, sino hacer uno propio en joomla o drupal por ejemplo pues veo muchos blogs que quedan muy buenos con esos CMS y no sé como se manejan esos bichos.