Borrar elementos de un Arbol binario


En el post Árboles binarios en Java se habló sobre como crear un árbol binario en Java y se analizaron las siguientes operaciones:

  • Agregar un nuevo nodo
  • Buscar un nodo
  • Imprimir in order
  • Imprimir in pos order
  • Imprimir in pre order

En este post se explicará como implementar el borrado de un nodo en el árbol.

Posibles escenarios

Cuando queremos borrar un elemento de un árbol binario, nos daremos cuenta que hay 3 posibles escenarios:

  • El nodo no tiene nodos hijos
  • El nodo tiene 1 hijo
  • El nodo tiene 2 hijos

A continuación se presentará como borrar el nodo con Java para cada uno de ellos.

El nodo no tiene nodos hijos

Si el nodo que se desea borrar no tiene ningún nodo hijo, el borrado será muy simple ya que lo único que se debe hacer es asignar el valor de null a la referencia padre que apunta a el.

El borrado para este escenario tendrá una complejidad de  O(Log N) por la búsqueda + O(Log 1) del borrado lo cual da una complejidad total de O(Log N).

El nodo tiene un hijo

Si el nodo que se desea borrar tiene un nodo hijo el procedimiento será el siguiente:

  • Buscar el elemento que deseamos borrar
  • Apuntar el puntero padre que apunta a el a su nodo hijo

El borrado para este escenario tendrá una complejidad de O(Log N) por la búsqueda + O(1) de la actualización de referencias = O(Log N).

El nodo tiene 2 hijos

Este es el escenario más complejo y debemos seguir lo siguiente:

  1. Buscar el elemento
  2. Para el siguiente paso tenemos dos opciones
    • Buscar el elemento más grande en el sub árbol de la izquierda (Que será conocido como predecesor).
    • Buscar el elemento más pequeño en el sub árbol de la derecha (Que será conocido como sucesor)
  3. Intercambiar el predecesor o sucesor con el nodo que se desea borrar, antes de hacerlo se deben validar los siguientes dos escenarios
    1. Si el predecesor o sucesor no tienen nodos hijos: El elemento se intercambiará con el predecesor o sucesor y será borrado
    2. Si el predecesor o sucesor tiene un nodo hijo: El elemento se intercambiará con el predecesor o sucesor, será borrado y su hijo ahora será hijo del predecesor o sucesor.

El borrado para este escenario tendrá una complejidad de O(Log N).

Analizando el código

Una vez que entendemos lo que se debe realizar, el siguiente paso será programarlo y analizar paso a paso el código:

  • Programando la búsqueda del predecessor:
public Node findPredecessor() {
	if (this.getRight() == null) {
		return this;
	} else {
		return this.getRight().findPredecessor();
	}
}
  • Programando la búsqueda del sucessor:
public Node findSuccessor() {
	if (this.getLeft() == null) {
		return this;
	} else {
		return this.getLeft().findSuccessor();
	}
}
  • Programando el borrado:
public Node delete(Integer value) {
	Node response = this;
	if (value < this.value) { 		this.left = this.left.delete(value); 	} else if (value > this.value) {
		this.right = this.right.delete(value);
	} else {
		if (this.left != null && this.right != null) {
			Node temp = this;
			Node maxOfTheLeft = this.left.findPredecessor();
			this.value = maxOfTheLeft.getValue();
			temp.left=temp.left.delete(maxOfTheLeft.getValue());
		} else if (this.left != null) {
			response = this.left;
		} else if (this.right != null) {
			response = this.right;
		} else {
			response = null;
		}
	}
	return response;
}

Analizando método por método:

  • findPredecessor : Busca el nodo más grande de la rama

  • findSuccessor : Busca el nodo más pequeño de la rama
  • delete: Busca en el árbol y cuando encuentra el elemento intercambia el predecesor de la izquierda por el elemento a borrar

Todo el código

A continuación se muestra como se ve la clase Node completa:


import java.util.Optional;

