Categories Estructuras de Datos, Java

Árboles Binarios de Búsqueda en Java

by k3rnelLeave a Comment on Árboles Binarios de Búsqueda en Java
COMPARTIR EN REDES SOCIALES

En esta entrada vamos a explicar los árboles binarios de búsqueda en Java. Los árboles binarios de búsqueda son una estructura de datos que permite realizar búsquedas, insertar elementos y borrar elementos con un tiempo medio logarítmico.

Primero explicaremos qué es un árbol binario, después veremos sus principales operaciones y cómo funcionan. Finalmente realizaremos una implementación para enteros y una implementación genérica que permitirá almacenar cualquier tipo de objeto en los nodos.

¿ Qué aspecto tiene un árbol binario de búsqueda ?

En la siguiente imagen podemos ver el aspecto que tiene un árbol binario de búsqueda:

Representación de un Árbol Binario de Búsqueda en Java
Representación de un Árbol Binario de Búsqueda

Se basa en nodos. Cada nodo puede tener como máximo 2 hijos. El hijo de la izquierda siempre tendrá un valor menor que su padre y el hijo de la derecha siempre tendrá un valor mayor que su padre. Un nodo no tiene porque tener 2 hijos obligatoriamente, puede tener:

  • Solo un nodo hijo menor que él, por lo tanto este se posicionará a la izquierda.
  • Solo un nodo hijo mayor que él, por lo tanto este se posicionará a la derecha.
  • Ningún nodo hijo. A estos nodos les llamamos «nodos hoja».

Veamos un ejemplo de cada caso de uso.

Solo un nodo hijo posicionado a la izquierda

Nodo con solo un nodo hijo posicionado a su izquierda
Nodo con solo un nodo hijo posicionado a su izquierda

Como podéis apreciar en la imagen, el nodo con valor «14» solo tiene un nodo hijo «13» posicionado a su izquierda porque es menor.

Solo un nodo hijo posicionado a la derecha

Nodo con solo un nodo hijo posicionado a su derecha
Nodo con solo un nodo hijo posicionado a su derecha

El nodo con valor «10» solo tiene un hijo «14», posicionado a su derecha porque «14» es mayor que «10».

Nodos hoja

Nodos hoja en un árbol binario de búsqueda en Java.
Nodos hoja en un árbol binario de búsqueda.

En esta imagen tanto «1» como «4», «7» y «13» son nodos hoja porque ninguno de ellos tiene hijos.

El nodo inicial o «Nodo Ráiz»

Nodo raíz en un árbol binario de búsqueda de Java
Nodo raíz en un árbol binario de búsqueda

Llamamos nodo raíz al nodo inicial de nuestro árbol. En este caso el nodo con valor «8».

Las operaciones sobre un Árbol Binario de búsqueda en Java

Las principales operaciones sobre un árbol binario de búsqueda son:

  • Inserción de nuevos nodos.
  • Búsqueda de nodos.
  • Eliminación de nodos

La operación de inserción de nuevos nodos en el Árbol Binario de Búsqueda en Java

Para insertar un nuevo nodo en un árbol binario es necesario buscar la posición en la cuál debería de posicionarse, para ello se sigue el siguiente algoritmo:

  1. Se mira cada nodo, si el valor del nodo que queremos insertar es mayor que el valor del nodo que estamos inspeccionando vamos hacía la derecha. Por el contrario, si el valor del nodo que queremos insertar es menor que valor del nodo que estamos inspeccionando vamos hacia la izquierda.
  2. Llegará un momento en el que encontraremos la posición donde debería de estar el nodo porque llegaremos a la conclusión de que nos hemos quedado sin árbol que recorrer, y por lo tanto, insertaremos nuestro nuevo nodo a la izquierda o derecha del último nodo, dependiendo de si es mayor o menor a este.

Veamos un ejemplo teórico partiendo del siguiente árbol:

Representación del Árbol Binario de Búsqueda en Java que utilizaremos para los conceptos para explicar las operaciones sobre el árbol.

Supongamos que queremos insertar el valor «9»:

  1. Comparamos «9» con «8», como «9» es mayor que «8» nos movemos a la derecha.
  2. Comparamos «9» con «10», como «9» es menor que «10», y «10» no tiene nodo izquierdo lo insertamos en esta posición.

Supongamos que queremos insertar el valor «5»:

  1. Comparamos «5» con «8» como «5» es menor que «8» nos movemos hacia la izquierda.
  2. Comparamos «5» con «3» como «5» es mayor que «3» nos movemos hacia la derecha.
  3. Comparamos «5» con «6» como «5» es menor que «6» nos movemos hacia la izquierda.
  4. Comparamos «5» con «4» como «5» es mayor que «4» nos movemos hacia la derecha.
  5. Como hemos llegado a un nodo hoja insertamos el nodo a la derecha del «4», dado que «5» es mayor que 4.

Supongamos que queremos insertar el valor «42»:

  1. Comparamos «42» con «8» como «42» es mayor que «8» nos movemos hacia la derecha.
  2. Comparamos «42» con «10» como «42» es mayor que «10» nos movemos hacia la derecha.
  3. Comparamos «42» con «14» como «42» es mayor que «14» nos movemos hacia la derecha.
  4. Como hemos llegado a un nodo cuyo hijo derecho está vacío esta debe de ser la posición en la que insertaremos el «42».

La operación de eliminación de nodos en el Árbol Binario de Búsqueda en Java

La operación de eliminación de un determinado nodo es realmente compleja porque puede exigir reposicionar nodos, y tiene los siguientes casos de uso:

Eliminar la raíz

Tenemos el siguiente árbol:

Representación de un Árbol Binario de Búsqueda en Java antes de eliminar la raíz

Queremos eliminar la raíz «15», tenemos que seguir el siguiente algoritmo:

  1. Como tenemos derecha, hacemos la raíz el nodo con valor «17»
  2. Reposicionamos el hijo izquierdo de la antigua raíz, es decir, reposicionamos el árbol izquierdo de la antigua raíz. Si no tuviésemos un hijo izquierdo no reposicionaríamos nada.

Nos quedaría de la siguiente forma:

Representación de un Árbol Binario de Búsqueda en Java después de eliminar la raíz

¿ Qué pasa si no tenemos nodos a la derecha de la raíz ?

Simplemente ponemos como raíz el nodo izquierdo.

Eliminar un nodo al que hemos llegado por la derecha y no es nodo hoja

Tenemos el siguiente árbol:

Representación de un Árbol Binario de Búsqueda en Java antes de eliminar un nodo al que hemos llegado por la derecha

Queremos eliminar el nodo con valor «17», si os fijáis llegamos a él por la derecha, tenemos que seguir el siguiente algoritmo:

  1. Si el nodo que queremos eliminar tiene nodo derecho
    1. Apuntamos a su padre al nodo derecho del nodo que queremos eliminar
    2. Comprobamos si el nodo que queremos eliminar tiene hijo izquierdo y lo reposicionamos en el árbol. Si no tiene hijo izquierdo no hacemos nada
  2. Si el nodo que queremos eliminar no tiene nodo derecho
    1. Solo tenemos que reposicionar el hijo izquierdo del nodo a eliminar.

Quedaría de la siguiente manera:

Representación de un Árbol Binario de Búsqueda en Java después de eliminar un nodo al que hemos llegado por la derecha

Eliminar un nodo al que hemos llegado por la izquierda y no es nodo hoja

Tenemos el siguiente árbol:

Representación de un Árbol Binario de Búsqueda en Java antes de eliminar un nodo al que hemos llegado por la izquierda

Queremos eliminar el nodo con valor «13», si os fijáis llegamos a él por la izquierda, tenemos que seguir el siguiente algoritmo:

  1. Si el nodo que queremos eliminar tiene nodo izquierdo
    1. Apuntamos a su padre al nodo izquierdo del nodo que queremos eliminar
    2. Comprobamos si el nodo que queremos eliminar tiene hijo derecho y lo reposicionamos en el árbol. Si no tiene hijo derecho no hacemos nada
  2. Si el nodo que queremos eliminar no tiene nodo izquierdo
    1. Solo tenemos que reposicionar el hijo derecho del nodo a eliminar.

Quedaría de la siguiente manera:

Representación de un Árbol Binario de Búsqueda en Java después de eliminar un nodo al que hemos llegado por la izquierda

Eliminar un nodo hoja

Este es el caso más sencillo de todos, ya que solo tenemos que eliminar el nodo.

Veamos un ejemplo, tenemos el siguiente árbol:

