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

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s