public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

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

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public void add(Integer value) {
		if (value < this.value) {
			if (left != null) {
				left.add(value);
			} else {
				left = new Node(value);
			}
		} else {
			if (right != null) {
				right.add(value);
			} else {
				right = new Node(value);
			}
		}
	}

	public Optional<Node> find(Integer value) {
		if (value == this.value) {
			return Optional.of(this);
		} else if (value < this.value) {
			if (this.left != null) {
				return this.left.find(value);
			} else {
				return Optional.empty();
			}
		} else {
			if (this.right != null) {
				return this.right.find(value);
			} else {
				return Optional.empty();
			}
		}
	}

	public void printInOrder() {
		if (left != null) {
			left.printInOrder();
		}
		System.out.println(value);
		if (right != null) {
			right.printInOrder();
		}
	}

	public void printPreOrder() {
		System.out.println(value);
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
	}

	public void printPosOrder() {
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
		System.out.println(value);
	}

	public Node findPredecessor() {
		if (this.getRight() == null) {
			return this;
		} else {
			return this.getRight().findPredecessor();
		}
	}

	public Node findSuccessor() {
		if (this.getLeft() == null) {
			return this;
		} else {
			return this.getLeft().findSuccessor();
		}
	}

	public Node delete(Integer value) {
		Node response = this;
		if (value < this.value) { 			this.left = this.left.delete(value); 		} else if (value > this.value) {
			this.right = this.right.delete(value);
		} else {
			if (this.left != null && this.right != null) {
				Node temp = this;
				Node maxOfTheLeft = this.left.findPredecessor();
				this.value = maxOfTheLeft.getValue();
				temp.left = temp.left.delete(maxOfTheLeft.getValue());
			} else if (this.left != null) {
				response = this.left;
			} else if (this.right != null) {
				response = this.right;
			} else {
				response = null;
			}
		}
		return response;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
	}

}

 Probando el código

El último paso es probar todo el código y ver que el borrado funciona, para esto ejecutaremos el siguiente código:

public class TreeTest {
	public static void main(String[] args) {
		Node root = new Node(32);
		root.add(10);
		root.add(55);
		root.add(1);
		root.add(19);
		root.add(16);
		root.add(23);
		root.add(79);
		System.out.println("Tree before deletion");
		root.printPreOrder();
		root.delete(55);
		root.delete(16);
		root.delete(32);
		System.out.println("Tree after deletion");
		root.printPreOrder();

	}
}<span 				data-mce-type="bookmark" 				id="mce_SELREST_start" 				data-mce-style="overflow:hidden;line-height:0" 				style="overflow:hidden;line-height:0" 			></span>

Como se puede ver es posible borrar nodos en los 3 escenarios mencionados anteriormente.

Si te gusta el contenido y quieres enterarte cuando realicemos un post nuevo síguenos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com

Árboles binarios en Java


Uno de los temas sobre desarrollo de software que todos los desarrolladores de software deberían conocer y que por lo mismo es cuestionado en una gran parte de las entrevistas es el manejo de arboles binarios, en este post entraremos en detalle en este tema y lo analizaremos paso a paso.

Introducción

En este ejemplo se mostrará como desarrollar un árbol binario balanceado en Java, esto significa que los datos serán ordenados en tiempo de inserción de acuerdo a lo siguiente:

  • Si el valor a insertar es menor al valor del nodo se insertará a la izquierda
  • Si el valor a insertar es mayor al valor del nodo se insertará a la derecha

La clase a desarrollar será de acuerdo al siguiente diagrama:

Tree node

Analizando la clase

El siguiente paso será analizar la clase a desarrollar, para esto expliquemos a detalle cada uno de los componentes:

  • Atributos
    • value: Cada nodo contendrá un valor almacenado
    • left : Cada nodo tendrá una rama izquierda
    • right : Cada nodo tendrá una rama derecha
  • Métodos
    • add : Permite agregar un nuevo valor al árbol binario
    • find : Permite buscar un valor en el árbol binario
    • printInOrder : Permite imprimir el árbol en modo In order
    • printPreOrder : Permite imprimir el árbol en modo Pre Order
    • printPosOrder : Permite imprimir el árbol en modo Pos Order

Creando el árbol

Para crear el árbol solo debemos crear una clase llamada Node (Nodo), veamos el código necesario para definir los atributos a utilizar:

public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}
//... Getters y setters
}

Agregar un valor nuevo

Para agregar un valor nuevo al árbol la lógica será la siguiente:

  1. Si el valor a agregar es menor al del nodo actual se insertará del lado izquierdo
  2. Si el valor a agregar es mayor al del nodo actual se insertará del lado derecho

Recordemos que cada nodo puede tener solo 2 nodos hijos, por lo tanto si el nodo actual contiene un 10 y el valor a insertar es un 7 este se insertará del lado izquierdo, si ya hay un valor insertado del lado izquierdo se ejecutará la misma lógica con el valor insertado hasta llegar a un nodo izquierdo o derecho nulo, veamos el código:

public class Node {
...// El código anterior
public void add(Integer value) {
	if (value < this.value) {
		if (left != null) {
			left.add(value);
		} else {
			left = new Node(value);
		}
	} else {
		if (right != null) {
			right.add(value);
		} else {
			right = new Node(value);
		}
	}
}
}