Representación de un Árbol Binario de Búsqueda en Java antes de eliminar un nodo hoja

Queremos eliminar el valor «5», lo eliminamos y el árbol quedaría de la siguiente manera:

Representación de un Árbol Binario de Búsqueda en Java después de eliminar un nodo hoja

La operación de búsqueda en el Árbol Binario de Búsqueda en Java

La operación de búsqueda se realiza de forma binaria, de la siguiente forma:

  1. Se compara el valor a buscar con cada nodo empezando por la raíz. Si el valor buscado es mayor al nodo que estamos recorriendo vamos hacia la derecha, si es menor hacia la izquierda.
  2. Llegará un momento en el que encontraremos el elemento o no lo encontraremos porque:
    1. Llegaremos a un nodo hoja sin haberlo encontrado.
    2. Deberíamos de ir a la derecha y no tenemos nodo a la derecha o deberíamos ir a la izquierda y no tenemos nodo izquierdo.

Vamos a verlo con un ejemplo teórico con el siguiente árbol:

Representación de un Árbol Binario de Búsqueda en Java para explicar la operación de búsqueda de elementos

Vamos a buscar el número «6»:

  1. Comparamos «6» con «8», como «8» es mayor que «6» nos movemos a la izquierda.
  2. Comparamos «6» con «3», como «3» es menor que «6» nos movemos a la derecha.
  3. Encontramos nuestro elemento.

Vamos a buscar el numero «33»:

  1. Comparamos «33» con «8», como «33» es mayor que «8» nos movemos a la derecha.
  2. Comparamos «33» con «10», como «33» es mayor que «10» nos movemos a la derecha.
  3. Comparamos «33» con «14», como «33» es mayor que «14» nos movemos a la derecha.
  4. Dado que no hay derecha, el número no se encuentra en el árbol.

Vamos a buscar el número «5»:

  1. Comparamos «5» con «8», como «5» es menor que «8» nos movemos a la izquierda.
  2. Comparamos «5» con «3», como «5» es mayor que «3» nos movemos a la derecha.
  3. Comparamos «5» con «6», como «5» es menor que «6» nos movemos a la izquierda.
  4. Comparamos «5» con «4», como «5» es mayor que «4» y «4» es un nodo hoja, el elemento no se encuentra.

Vamos a buscar el número «42»:

  1. Comparamos «42» con «8», como «42» es mayor que «8» nos movemos a la derecha.
  2. Comparamos «42» con «10», como «42» es mayor que «10» nos movemos a la derecha.
  3. Comparamos «42» con «14», como «42» es mayor que «14» pero «14» no tiene nodo derecho, el elemento no se encuentra.

Vayamos con la implementación.

Implementación del Árbol Binario de Búsqueda en Java

En esta sección implementaremos un árbol binario de búsqueda para enteros y otro genérico con las siguientes operaciones:

  1. La operación «insertarElemento», que nos permitirá añadir nuevos nodos a nuestro árbol.
  2. La operación «insertarNodo», que utilizaremos para reposicionar nodos.
  3. La operación «buscarElemento», que utilizaremos para buscar elementos.
  4. La operación «eliminarElemento», que se utilizará para borrar elementos.
  5. La operación «size», que nos devolverá el número de elementos que tiene nuestro árbol.
  6. La operación «getNumeroIteracionUltimaBusqueda», que nos devolverá cuantos pasos hemos realizado para encontrar o no encontrar la última búsqueda. Esto nos permitirá comprobar que el orden de complejidad de las búsquedas es logarítmico.
  7. La operación «getNumeroIteracionesMedioEnBusquedas», que nos devolverá el número medio de pasos en nuestras búsquedas.
  8. La operación «obtenerElementosOrdenadosAscendentemente», que nos permitirá obtener un «ArrayList» con todos los elementos ordenados de forma ascendente.
  9. La operación «obtenerElementosOrdenadosDescendentemente», que nos permitirá obtener un «ArrayList» con todos los elementos ordenados de forma descendente.
  10. La operación «recorrerAscendente», que será una operación auxiliar para la operación «obtenerElementosOrdenadosAscendentemente».
  11. La operación «recorrerDescendente», que será una operación auxiliar para la operación «obtenerElementosOrdenadosDescendentemente».

Veamos primero el código entero y después vayamos operación por operación:

Nuestra clase Nodo

public class Nodo<V> {

	private V value;
	private Nodo<V> izq;
	private Nodo<V> der;
	
	public Nodo(V value, Nodo<V> izq, Nodo<V> der) {
		super();
		this.value = value;
		this.izq = izq;
		this.der = der;
	}

	public V getValue() {
		return value;
	}

	public void setValue(V value) {
		this.value = value;
	}

	public Nodo<V> getIzq() {
		return izq;
	}

	public void setIzq(Nodo<V> izq) {
		this.izq = izq;
	}

	public Nodo<V> getDer() {
		return der;
	}

	public void setDer(Nodo<V> der) {
		this.der = der;
	}
}

Nuestra clase nodo tiene 3 parámetros:

  1. «value», que contendrá el valor de nuestro elemento.
  2. «izq», que será un puntero hacía el nodo hijo izquierdo.
  3. «der», que será un puntero hacía el nodo hijo derecho.

Así mismo tendremos «getters» y «setters» para cada uno de los atributos.

Hemos utilizado genéricos para construir la clase, luego nos servirá para nuestro árbol genérico, pero ahora estamos con el árbol de enteros.

Nuestra clase ArbolBinarioBusqueda

import java.util.ArrayList;

public class ArbolBinarioBusqueda {

	Nodo<Integer> raiz = null;
	private int numeroElementos = 0;
	private int numeroBusquedas = 0;
	private int numeroIteracionesTotal = 0;
	private int numeroIteracionesUltimaBusqueda = 0;

	public ArbolBinarioBusqueda() {

	}

	public void insertarElemento(Integer value) {
		Nodo<Integer> nuevoNodo = new Nodo<Integer>(value, null, null);

		if (raiz == null) {
			raiz = nuevoNodo;
			System.out.println("Inserto la raiz");
		} else {
			// Necesitamos encontrar en que posición debemos insertar el nodo
			Nodo<Integer> aux = raiz;

			while (aux != null) {
				// Comprobamos si tenemos que insertarlo ya
				// Comprobamos si nodo hoja
				if (aux.getDer() == null && aux.getIzq() == null) {
					if (value > aux.getValue()) {
						// Derecha
						System.out.println(value + " Lo insertamos a la derecha de: " + aux.getValue());
						aux.setDer(nuevoNodo);
						aux = null;
					} else {
						// Izquierda
						System.out.println(value + " Lo insertamos a la izquierda de: " + aux.getValue());
						aux.setIzq(nuevoNodo);
						aux = null;
					}
				} else if (value > aux.getValue() && aux.getDer() == null) {
					// Lo insertamos a la derecha
					System.out.println(value + " Lo insertamos a la derecha de: " + aux.getValue());
					aux.setDer(nuevoNodo);
					aux = null;
				} else if (value < aux.getValue() && aux.getIzq() == null) {
					// Lo insertamos a la izquierda
					System.out.println(value + " Lo insertamos a la izquierda de: " + aux.getValue());
					aux.setIzq(nuevoNodo);
					aux = null;
				} else {
					// Pasamos de nodo
					if (value > aux.getValue()) {
						aux = aux.getDer();
					} else {
						aux = aux.getIzq();
					}
				}

			}

		}

		// Incrementamos el número de elementos en 1
		numeroElementos++;

	}

	private void insertarNodo(Nodo<Integer> nodo) {
		if (raiz == null) {
			raiz = nodo;
			System.out.println("Inserto la raiz");
		} else {
			// Necesitamos encontrar en que posición debemos insertar el nodo
			Nodo<Integer> aux = raiz;

			while (aux != null) {
				// Comprobamos si tenemos que insertarlo ya
				// Comprobamos si nodo hoja
				if (aux.getDer() == null && aux.getIzq() == null) {
					if (nodo.getValue() > aux.getValue()) {
						// Derecha
						System.out.println(nodo.getValue() + " Lo insertamos a la derecha de: " + aux.getValue());
						aux.setDer(nodo);
						aux = null;
					} else {
						// Izquierda
						System.out.println(nodo.getValue() + " Lo insertamos a la izquierda de: " + aux.getValue());
						aux.setIzq(nodo);
						aux = null;
					}
				} else if (nodo.getValue() > aux.getValue() && aux.getDer() == null) {
					// Lo insertamos a la derecha
					System.out.println(nodo.getValue() + " Lo insertamos a la derecha de: " + aux.getValue());
					aux.setDer(nodo);
					aux = null;
				} else if (nodo.getValue() < aux.getValue() && aux.getIzq() == null) {
					// Lo insertamos a la izquierda
					System.out.println(nodo.getValue() + " Lo insertamos a la izquierda de: " + aux.getValue());
					aux.setIzq(nodo);
					aux = null;
				} else {
					// Pasamos de nodo
					if (nodo.getValue() > aux.getValue()) {
						aux = aux.getDer();
					} else {
						aux = aux.getIzq();
					}
				}

			}
		}
	}

