Eliminar un Nodo

Quiz no es una de las tareas ms sencillas, ya que se pueden presentar diferentes situaciones:

Borrar un Nodo sin hijos Borrar un Nodo con un subrbol hijo Borrar un Nodo con dos subrboles hijos

Veamos como resolver cada uno de estos casos.

Caso 1 (Borrar un Nodo sin hijos) :

El caso ms sencillo, lo nico que hay que hacer es borrar el nodo y establecer el apuntador de su padre a nulo.

Caso 2 (Borrar un Nodo con un subrbol hijo) :

Este caso tampoco es muy complicado, nicamente tenemos que borrar el Nodo y el subrbol que tena pasa a ocupar su lugar.

Caso 3 (Borrar un Nodo con dos subrboles hijos) :

Este es un caso algo complejo, tenemos que tomar el hijo derecho del Nodo que queremos eliminar y recorrer hasta el hijo ms a la izquierda ( hijo izquierdo y si este tiene hijo izquierdo repetir hasta llegar al ltimo nodo a la izquierda), reemplazamos el valor del nodo que queremos eliminar por el nodo que encontramos ( el hijo ms a la izquierda ), el nodo que encontramos por ser el ms a la izquierda es imposible que tenga nodos a su izquierda pero si que es posible que tenga un subrbol a la derecha, para terminar solo nos queda proceder a eliminar este nodo de las formas que conocemos ( caso 1, caso 2 ) y tendremos la eliminacin completa.