Como se puede observar en el código se utiliza recursividad para agregar los nodos en caso de que ya existan en el árbol.

Buscar un valor

La lógica para buscar un valor en el árbol es muy similar que para insertarlo, en el código que se mostrará se utilizará la clase Optional agregada en Java 8, veamos el código:

import java.util.Optional;
public class Node {
...// El código anterior
public Optional<Node> find(Integer value) {
	if (value == this.value) {
		return Optional.of(this);
	} else if (value < this.value) {
		if (this.left != null) {
			return this.left.find(value);
		} else {
			return Optional.empty();
		}
	} else {
		if (this.right != null) {
			return this.right.find(value);
		} else {
			return Optional.empty();
		}
	}
}
}

Como se puede ver es necesario importar la clase Optional del paquete java.util.

Imprimir los valores del árbol binario

Para imprimir los valores es necesario iterar el árbol utilizando recursividad y existen 3 formas de hacerlo:

  1. In order: Imprime el valor del nodo izquierdo, después el del nodo contenedor y al final el del nodo derecho
  2. Pre order: Imprime el valor del nodo contenedor, después el del nodo izquierdo y al final el del nodo derecho
  3. Pos order: Imprime el valor del nodo izquierdo, después el del nodo derecho y al final el del nodo contenedor

Veámoslo en código:

public class Node{
...// El código anterior
        public void printInOrder(){
		if(left!=null){
			left.printInOrder();
		}
		System.out.println(value);
		if(right!=null){
			right.printInOrder();
		}
	}

	public void printPreOrder(){
		System.out.println(value);
		if(left!=null){
			left.printPreOrder();
		}
		if(right!=null){
			right.printPreOrder();
		}
	}

	public void printPosOrder(){
		if(left!=null){
			left.printPreOrder();
		}
		if(right!=null){
			right.printPreOrder();
		}
		System.out.println(value);
	}
}

Todo el código junto

Si unimos el código anterior queda del siguiente modo:


import java.util.Optional;

/**
 * @author raidentrance
 *
 */
public class Node {
	private Integer value;
	private Node left;
	private Node right;

	public Node(Integer value) {
		this.value = value;
	}

	public Integer getValue() {
		return value;
	}

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

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public void add(Integer value) {
		if (value < this.value) {
			if (left != null) {
				left.add(value);
			} else {
				left = new Node(value);
			}
		} else {
			if (right != null) {
				right.add(value);
			} else {
				right = new Node(value);
			}
		}
	}

	public Optional<Node> find(Integer value) {
		if (value == this.value) {
			return Optional.of(this);
		} else if (value < this.value) {
			if (this.left != null) {
				return this.left.find(value);
			} else {
				return Optional.empty();
			}
		} else {
			if (this.right != null) {
				return this.right.find(value);
			} else {
				return Optional.empty();
			}
		}
	}

	public void printInOrder() {
		if (left != null) {
			left.printInOrder();
		}
		System.out.println(value);
		if (right != null) {
			right.printInOrder();
		}
	}

	public void printPreOrder() {
		System.out.println(value);
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
	}

	public void printPosOrder() {
		if (left != null) {
			left.printPreOrder();
		}
		if (right != null) {
			right.printPreOrder();
		}
		System.out.println(value);
	}

	@Override
	public String toString() {
		return "Node [value=" + value + ", left=" + left + ", right=" + right + "]";
	}

}

Probando el árbol

Para probar el árbol que creamos, utilizaremos una clase nueva llamada TreeTest, veamos el código:

import java.util.Optional;

/**
 * @author raidentrance
 *
 */
public class TreeTest {
	public static void main(String[] args) {
		Node root = new Node(10);
		root.add(5);
		root.add(15);
		root.add(8);

		Optional<Node> result = root.find(11);
		if (result.isPresent()) {
			System.out.println(result.get());
		} else {
			System.out.println("Value not found");
		}

		result = root.find(8);
		if (result.isPresent()) {
			System.out.println(result.get());
		} else {
			System.out.println("Value not found");
		}
		System.out.println("Print in order");
		root.printInOrder();
		System.out.println("Print pos order");
		root.printPosOrder();
		System.out.println("Print pre order");
		root.printPreOrder();
	}
}

Producirá la siguiente salida:

Value not found
Node [value=8, left=null, right=null]
Print in order
5
8
10
15
Print pos order
5
8
15
10
Print pre order
10
5
8
15

Si te gusta el contenido compártelo y no olvides seguirnos en nuestras redes sociales https://twitter.com/geeks_mx y https://www.facebook.com/geeksJavaMexico/.

Autor: Alejandro Agapito Bautista

Twitter: @raidentrance

Contacto:raidentrance@gmail.com