	public Integer buscarElemento(Integer value) {
		Nodo<Integer> aux = raiz;
		Nodo<Integer> resultado = null;
		numeroIteracionesUltimaBusqueda = 0;

		while (aux != null) {
			// Comprobamos si es el valor
			if (aux.getValue() == value) {
				// Hemos encontrado el elemento
				resultado = aux;
				aux = null;
			} else if (aux.getDer() == null && aux.getIzq() == null) {
				// Si hemos llegado a un nodo hoja el elemento no está en el ABB
				// El elemento no está
				aux = null;
			} else if (value > aux.getValue() && aux.getDer() != null) {
				// Si el valor es mayor y tenemos nodo a la derecha, vamos a la derecha
				aux = aux.getDer();
			} else if (value < aux.getValue() && aux.getIzq() != null) {
				// Si el valor es menos y tenemos nodo a la izquierda, vamos a la izquierda
				aux = aux.getIzq();
			} else {
				// Si el nodo es mayor y no tenemos nodo a la derecha o es menor y no tenemos
				// nodo a la izquierda
				// El elemento no está
				aux = null;
			}

			numeroIteracionesUltimaBusqueda++;
		}

		numeroIteracionesTotal += numeroIteracionesUltimaBusqueda;
		numeroBusquedas++;

		if (resultado != null) {
			return resultado.getValue();
		}else {
			return null;
		}
	}

	public boolean eliminarElemento(Integer value) {
		boolean resultado = false;
		Nodo<Integer> aux = raiz;

		while (aux != null) {
			// Si es la raiz
			if (aux.getValue() == value) {
				Nodo<Integer> nodoAEliminar = aux;

				if (aux.getDer() != null) {
					raiz = aux.getDer();
					if (nodoAEliminar.getIzq() != null) {
						insertarNodo(nodoAEliminar.getIzq());
						nodoAEliminar.setIzq(null);
						nodoAEliminar.setDer(null);
					}
				}else if (aux.getIzq() != null) {
					raiz = aux.getIzq();
					if (nodoAEliminar.getDer() != null) {
						insertarNodo(nodoAEliminar.getDer());
						nodoAEliminar.setIzq(null);
						nodoAEliminar.setDer(null);
					}
				}else {
					raiz = null;
				}
				
				resultado = true;
				aux = null;
			} else if (aux.getIzq() != null && aux.getIzq().getValue() == value) {
				Nodo<Integer> nodoAEliminar = aux.getIzq();
				// Si el valor está a la izquierda del nodo que estamos recorriendo
				// Miramos si tenemos izquierda en el nodo a eliminar

				if (aux.getIzq().getIzq() != null) {
					// Tenemos Nodo a la izquierda
					// Apuntamos el nodo que estamos recorriendo al siguiente del nodo a eliminar
					aux.setIzq(aux.getIzq().getIzq());
					// Reposicionamos sus hijos
					if (nodoAEliminar.getDer() != null) {
						insertarNodo(nodoAEliminar.getDer());
					}
					nodoAEliminar.setDer(null);
					nodoAEliminar.setIzq(null);
					resultado = true;
					aux = null;
				} else {
					// No tenemos nodo a la izquierda del elemento a eliminar
					// Miramos si es nodo hoja

					if (aux.getIzq() == null && aux.getDer() == null) {
						aux.setIzq(null);
					} else {
						aux.setIzq(null);
						if (nodoAEliminar.getDer() != null) {
							insertarNodo(nodoAEliminar.getDer());
						}
					}
					
					resultado = true;
					aux = null;
				}

			} else if (aux.getDer() != null && aux.getDer().getValue() == value) {
				Nodo<Integer> nodoAEliminar = aux.getDer();
				// Si el valor está a la derecha del nodo que estamos recorriendo
				// Miramos si tenemos derecha en el nodo a eliminar

				if (aux.getDer().getDer() != null) {
					// Tenemos Nodo a la izquierda
					// Apuntamos el nodo que estamos recorriendo al siguiente del nodo a eliminar
					aux.setDer(aux.getDer().getDer());
					// Reposicionamos sus hijos
					if (nodoAEliminar.getIzq() != null) {
						insertarNodo(nodoAEliminar.getIzq());
					}
					nodoAEliminar.setDer(null);
					nodoAEliminar.setIzq(null);
					resultado = true;
					aux = null;
				} else {
					// No tenemos nodo a la izquierda del elemento a eliminar
					// Miramos si es nodo hoja

					if (aux.getIzq().getIzq() == null && aux.getDer().getDer() == null) {
						aux.setDer(null);
					} else {
						aux.setDer(null);
						if (nodoAEliminar.getIzq() != null) {
							insertarNodo(nodoAEliminar.getIzq());
						}

					}
					
					resultado = true;
					aux = null;
				}
			} else {
				if (value > aux.getValue()) {
					aux = aux.getDer();
				} else {
					aux = aux.getIzq();
				}
			}
		}
		
		//En caso de borrar el nodo disminuimos la cantidad de nodos en 1
		if (resultado) {
			numeroElementos--;
		}

		return resultado;

	}

	public int size() {
		return this.numeroElementos;
	}

	public int getNumeroIteracionesMedioEnBusquedas() {
		return (int) Math.ceil(numeroIteracionesTotal / (double) this.numeroBusquedas);
	}

	public int getNumeroIteracionesUltimaBusqueda() {
		return this.numeroIteracionesUltimaBusqueda;
	}

	public ArrayList<Integer> obtenerElementosOrdenadosAscendentemente() {
		ArrayList<Integer> elementosOrdenados = new ArrayList<>();
		recorrerAscendente(raiz, elementosOrdenados);
		return elementosOrdenados;
	}

	public ArrayList<Integer> obtenerElementosOrdenadosDescendentemente() {
		ArrayList<Integer> elementosOrdenados = new ArrayList<>();
		recorrerDescendente(raiz, elementosOrdenados);
		return elementosOrdenados;
	}

	private void recorrerAscendente(Nodo<Integer> nodo, ArrayList<Integer> elementos) {
		if (nodo != null) {
			if (nodo.getIzq() == null && nodo.getDer() == null) {
				elementos.add(nodo.getValue());
			} else {
				recorrerAscendente(nodo.getIzq(), elementos);
				elementos.add(nodo.getValue());
				recorrerAscendente(nodo.getDer(), elementos);
			}
		}

	}

	private void recorrerDescendente(Nodo<Integer> nodo, ArrayList<Integer> elementos) {
		if (nodo != null) {
			if (nodo.getIzq() == null && nodo.getDer() == null) {
				elementos.add(nodo.getValue());
			} else {
				recorrerDescendente(nodo.getDer(), elementos);
				elementos.add(nodo.getValue());
				recorrerDescendente(nodo.getIzq(), elementos);
			}
		}

	}

}

Vamos ahora a explicar cada una de las operaciones y los atributos de clase.

Los atributos de la clase

Tenemos los siguientes atributos de la clase:

  1. «raiz», será un objeto de tipo «Nodo<Integer>», apuntará a la raíz del árbol en todo momento.
  2. «numeroElementos», nos servirá para contabilizar cuantos elementos tenemos en nuestro árbol.
  3. «numeroBusquedas», no servirá para contabilizar el número de búsqueda que hemos realizado sobre el árbol.
  4. «numeroIteracionesTotal», nos servirá para poder calcular el numero de veces medio que recorremos los nodos hasta encontrar nuestro elemento.
  5. «numeroIteracionesUltimaBusqueda», nos servirá para saber el número de pasos realizado en la última búsqueda.

El método «insertarElemento»