Ahora que sabemos como eliminar nodos segn sea el caso vamos a programar cada uno de estos; tomaremos como base los archivos que ya tenamos hechos anteriormente, que pueden ver aqui . La clase que modificaremos es la clase Arbol a la cual le agregaremos estas funciones. Comenzamos con una funcin para saber el caso a utilizar de acuerdo a lo que ya vimos previamente:
public boolean removeNodo( Nodo nodo ) {

/* Creamos variables para saber si tiene hijos izquierdo y derecho */ boolean tieneNodoDerecha = nodo.getHojaDerecha() != null ? true : false; boolean tieneNodoIzquierda = nodo.getHojaIzquierda() != null ? true : false;

/* Verificamos los 3 casos diferentes y llamamos a la funcin correspondiente */

/* Caso 1: No tiene hijos */ if (!tieneNodoDerecha && !tieneNodoIzquierda) { return removeNodoCaso1( nodo ); }

/* Caso 2: Tiene un hijo y el otro no */ if ( tieneNodoDerecha && !tieneNodoIzquierda ) { return removeNodoCaso2( nodo ); }

/* Caso 2: Tiene un hijo y el otro no */ if ( !tieneNodoDerecha && tieneNodoIzquierda ) { return removeNodoCaso2( nodo );

/* Caso 3: Tiene ambos hijos */ if ( tieneNodoDerecha && tieneNodoIzquierda ) { return removeNodoCaso3( nodo ); }

return false; }

La razn por la que la funcin es boolean es que se puede presentar el caso en que no exista en el rbol el nodo que queremos eliminar, en ese caso nos encargaremos ms adelante de devolver FALSE para estar enterados. Resolver el caso 1

Lo nico que hay que hacer es borrar el nodo y establecer el apuntador de su padre a nulo.

private boolean removeNodoCaso1( Nodo nodo ) { /* lo nico que hay que hacer es borrar el nodo y establecer el apuntador de su padre a nulo */ /* * Guardemos los hijos del padre temporalmente para saber cul de sus hijos hay que * eliminar */ Nodo hijoIzquierdo = nodo.getPadre().getHojaIzquierda(); Nodo hijoDerecho = nodo.getPadre().getHojaDerecha(); if ( hijoIzquierdo == nodo ) { nodo.getPadre().setHojaIzquierda( null ); return true; } if ( hijoDerecho == nodo) {

nodo.getPadre().setHojaDerecha( null ); return true; } return false; }

Vemos las lneas resaltadas donde se hace la eliminacin del nodo ( nicamente se cambia el valor del padre a NULL, pero como sabemos en java cuando el objeto no tiene referencias, al pasar el garbage collector lo elimina de memoria, liberando la misma.
Resolver el caso 2:

Borrar el Nodo y el subrbol que tena pasa a ocupar su lugar

private boolean removeNodoCaso2( Nodo nodo ) { /* Borrar el Nodo y el subrbol que tena pasa a ocupar su lugar */ /* * Guardemos los hijos del padre temporalmente para saber cul de sus hijos hay que * eliminar */ Nodo hijoIzquierdo = nodo.getPadre().getHojaIzquierda(); Nodo hijoDerecho = nodo.getPadre().getHojaDerecha(); /* * Buscamos el hijo existente del nodo que queremos eliminar */ Nodo hijoActual = nodo.getHojaIzquierda() != null ? nodo.getHojaIzquierda() : nodo.getHojaDerecha(); if ( hijoIzquierdo == nodo ) { nodo.getPadre().setHojaIzquierda( hijoActual ); /* Eliminando todas las referencias hacia el nodo */ hijoActual.setPadre(nodo.getPadre()); nodo.setHojaDerecha(null); nodo.setHojaIzquierda(null); return true; } if ( hijoDerecho == nodo) { nodo.getPadre().setHojaDerecha( hijoActual );

/* Eliminando todas las referencias hacia el nodo */ hijoActual.setPadre(nodo.getPadre()); nodo.setHojaDerecha(null); nodo.setHojaIzquierda(null); return true; } return false; }
Resolver el caso 3:

Este es un caso algo complejo, tenemos que tomar el hijo derecho del Nodo que queremos eliminar y recorrer hasta el hijo ms a la izquierda ( hijo izquierdo y si este tiene hijo izquierdo repetir hasta llegar al ltimo nodo a la izquierda), reemplazamos el valor del nodo que queremos eliminar por el nodo que encontramos ( el hijo ms a la izquierda ), el nodo que encontramos por ser el ms a la izquierda es imposible que tenga nodos a su izquierda pero si que es posible que tenga un subrbol a la derecha, para terminar solo nos queda proceder a eliminar este nodo de las formas que conocemos ( caso 1, caso 2 ) y tendremos la eliminacin completa.

Como dije al inicio es uno de los casos ms difciles complejos en cuanto a esto, para poder hacer todo lo mencionado necesitamos usar recursividad, as que veamos como queda el cdigo

private boolean removeNodoCaso3( Nodo nodo ) { /* Tomar el hijo derecho del Nodo que queremos eliminar */ Nodo nodoMasALaIzquierda = recorrerIzquierda( nodo.getHojaDerecha() ); if ( nodoMasALaIzquierda != null ) { /* * Reemplazamos el valor del nodo que queremos eliminar por el nodo que encontramos */ nodo.setValor( nodoMasALaIzquierda.getValor() ); /* * Eliminar este nodo de las formas que conocemos ( caso 1, caso 2 ) */ removeNodo( nodoMasALaIzquierda ); return true; } return false;

} /* Recorrer de forma recursiva hasta encontrar el nodo ms a la izquierda */ private Nodo recorrerIzquierda(Nodo nodo) { if (nodo.getHojaIzquierda() != null) { return recorrerIzquierda( nodo.getHojaIzquierda() ); } return nodo; }

Para poder hacer el recorrido hacia la izquierda, hicimos una funcin recursiva que recorre todos los nodos a la izquierda a partir del nodo dado, en caso de que ya no existan nodos a su izquierda devuelve el ltimo encontrado. Y con esto, tenemos el tema de la eliminacin de nodos terminado, en la prxima entrada veremos como hacer los recorridos inorden, postorden, preorden. Y para quienes se perdieron un poco, dejo tambin el como quedaran a partir de aqu las dos clases que hasta ahora llevamos y la descarga de las mismas.

Nodo.java

public class Nodo { /* Declaraciones de variables */ private int valor; private Nodo padre; private Nodo hojaIzquierda; private Nodo hojaDerecha; /* Constructor */ public Nodo(int valor) { this.valor = valor; } /* Setters y Getters */ public void setValor(int valor) { this.valor = valor; }

public int getValor() { return valor; } public Nodo getPadre() { return padre; } public void setPadre(Nodo padre) { this.padre = padre; } public Nodo getHojaIzquierda() { return hojaIzquierda; } public void setHojaIzquierda(Nodo hojaIzquierda) { this.hojaIzquierda = hojaIzquierda; } public Nodo getHojaDerecha() { return hojaDerecha; } public void setHojaDerecha(Nodo hojaDerecha) { this.hojaDerecha = hojaDerecha; } }
Arbol.java

public class Arbol { /* Atributos */ private Nodo raiz; /* Contructories */ public Arbol() { } public Arbol( int valor ) {

this.raiz = new Nodo( valor ); } public Arbol( Nodo raiz ) { this.raiz = raiz; } /* Setters y Getters */ public Nodo getRaiz() { return raiz; } public void setRaiz(Nodo raiz) { this.raiz = raiz; } /* Funciones */ private void addNodo( Nodo nodo, Nodo raiz ) { /* 2.- Partiendo de la raz preguntamos: Nodo == null ( o no existe ) ? */ if ( raiz == null ) { /* * 3.- En caso afirmativo X pasa a ocupar el lugar del nodo y ya * hemos ingresado nuestro primer dato. */ raiz = nodo; } else { /* 4.- En caso negativo preguntamos: X < Nodo */ if ( nodo.getValor() <= raiz.getValor() ) { /* * 5.- En caso de ser menor pasamos al Nodo de la IZQUIERDA del * que acabamos de preguntar y repetimos desde el paso 2 * partiendo del Nodo al que acabamos de visitar */ addNodo( nodo , raiz.getHojaIzquierda() ); } else { /* * 6.- En caso de ser mayor pasamos al Nodo de la DERECHA y tal * cual hicimos con el caso anterior repetimos desde el paso 2 * partiendo de este nuevo Nodo. */ addNodo( nodo, raiz.getHojaDerecha() ); } } }

public void addNodo( Nodo nodo ) { this.addNodo( nodo , this.raiz ); } public boolean removeNodo( Nodo nodo ) { /* Creamos variables para saber si tiene hijos izquierdo y derecho */ boolean tieneNodoDerecha = nodo.getHojaDerecha() != null ? true : false; boolean tieneNodoIzquierda = nodo.getHojaIzquierda() != null ? true : false; /* Verificamos los 3 casos diferentes y llamamos a la funcin correspondiente */ /* Caso 1: No tiene hijos */ if (!tieneNodoDerecha && !tieneNodoIzquierda) { return removeNodoCaso1( nodo ); } /* Caso 2: Tiene un hijo y el otro no */ if ( tieneNodoDerecha && !tieneNodoIzquierda ) { return removeNodoCaso2( nodo ); } /* Caso 2: Tiene un hijo y el otro no */ if ( !tieneNodoDerecha && tieneNodoIzquierda ) { return removeNodoCaso2( nodo ); } /* Caso 3: Tiene ambos hijos */ if ( tieneNodoDerecha && tieneNodoIzquierda ) { return removeNodoCaso3( nodo ); } return false; } private boolean removeNodoCaso1( Nodo nodo ) { /* lo nico que hay que hacer es borrar el nodo y establecer el apuntador de su padre a nulo */ /* * Guardemos los hijos del padre temporalmente para saber cul de sus hijos hay que * eliminar */ Nodo hijoIzquierdo = nodo.getPadre().getHojaIzquierda(); Nodo hijoDerecho = nodo.getPadre().getHojaDerecha(); if ( hijoIzquierdo == nodo ) {

nodo.getPadre().setHojaIzquierda( null ); return true; } if ( hijoDerecho == nodo) { nodo.getPadre().setHojaDerecha( null ); return true; } return false; } private boolean removeNodoCaso2( Nodo nodo ) { /* Borrar el Nodo y el subrbol que tena pasa a ocupar su lugar */ /* * Guardemos los hijos del padre temporalmente para saber cul de sus hijos hay que * eliminar */ Nodo hijoIzquierdo = nodo.getPadre().getHojaIzquierda(); Nodo hijoDerecho = nodo.getPadre().getHojaDerecha(); /* * Buscamos el hijo existente del nodo que queremos eliminar */ Nodo hijoActual = nodo.getHojaIzquierda() != null ? nodo.getHojaIzquierda() : nodo.getHojaDerecha(); if ( hijoIzquierdo == nodo ) { nodo.getPadre().setHojaIzquierda( hijoActual ); /* Eliminando todas las referencias hacia el nodo */ hijoActual.setPadre(nodo.getPadre()); nodo.setHojaDerecha(null); nodo.setHojaIzquierda(null); return true; } if ( hijoDerecho == nodo) { nodo.getPadre().setHojaDerecha( hijoActual ); /* Eliminando todas las referencias hacia el nodo */ hijoActual.setPadre(nodo.getPadre()); nodo.setHojaDerecha(null); nodo.setHojaIzquierda(null);

return true; } return false; } private boolean removeNodoCaso3( Nodo nodo ) { /* Tomar el hijo derecho del Nodo que queremos eliminar */ Nodo nodoMasALaIzquierda = recorrerIzquierda( nodo.getHojaDerecha() ); if ( nodoMasALaIzquierda != null ) { /* * Reemplazamos el valor del nodo que queremos eliminar por el nodo que encontramos */ nodo.setValor( nodoMasALaIzquierda.getValor() ); /* * Eliminar este nodo de las formas que conocemos ( caso 1, caso 2 ) */ removeNodo( nodoMasALaIzquierda ); return true; } return false; } /* Recorrer de forma recursiva hasta encontrar el nodo ms a la izquierda */ private Nodo recorrerIzquierda(Nodo nodo) { if (nodo.getHojaIzquierda() != null) { return recorrerIzquierda( nodo.getHojaIzquierda() ); } return nodo; } }