public void insertarElemento(Integer value) {
	Nodo<Integer> nuevoNodo = new Nodo<Integer>(value, null, null);

	if (raiz == null) {
		raiz = nuevoNodo;
		System.out.println("Inserto la raiz");
	} else {
		// Necesitamos encontrar en que posición debemos insertar el nodo
		Nodo<Integer> aux = raiz;

		while (aux != null) {
			// Comprobamos si tenemos que insertarlo ya
			// Comprobamos si nodo hoja
			if (aux.getDer() == null && aux.getIzq() == null) {
				if (value > aux.getValue()) {
					// Derecha
					System.out.println(value + " Lo insertamos a la derecha de: " + aux.getValue());
					aux.setDer(nuevoNodo);
					aux = null;
				} else {
					// Izquierda
					System.out.println(value + " Lo insertamos a la izquierda de: " + aux.getValue());
					aux.setIzq(nuevoNodo);
					aux = null;
				}
			} else if (value > aux.getValue() && aux.getDer() == null) {
				// Lo insertamos a la derecha
				System.out.println(value + " Lo insertamos a la derecha de: " + aux.getValue());
				aux.setDer(nuevoNodo);
				aux = null;
			} else if (value < aux.getValue() && aux.getIzq() == null) {
				// Lo insertamos a la izquierda
				System.out.println(value + " Lo insertamos a la izquierda de: " + aux.getValue());
				aux.setIzq(nuevoNodo);
				aux = null;
			} else {
				// Pasamos de nodo
				if (value > aux.getValue()) {
					aux = aux.getDer();
				} else {
					aux = aux.getIzq();
				}
			}

		}

	}

	// Incrementamos el número de elementos en 1
	numeroElementos++;

}

Lo primero que realizamos en nuestro método es crear el nodo con el nuevo valor que vamos a introducir. Después comprobamos si la raíz es nula, es decir si nuestro árbol está vacío, en caso de estarlo asignamos a la raíz nuestro nuevo nodo. En caso de que nuestro árbol ya tenga una raíz tenemos que buscar la posición donde insertarlo.

Esto lo realizamos mediante un puntero auxiliar llamado «aux» y mediante un bucle while, en cada iteración se buscan los diferentes casos de uso que dan lugar a la inserción del elemento.

El primero de ellos es que hayamos llegado a un nodo hoja mientras recorremos nuestro árbol, en este caso habrá que insertar el nuevo nodo a la izquierda o derecha de nuestro nodo hoja en función de si este es mayor o menor que el nodo hoja.

El segundo caso de uso es que nuestro valor sea mayor que el nodo que estamos recorriendo en este momento y dicho nodo no tenga hijo derecho, por lo tanto, lo insertamos a la derecha.

El tercer caso de uso es que nuestro valor sea menor que el nodo que estamos recorriendo y que nuestro nodo no tenga hijo izquierdo, lo insertamos en la izquierda.

En caso de que no se cumpla ningún caso de uso de los mencionados anteriormente simplemente pasamos al nodo siguiente yendo a la derecha si el valor es mayor al nodo que estamos recorriendo o por el contrario yendo a la izquierda si es menor.

Por último, y una vez ya insertado el nodo, incrementamos el número de elementos en 1.

El método buscarElemento

public Integer buscarElemento(Integer value) {
	Nodo<Integer> aux = raiz;
	Nodo<Integer> resultado = null;
	numeroIteracionesUltimaBusqueda = 0;

	while (aux != null) {
		// Comprobamos si es el valor
		if (aux.getValue() == value) {
			// Hemos encontrado el elemento
			resultado = aux;
			aux = null;
		} else if (aux.getDer() == null && aux.getIzq() == null) {
			// Si hemos llegado a un nodo hoja el elemento no está en el ABB
			// El elemento no está
			aux = null;
		} else if (value > aux.getValue() && aux.getDer() != null) {
			// Si el valor es mayor y tenemos nodo a la derecha, vamos a la derecha
			aux = aux.getDer();
		} else if (value < aux.getValue() && aux.getIzq() != null) {
			// Si el valor es menos y tenemos nodo a la izquierda, vamos a la izquierda
			aux = aux.getIzq();
		} else {
			// Si el nodo es mayor y no tenemos nodo a la derecha o es menor y no tenemos
			// nodo a la izquierda
			// El elemento no está
			aux = null;
		}

		numeroIteracionesUltimaBusqueda++;
	}

	numeroIteracionesTotal += numeroIteracionesUltimaBusqueda;
	numeroBusquedas++;

	if (resultado != null) {
		return resultado.getValue();
	}else {
		return null;
	}
}

Lo primero que realizamos en este método es crear un puntero auxiliar «aux» que apuntará a la raíz y que nos servirá para recorrer nuestro árbol sin modificar el puntero «raiz» (atributo de clase).

Después crearemos un Nodo resultado que nos servirá para asignar a este el nodo que corresponde con la búsqueda que estamos realizando.

El algoritmo funciona recorriendo el árbol yendo hacía la izquierda o derecha en función de si el elemento que estamos buscando es mayor o menor que el nodo que estamos recorriendo. Llegará un momento en el que encontraremos el elemento o no lo encontraremos porque hemos llegado a un nodo hoja o el valor que estamos buscando es mayor que el nodo que estamos recorriendo y no tenemos nodo a la derecha o es menor y no tenemos nodo a la izquierda.

Por último contabilizamos las búsquedas y devolvemos el resultado.

El método eliminarElemento

public boolean eliminarElemento(Integer value) {
	boolean resultado = false;
	Nodo<Integer> aux = raiz;

	while (aux != null) {
		// Si es la raiz
		if (aux.getValue() == value) {
			Nodo<Integer> nodoAEliminar = aux;

			if (aux.getDer() != null) {
				raiz = aux.getDer();
				if (nodoAEliminar.getIzq() != null) {
					insertarNodo(nodoAEliminar.getIzq());
					nodoAEliminar.setIzq(null);
					nodoAEliminar.setDer(null);
				}
			}else if (aux.getIzq() != null) {
				raiz = aux.getIzq();
				if (nodoAEliminar.getDer() != null) {
					insertarNodo(nodoAEliminar.getDer());
					nodoAEliminar.setIzq(null);
					nodoAEliminar.setDer(null);
				}
			}else {
				raiz = null;
			}
			
			resultado = true;
			aux = null;
		} else if (aux.getIzq() != null && aux.getIzq().getValue() == value) {
			Nodo<Integer> nodoAEliminar = aux.getIzq();
			// Si el valor está a la izquierda del nodo que estamos recorriendo
			// Miramos si tenemos izquierda en el nodo a eliminar

			if (aux.getIzq().getIzq() != null) {
				// Tenemos Nodo a la izquierda
				// Apuntamos el nodo que estamos recorriendo al siguiente del nodo a eliminar
				aux.setIzq(aux.getIzq().getIzq());
				// Reposicionamos sus hijos
				if (nodoAEliminar.getDer() != null) {
					insertarNodo(nodoAEliminar.getDer());
				}
				nodoAEliminar.setDer(null);
				nodoAEliminar.setIzq(null);
				resultado = true;
				aux = null;
			} else {
				// No tenemos nodo a la izquierda del elemento a eliminar
				// Miramos si es nodo hoja

				if (aux.getIzq() == null && aux.getDer() == null) {
					aux.setIzq(null);
				} else {
					aux.setIzq(null);
					if (nodoAEliminar.getDer() != null) {
						insertarNodo(nodoAEliminar.getDer());
					}
				}
				
				resultado = true;
				aux = null;
			}

		} else if (aux.getDer() != null && aux.getDer().getValue() == value) {
			Nodo<Integer> nodoAEliminar = aux.getDer();
			// Si el valor está a la derecha del nodo que estamos recorriendo
			// Miramos si tenemos derecha en el nodo a eliminar

			if (aux.getDer().getDer() != null) {
				// Tenemos Nodo a la izquierda
				// Apuntamos el nodo que estamos recorriendo al siguiente del nodo a eliminar
				aux.setDer(aux.getDer().getDer());
				// Reposicionamos sus hijos
				if (nodoAEliminar.getIzq() != null) {
					insertarNodo(nodoAEliminar.getIzq());
				}
				nodoAEliminar.setDer(null);
				nodoAEliminar.setIzq(null);
				resultado = true;
				aux = null;
			} else {
				// No tenemos nodo a la izquierda del elemento a eliminar
				// Miramos si es nodo hoja

				if (aux.getIzq().getIzq() == null && aux.getDer().getDer() == null) {
					aux.setDer(null);
				} else {
					aux.setDer(null);
					if (nodoAEliminar.getIzq() != null) {
						insertarNodo(nodoAEliminar.getIzq());
					}

				}
				
				resultado = true;
				aux = null;
			}
		} else {
			if (value > aux.getValue()) {
				aux = aux.getDer();
			} else {
				aux = aux.getIzq();
			}
		}
	}
	
	//En caso de borrar el nodo disminuimos la cantidad de nodos en 1
	if (resultado) {
		numeroElementos--;
	}

	return resultado;

}

Lo primero que hacemos en este método es crear una variable booleana que utilizaremos para saber si hemos borrado el nodo y devolver como resultado «true» o «false». Luego creamos como siempre un puntero auxiliar para movernos por el árbol.

Este algoritmo funciona de la siguiente forma:

  • Si el elemento a eliminar es el nodo raíz, eliminamos la raíz, y si tenemos la parte derecha ponemos la parte derecha como nueva raíz y reposicionamos el hijo izquierdo del antiguo nodo raíz en caso de que lo tenga. Si no tenemos parte derecha, ponemos la parte izquierda del nodo raíz como nueva raíz y no reposicionamos nada. Si no tenemos ni parte izquierda ni derecha asignamos la raíz a null, ya que nuestro árbol estará vacio.
  • En caso de que el elemento a eliminar no sea la raíz, si encontramos el elemento por la izquierda miramos si hay un nodo más a la izquierda del elemento a eliminar, y en el caso de que lo haya apuntamos el nodo anterior del nodo que queremos eliminar al nodo siguiente izquierdo del nodo que queremos eliminar y reposicionamos la parte derecha del nodo a eliminar. Si el nodo que queremos eliminar no tiene nodo siguiente izquierdo, miramos si se trata de un nodo hoja, en caso de que sea un nodo hoja lo eliminamos sin más. En caso de que no sea hoja eliminamos el nodo y reposicionamos la parte derecha.
  • En caso de que el elemento a eliminar no sea la raíz, si encontramos el elemento por la derecha miramos si hay un nodo más a la derecha del elemento a eliminar, y en el caso de que lo haya apuntamos el nodo anterior del nodo que queremos eliminar al nodo siguiente derecho del nodo que queremos eliminar y reposicionamos la parte izquierda del nodo a eliminar. Si el nodo que queremos eliminar no tiene nodo siguiente derecho, miramos si se trata de un nodo hoja, en caso de que sea un nodo hoja lo eliminamos sin más. En caso de que no sea hoja eliminamos el nodo y reposicionamos la parte izquierda.
  • En caso de que no se cumpla ninguna condición vamos avanzando por el árbol en función de si nuestro valor a eliminar es mayor o menor que el nodo que estamos recorriendo.

Si no encontramos el nodo a eliminar llegará un momento en el que «aux» valdrá «null».

El método insertarNodo

private void insertarNodo(Nodo<Integer> nodo) {
	if (raiz == null) {
		raiz = nodo;
		System.out.println("Inserto la raiz");
	} else {
		// Necesitamos encontrar en que posición debemos insertar el nodo
		Nodo<Integer> aux = raiz;

		while (aux != null) {
			// Comprobamos si tenemos que insertarlo ya
			// Comprobamos si nodo hoja
			if (aux.getDer() == null && aux.getIzq() == null) {
				if (nodo.getValue() > aux.getValue()) {
					// Derecha
					System.out.println(nodo.getValue() + " Lo insertamos a la derecha de: " + aux.getValue());
					aux.setDer(nodo);
					aux = null;
				} else {
					// Izquierda
					System.out.println(nodo.getValue() + " Lo insertamos a la izquierda de: " + aux.getValue());
					aux.setIzq(nodo);
					aux = null;
				}
			} else if (nodo.getValue() > aux.getValue() && aux.getDer() == null) {
				// Lo insertamos a la derecha
				System.out.println(nodo.getValue() + " Lo insertamos a la derecha de: " + aux.getValue());
				aux.setDer(nodo);
				aux = null;
			} else if (nodo.getValue() < aux.getValue() && aux.getIzq() == null) {
				// Lo insertamos a la izquierda
				System.out.println(nodo.getValue() + " Lo insertamos a la izquierda de: " + aux.getValue());
				aux.setIzq(nodo);
				aux = null;
			} else {
				// Pasamos de nodo
				if (nodo.getValue() > aux.getValue()) {
					aux = aux.getDer();
				} else {
					aux = aux.getIzq();
				}
			}

		}
	}
}

Este método funciona igual que el método «insertarElemento», pero a diferencia del anterior este no inserta el valor, sino que inserta nodos. Se utiliza para reposicionar los nodos después de las eliminaciones.

El método size

public int size() {
	return this.numeroElementos;
}

Este método es verdaderamente muy sencillo, simplemente devuelve el número de elementos que tenemos en nuestro árbol.

El método getNumeroIteracionesUltimaBusqueda

public int getNumeroIteracionesUltimaBusqueda() {
	return this.numeroIteracionesUltimaBusqueda;
}

El método también es verdaderamente sencillo, cada vez que realizamos una búsqueda y pasamos de un nodo a otro se va incrementando la variable «numeroIteracionesUltimaBusqueda». Por lo tanto, este método solo devuelve el valor de dicha variable.

El método «getNumeroIteracionesMedioEnBusquedas»

public int getNumeroIteracionesMedioEnBusquedas() {
	return (int) Math.ceil(numeroIteracionesTotal / (double) this.numeroBusquedas);
}

Este método calcula la media del numero de iteraciones de todas las búsquedas. Cada vez que realizamos una iteración en el método de buscar incrementamos en 1 la variable «numeroIteracionesTotal».

El método obtenerElementosOrdenadosAscendentemente

public ArrayList<Integer> obtenerElementosOrdenadosAscendentemente() {
	ArrayList<Integer> elementosOrdenados = new ArrayList<>();
	recorrerAscendente(raiz, elementosOrdenados);
	return elementosOrdenados;
}

Este método devuelve un «ArrayList» de «Integer» con los elementos ordenados de forma ascendente. hace uso del método «recorrerAscendente» que se ejecuta de forma recursiva:

private void recorrerAscendente(Nodo<Integer> nodo, ArrayList<Integer> elementos) {
	if (nodo != null) {
		if (nodo.getIzq() == null && nodo.getDer() == null) {
			elementos.add(nodo.getValue());
		} else {
			recorrerAscendente(nodo.getIzq(), elementos);
			elementos.add(nodo.getValue());
			recorrerAscendente(nodo.getDer(), elementos);
		}
	}
}

No vamos a explicar la recursividad en esta entrada, porque es un tema bastante complejo, pero básicamente este método inserta los elementos cuando llega al caso base y cuando se ha resuelto la recursividad para el nodo izquierdo. De forma que si tenemos el siguiente árbol:

Representación de un Árbol Binario de Búsqueda en Java para explicar la recursividad

Primero se insertaría el elemento 13(parte izquierda), luego el «17» (nodo padre) y luego la parte derecha, el «18». El resultado sería 13,17,18.

El método obtenerElementosOrdenadosDescendentemente

Este método funciona de la misma forma que el anterior pero resolviendo primero la parte derecha del árbol.

public ArrayList<Integer> obtenerElementosOrdenadosDescendentemente() {
	ArrayList<Integer> elementosOrdenados = new ArrayList<>();
	recorrerDescendente(raiz, elementosOrdenados);
	return elementosOrdenados;
}

private void recorrerDescendente(Nodo<Integer> nodo, ArrayList<Integer> elementos) {
	if (nodo != null) {
		if (nodo.getIzq() == null && nodo.getDer() == null) {
			elementos.add(nodo.getValue());
		} else {
			recorrerDescendente(nodo.getDer(), elementos);
			elementos.add(nodo.getValue());
			recorrerDescendente(nodo.getIzq(), elementos);
		}
	}

}

Y con esto ya hemos acabado nuestra explicación de la implementación. Vamos ahora a realizar pruebas sobre nuestro árbol.

Vamos a insertar el siguiente árbol:

Representación del Árbol Binario de Búsqueda en Java que utilizaremos para las pruebas

Sobre este árbol:

  1. Obtendremos el número de elementos que tenemos.
  2. Obtendremos e imprimiremos los elementos de forma ascendente.
  3. Obtendremos e imprimiremos los elementos de forma descendente.
  4. Realizaremos diferentes búsquedas.
  5. Imprimiremos el numero de iteraciones de las búsquedas. Tanto individualmente como la media.
  6. Eliminaremos elementos.
  7. Volveremos a realizar búsquedas.
  8. Obtendremos de nuevo los elementos de forma ascendente y descendente.
  9. Imprimiremos el número de elementos que tenemos

Veamos el código:

public static void main(String[] args) {

	//Creamos el Arbol binario de Busqueda
	ArbolBinarioBusqueda abb = new ArbolBinarioBusqueda();
	
	//Insertamos nos nodos
	abb.insertarElemento(15);
	abb.insertarElemento(9);
	abb.insertarElemento(20);
	abb.insertarElemento(6);
	abb.insertarElemento(14);
	abb.insertarElemento(13);
	abb.insertarElemento(17);
	abb.insertarElemento(64);
	abb.insertarElemento(72);
	abb.insertarElemento(26);

	//Imprimimos el número de elementos que tenemos:
	System.out.println("Número de elementos: " + abb.size());
	
	//Obtenemos los números ordenados ascendentemente
	ArrayList<Integer> numerosOrdenadosAscedentemente = abb.obtenerElementosOrdenadosAscendentemente();
	System.out.print("Lista de números ordenados ascendentemente: [ ");
	
	for (Integer numero: numerosOrdenadosAscedentemente) {
		System.out.print(numero + " ");
	}
	System.out.print("]\n");
	
	//Obtenemos los números ordenados descendentemente
	ArrayList<Integer> numerosOrdenadosDescedentemente = abb.obtenerElementosOrdenadosDescendentemente();
	System.out.print("Lista de números ordenados descendentemente: [ ");
	
	for (Integer numero: numerosOrdenadosDescedentemente) {
		System.out.print(numero + " ");
	}
	System.out.print("]\n");
	
	//Realizamos diferentes búsquedas
	if (abb.buscarElemento(20) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(72) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(56) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(6) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(9) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	//imprimimos estadisticas
	System.out.println("Numero de iteraciones en la última búsqueda: " + abb.getNumeroIteracionesUltimaBusqueda());
	System.out.println("Numero de iteraciones medio en las búsquedas: " + abb.getNumeroIteracionesMedioEnBusquedas());

	//Eliminamos nodos
	//Eliminamos la raiz
	abb.eliminarElemento(15);
	//Eliminamos nodos
	abb.eliminarElemento(13);
	abb.eliminarElemento(14);
	abb.eliminarElemento(64);
	
	//Buscamos los elementos eliminado
	if (abb.buscarElemento(15) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(13) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(14) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	if (abb.buscarElemento(64) != null) {
		System.out.println("Elemento encontrado");
	}else {
		System.out.println("Elemento no encontrado");
	}
	
	//Obtenemos los números ordenados ascendentemente
	numerosOrdenadosAscedentemente = abb.obtenerElementosOrdenadosAscendentemente();
	System.out.print("Lista de números ordenados ascendentemente: [ ");
	
	for (Integer numero: numerosOrdenadosAscedentemente) {
		System.out.print(numero + " ");
	}
	System.out.print("]\n");
	
	//Obtenemos los números ordenados descendentemente
	numerosOrdenadosDescedentemente = abb.obtenerElementosOrdenadosDescendentemente();
	System.out.print("Lista de números ordenados descendentemente: [ ");
	
	for (Integer numero: numerosOrdenadosDescedentemente) {
		System.out.print(numero + " ");
	}
	System.out.print("]\n");
	
	//Imprimimos el número de elementos que tenemos:
	System.out.println("Número de elementos: " + abb.size());
}

Inserto la raiz
9 Lo insertamos a la izquierda de: 15
20 Lo insertamos a la derecha de: 15
6 Lo insertamos a la izquierda de: 9
14 Lo insertamos a la derecha de: 9
13 Lo insertamos a la izquierda de: 14
17 Lo insertamos a la izquierda de: 20
64 Lo insertamos a la derecha de: 20
72 Lo insertamos a la derecha de: 64
26 Lo insertamos a la izquierda de: 64
Número de elementos: 10
Lista de números ordenados ascendentemente: [ 6 9 13 14 15 17 20 26 64 72 ]
Lista de números ordenados descendentemente: [ 72 64 26 20 17 15 14 13 9 6 ]
Elemento encontrado
Elemento encontrado
Elemento no encontrado
Elemento encontrado
Elemento encontrado
Numero de iteraciones en la última búsqueda: 2
Numero de iteraciones medio en las búsquedas: 3
9 Lo insertamos a la izquierda de: 17
26 Lo insertamos a la izquierda de: 72
Elemento no encontrado
Elemento no encontrado
Elemento no encontrado
Elemento no encontrado
Lista de números ordenados ascendentemente: [ 6 9 17 20 26 72 ]
Lista de números ordenados descendentemente: [ 72 26 20 17 9 6 ]
Número de elementos: 6

Implementación de Árboles Binarios de Búsqueda Genéricos en Java

Nuestra clase NodoGenerico

public class NodoGenerico<V> {

	private V value;
	private NodoGenerico<V> izq;
	private NodoGenerico<V> der;
	
	public NodoGenerico(V value, NodoGenerico<V> izq, NodoGenerico<V> der) {
		super();
		this.value = value;
		this.izq = izq;
		this.der = der;
	}

	public V getValue() {
		return value;
	}

	public void setValue(V value) {
		this.value = value;
	}

	public NodoGenerico<V> getIzq() {
		return izq;
	}

	public void setIzq(NodoGenerico<V> izq) {
		this.izq = izq;
	}

	public NodoGenerico<V> getDer() {
		return der;
	}

	public void setDer(NodoGenerico<V> der) {
		this.der = der;
	}
}

Nuestra clase Producto

public class Producto extends Comparable<Producto>{
	private int id;
	private String nombre;
	
	public Producto(int id, String nombre) {
		this.id = id;
		this.nombre = nombre;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getNombre() {
		return nombre;
	}

	public void setNombre(String nombre) {
		this.nombre = nombre;
	}
	
	@Override
	public boolean equals(Object p2) {
		Producto producto2 = (Producto)p2;
		if (this.getId() == producto2.getId() && this.getNombre().equals(producto2.getNombre())) {
			return true;
		}else {
			return false;
		}
	}

	@Override
	int compare(Producto value) {
		if (this.id > value.getId()) {
			return 1;
		}else if (this.id < value.getId()) {
			return -1;
		}else {
			//Si son iguales
			return 0;
		}
	}

	@Override
	public String toString() {
		return "Producto [id=" + id + ", nombre=" + nombre + "]";
	}
}

En esta clase es necesario fijarse en 2 cosas:

  1. Extiende de la clase abstracta «Comparable»
  2. Implementa el método «compare»

La clase abstracta es la siguiente:

abstract class Comparable<V> {
	abstract int compare(V elementoAComparar);
}

Al extender de la clase abstracta estamos obligados a implementar el método compare. Este método devolverá «1» en el caso de que el «id» de nuestro producto sea superior al «id» del producto que le llega por parámetro, -1 en caso contrario y 0 si son iguales.

Este método será el que utilizaremos en nuestra implementación del árbol para realizar las comparaciones

Nuestra clase ArbolBinarioBusquedaGenerico

import java.util.ArrayList;

public class ArbolBinarioBusquedaGenerico<V extends Comparable<V>> {

	NodoGenerico<V> raiz = null;
	private int numeroElementos = 0;
	private int numeroBusquedas = 0;
	private int numeroIteracionesTotal = 0;
	private int numeroIteracionesUltimaBusqueda = 0;

	public ArbolBinarioBusquedaGenerico() {

	}

	public void insertarElemento(V value) {
		NodoGenerico<V> nuevoNodo = new NodoGenerico<V>(value, null, null);

		if (raiz == null) {
			raiz = nuevoNodo;
			System.out.println("Inserto la raiz");
		} else {
			// Necesitamos encontrar en que posición debemos insertar el nodo
			NodoGenerico<V> aux = raiz;

			while (aux != null) {
				// Comprobamos si tenemos que insertarlo ya
				// Comprobamos si nodo hoja
				if (aux.getDer() == null && aux.getIzq() == null) {
					if (value.compare(aux.getValue()) == 1) {
						// Derecha
						System.out.println(value + " Lo insertamos a la derecha de: " + aux.getValue());
						aux.setDer(nuevoNodo);
						aux = null;
					} else {
						// Izquierda
						System.out.println(value + " Lo insertamos a la izquierda de: " + aux.getValue());
						aux.setIzq(nuevoNodo);
						aux = null;
					}
				} else if (value.compare(aux.getValue()) == 1 && aux.getDer() == null) {
					// Lo insertamos a la derecha
					System.out.println(value + " Lo insertamos a la derecha de: " + aux.getValue());
					aux.setDer(nuevoNodo);
					aux = null;
				} else if (value.compare(aux.getValue()) == -1 && aux.getIzq() == null) {
					// Lo insertamos a la izquierda
					System.out.println(value + " Lo insertamos a la izquierda de: " + aux.getValue());
					aux.setIzq(nuevoNodo);
					aux = null;
				} else {
					// Pasamos de nodo
					if (value.compare(aux.getValue()) == 1) {
						aux = aux.getDer();
					} else {
						aux = aux.getIzq();
					}
				}

			}

		}

		// Incrementamos el número de elementos en 1
		numeroElementos++;
	}

	public V buscarElemento(V value) {
		NodoGenerico<V> aux = raiz;
		NodoGenerico<V> resultado = null;
		numeroIteracionesUltimaBusqueda = 0;

		while (aux != null) {
			// Comprobamos si es el valor
			if (value.compare(aux.getValue()) == 0) {
				// Hemos encontrado el elemento
				resultado = aux;
				aux = null;
			} else if (aux.getDer() == null && aux.getIzq() == null) {
				// Si hemos llegado a un nodo hoja el elemento no está en el ABB
				// El elemento no está
				aux = null;
			} else if (value.compare(aux.getValue()) == 1 && aux.getDer() != null) {
				// Si el valor es mayor y tenemos nodo a la derecha, vamos a la derecha
				aux = aux.getDer();
			} else if (value.compare(aux.getValue()) == -1 && aux.getIzq() != null) {
				// Si el valor es menos y tenemos nodo a la izquierda, vamos a la izquierda
				aux = aux.getIzq();
			} else {
				// Si el nodo es mayor y no tenemos nodo a la derecha o es menor y no tenemos
				// nodo a la izquierda
				// El elemento no está
				aux = null;
			}

			numeroIteracionesUltimaBusqueda++;
		}

		numeroIteracionesTotal += numeroIteracionesUltimaBusqueda;
		numeroBusquedas++;

		if (resultado != null) {
			return resultado.getValue();
		}else {
			return null;
		}
	}

	public boolean eliminarElemento(V value) {
		boolean resultado = false;
		NodoGenerico<V> aux = raiz;

		while (aux != null) {
			// Si es la raiz
			if (aux.getValue().compare(value) == 0) {
				NodoGenerico<V> nodoAEliminar = aux;

				if (aux.getDer() != null) {
					raiz = aux.getDer();
					if (nodoAEliminar.getIzq() != null) {
						insertarNodo(nodoAEliminar.getIzq());
						nodoAEliminar.setIzq(null);
						nodoAEliminar.setDer(null);
					}
				} else if (aux.getIzq() != null) {
					raiz = aux.getIzq();
					if (nodoAEliminar.getDer() != null) {
						insertarNodo(nodoAEliminar.getDer());
						nodoAEliminar.setIzq(null);
						nodoAEliminar.setDer(null);
					}
				} else {
					raiz = null;
				}

				resultado = true;
				aux = null;
			} else if (aux.getIzq() != null && aux.getIzq().getValue().compare(value) == 0) {
				NodoGenerico<V> nodoAEliminar = aux.getIzq();
				// Si el valor está a la izquierda del nodo que estamos recorriendo
				// Miramos si tenemos izquierda en el nodo a eliminar

				if (aux.getIzq().getIzq() != null) {
					// Tenemos Nodo a la izquierda
					// Apuntamos el nodo que estamos recorriendo al siguiente del nodo a eliminar
					aux.setIzq(aux.getIzq().getIzq());
					// Reposicionamos sus hijos
					if (nodoAEliminar.getDer() != null) {
						insertarNodo(nodoAEliminar.getDer());
					}
					nodoAEliminar.setDer(null);
					nodoAEliminar.setIzq(null);
					resultado = true;
					aux = null;
				} else {
					// No tenemos nodo a la izquierda del elemento a eliminar
					// Miramos si es nodo hoja

					if (aux.getIzq() == null && aux.getDer() == null) {
						aux.setIzq(null);
					} else {
						aux.setIzq(null);
						if (nodoAEliminar.getDer() != null) {
							insertarNodo(nodoAEliminar.getDer());
						}
					}

					resultado = true;
					aux = null;
				}

			} else if (aux.getDer() != null && aux.getDer().getValue().compare(value) == 0) {
				NodoGenerico<V> nodoAEliminar = aux.getDer();
				// Si el valor está a la derecha del nodo que estamos recorriendo
				// Miramos si tenemos derecha en el nodo a eliminar

				if (aux.getDer().getDer() != null) {
					// Tenemos Nodo a la izquierda
					// Apuntamos el nodo que estamos recorriendo al siguiente del nodo a eliminar
					aux.setDer(aux.getDer().getDer());
					// Reposicionamos sus hijos
					if (nodoAEliminar.getIzq() != null) {
						insertarNodo(nodoAEliminar.getIzq());
					}
					nodoAEliminar.setDer(null);
					nodoAEliminar.setIzq(null);
					resultado = true;
					aux = null;
				} else {
					// No tenemos nodo a la izquierda del elemento a eliminar
					// Miramos si es nodo hoja

					if (aux.getIzq().getIzq() == null && aux.getDer().getDer() == null) {
						aux.setDer(null);
					} else {
						aux.setDer(null);
						if (nodoAEliminar.getIzq() != null) {
							insertarNodo(nodoAEliminar.getIzq());
						}

					}

					resultado = true;
					aux = null;
				}
			} else {
				if (value.compare(aux.getValue()) == 1) {
					aux = aux.getDer();
				} else {
					aux = aux.getIzq();
				}
			}
		}

		// En caso de borrar el nodo disminuimos la cantidad de nodos en 1
		if (resultado) {
			numeroElementos--;
		}

		return resultado;

	}

	private void insertarNodo(NodoGenerico<V> nodo) {
		if (raiz == null) {
			raiz = nodo;
			System.out.println("Inserto la raiz");
		} else {
			// Necesitamos encontrar en que posición debemos insertar el nodo
			NodoGenerico<V> aux = raiz;

			while (aux != null) {
				// Comprobamos si tenemos que insertarlo ya
				// Comprobamos si nodo hoja
				if (aux.getDer() == null && aux.getIzq() == null) {
					if (nodo.getValue().compare(aux.getValue()) == 1) {
						// Derecha
						System.out.println(nodo.getValue() + " Lo insertamos a la derecha de: " + aux.getValue());
						aux.setDer(nodo);
						aux = null;
					} else {
						// Izquierda
						System.out.println(nodo.getValue() + " Lo insertamos a la izquierda de: " + aux.getValue());
						aux.setIzq(nodo);
						aux = null;
					}
				} else if (nodo.getValue().compare(aux.getValue()) == 1 && aux.getDer() == null) {
					// Lo insertamos a la derecha
					System.out.println(nodo.getValue() + " Lo insertamos a la derecha de: " + aux.getValue());
					aux.setDer(nodo);
					aux = null;
				} else if (nodo.getValue().compare(aux.getValue()) == -1 && aux.getIzq() == null) {
					// Lo insertamos a la izquierda
					System.out.println(nodo.getValue() + " Lo insertamos a la izquierda de: " + aux.getValue());
					aux.setIzq(nodo);
					aux = null;
				} else {
					// Pasamos de nodo
					if (nodo.getValue().compare(aux.getValue()) == 1) {
						aux = aux.getDer();
					} else {
						aux = aux.getIzq();
					}
				}

			}
		}
	}

	public int size() {
		return this.numeroElementos;
	}

	public int getNumeroIteracionesMedioEnBusquedas() {
		return (int) Math.ceil(numeroIteracionesTotal / (double) this.numeroBusquedas);
	}

	public int getNumeroIteracionesUltimaBusqueda() {
		return this.numeroIteracionesUltimaBusqueda;
	}

	public ArrayList<V> obtenerElementosOrdenadosAscendentemente() {
		ArrayList<V> elementosOrdenados = new ArrayList<>();
		recorrerAscendente(raiz, elementosOrdenados);
		return elementosOrdenados;
	}

	public ArrayList<V> obtenerElementosOrdenadosDescendentemente() {
		ArrayList<V> elementosOrdenados = new ArrayList<>();
		recorrerDescendente(raiz, elementosOrdenados);
		return elementosOrdenados;
	}

	private void recorrerAscendente(NodoGenerico<V> nodo, ArrayList<V> elementos) {
		if (nodo != null) {
			if (nodo.getIzq() == null && nodo.getDer() == null) {
				elementos.add(nodo.getValue());
			} else {
				recorrerAscendente(nodo.getIzq(), elementos);
				elementos.add(nodo.getValue());
				recorrerAscendente(nodo.getDer(), elementos);
			}
		}

	}

	private void recorrerDescendente(NodoGenerico<V> nodo, ArrayList<V> elementos) {
		if (nodo != null) {
			if (nodo.getIzq() == null && nodo.getDer() == null) {
				elementos.add(nodo.getValue());
			} else {
				recorrerDescendente(nodo.getDer(), elementos);
				elementos.add(nodo.getValue());
				recorrerDescendente(nodo.getIzq(), elementos);
			}
		}

	}

}

Vamos a realizar las mismas pruebas que en apartado anterior, y vamos a insertar el mismo árbol, pero en este caso no contendrá enteros, sino productos.

Las pruebas serán:

  1. Obtendremos el número de elementos que tenemos.
  2. Obtendremos e imprimiremos los elementos de forma ascendente.
  3. Obtendremos e imprimiremos los elementos de forma descendente.
  4. Realizaremos diferentes búsquedas.
  5. Imprimiremos el numero de iteraciones de las búsquedas. Tanto individualmente como la media.
  6. Eliminaremos elementos.
  7. Volveremos a realizar búsquedas.
  8. Obtendremos de nuevo los elementos de forma ascendente y descendente.
  9. Imprimiremos el número de elementos que tenemos

Veamos el código:

public static void main(String[] args) {

	// Creamos los productos
	Producto p1 = new Producto(15, "Tercas");
	Producto p2 = new Producto(9, "Tercas");
	Producto p3 = new Producto(20, "Tercas");
	Producto p4 = new Producto(6, "Tercas");
	Producto p5 = new Producto(14, "Tercas");
	Producto p6 = new Producto(13, "Tercas");
	Producto p7 = new Producto(17, "Tercas");
	Producto p8 = new Producto(64, "Tercas");
	Producto p9 = new Producto(72, "Tercas");
	Producto p10 = new Producto(26, "Tercas");

	// Creamos nuestro arbol generico parametrizado para productos
	ArbolBinarioBusquedaGenerico<Producto> abb = new ArbolBinarioBusquedaGenerico<Producto>();

	// Insertamos los productos
	abb.insertarElemento(p1);
	abb.insertarElemento(p2);
	abb.insertarElemento(p3);
	abb.insertarElemento(p4);
	abb.insertarElemento(p5);
	abb.insertarElemento(p6);
	abb.insertarElemento(p7);
	abb.insertarElemento(p8);
	abb.insertarElemento(p9);
	abb.insertarElemento(p10);

	// Imprimimos el número de elementos que tenemos:
	System.out.println("Número de elementos: " + abb.size());

	// Obtenemos los números ordenados ascendentemente
	ArrayList<Producto> numerosOrdenadosAscedentemente = abb.obtenerElementosOrdenadosAscendentemente();
	System.out.print("Lista de números ordenados ascendentemente: { ");

	for (Producto producto : numerosOrdenadosAscedentemente) {
		System.out.print(producto + " ");
	}
	System.out.print("}\n");

	// Obtenemos los números ordenados descendentemente
	ArrayList<Producto> numerosOrdenadosDescedentemente = abb.obtenerElementosOrdenadosDescendentemente();
	System.out.print("Lista de números ordenados descendentemente: { ");

	for (Producto producto : numerosOrdenadosDescedentemente) {
		System.out.print(producto + " ");
	}
	System.out.print("}\n");

	// Realizamos diferentes búsquedas
	if (abb.buscarElemento(new Producto(20, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(72, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(56, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(6, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(9, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	// imprimimos estadisticas
	System.out.println("Numero de iteraciones en la última búsqueda: " + abb.getNumeroIteracionesUltimaBusqueda());
	System.out
			.println("Numero de iteraciones medio en las búsquedas: " + abb.getNumeroIteracionesMedioEnBusquedas());

	// Eliminamos nodos
	// Eliminamos la raiz
	abb.eliminarElemento(new Producto(15, ""));
	// Eliminamos nodos
	abb.eliminarElemento(new Producto(13, ""));
	abb.eliminarElemento(new Producto(14, ""));
	abb.eliminarElemento(new Producto(64, ""));

	// Buscamos los elementos eliminado
	if (abb.buscarElemento(new Producto(15, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(13, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(14, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	if (abb.buscarElemento(new Producto(64, "")) != null) {
		System.out.println("Elemento encontrado");
	} else {
		System.out.println("Elemento no encontrado");
	}

	// Obtenemos los números ordenados ascendentemente
	numerosOrdenadosAscedentemente = abb.obtenerElementosOrdenadosAscendentemente();
	System.out.print("Lista de números ordenados ascendentemente: { ");

	for (Producto producto : numerosOrdenadosAscedentemente) {
		System.out.print(producto + " ");
	}
	System.out.print("}\n");

	// Obtenemos los números ordenados descendentemente
	numerosOrdenadosDescedentemente = abb.obtenerElementosOrdenadosDescendentemente();
	System.out.print("Lista de números ordenados descendentemente: { ");

	for (Producto producto : numerosOrdenadosDescedentemente) {
		System.out.print(producto + " ");
	}
	System.out.print("}\n");

	// Imprimimos el número de elementos que tenemos:
	System.out.println("Número de elementos: " + abb.size());

}

El resultado de nuestras pruebas

Inserto la raiz
Producto [id=9, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=15, nombre=Tercas]
Producto [id=20, nombre=Tercas] Lo insertamos a la derecha de: Producto [id=15, nombre=Tercas]
Producto [id=6, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=9, nombre=Tercas]
Producto [id=14, nombre=Tercas] Lo insertamos a la derecha de: Producto [id=9, nombre=Tercas]
Producto [id=13, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=14, nombre=Tercas]
Producto [id=17, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=20, nombre=Tercas]
Producto [id=64, nombre=Tercas] Lo insertamos a la derecha de: Producto [id=20, nombre=Tercas]
Producto [id=72, nombre=Tercas] Lo insertamos a la derecha de: Producto [id=64, nombre=Tercas]
Producto [id=26, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=64, nombre=Tercas]
Número de elementos: 10
Lista de números ordenados ascendentemente: { Producto [id=6, nombre=Tercas] Producto [id=9, nombre=Tercas] Producto [id=13, nombre=Tercas] Producto [id=14, nombre=Tercas] Producto [id=15, nombre=Tercas] Producto [id=17, nombre=Tercas] Producto [id=20, nombre=Tercas] Producto [id=26, nombre=Tercas] Producto [id=64, nombre=Tercas] Producto [id=72, nombre=Tercas] }
Lista de números ordenados descendentemente: { Producto [id=72, nombre=Tercas] Producto [id=64, nombre=Tercas] Producto [id=26, nombre=Tercas] Producto [id=20, nombre=Tercas] Producto [id=17, nombre=Tercas] Producto [id=15, nombre=Tercas] Producto [id=14, nombre=Tercas] Producto [id=13, nombre=Tercas] Producto [id=9, nombre=Tercas] Producto [id=6, nombre=Tercas] }
Elemento encontrado
Elemento encontrado
Elemento no encontrado
Elemento encontrado
Elemento encontrado
Numero de iteraciones en la última búsqueda: 2
Numero de iteraciones medio en las búsquedas: 3
Producto [id=9, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=17, nombre=Tercas]
Producto [id=26, nombre=Tercas] Lo insertamos a la izquierda de: Producto [id=72, nombre=Tercas]
Elemento no encontrado
Elemento no encontrado
Elemento no encontrado
Elemento no encontrado
Lista de números ordenados ascendentemente: { Producto [id=6, nombre=Tercas] Producto [id=9, nombre=Tercas] Producto [id=17, nombre=Tercas] Producto [id=20, nombre=Tercas] Producto [id=26, nombre=Tercas] Producto [id=72, nombre=Tercas] }
Lista de números ordenados descendentemente: { Producto [id=72, nombre=Tercas] Producto [id=26, nombre=Tercas] Producto [id=20, nombre=Tercas] Producto [id=17, nombre=Tercas] Producto [id=9, nombre=Tercas] Producto [id=6, nombre=Tercas] }
Número de elementos: 6

Y esta ha sido nuestra entrada de Árboles Binarios de Búsqueda en Java, espero que os haya gustado y que os haya servido para comprender mejor esta maravillosa estructura de datos.

Recordad dejad un comentario en la caja de comentarios si os ha sido útil el artículo y compartir en vuestras redes sociales la entrada!

Si os ha gustado esta entrada podéis también leer nuestra entrada sobre como implementar un ArrayList Genérico y nuestra entrada sobre como funcionan los genéricos.

Un saludo programadores!!!


COMPARTIR EN REDES SOCIALES

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *