La eliminación de un elemento de un árbol binario de búsqueda consiste básicamente en, dado un elemento a eliminar:
- Identificar si dicho elemento se encuentra en el ABB (identificación de duplicados), si no existe, se podría regresar un valor que indique dicha situación y dejar el ABB sin cambios.
- Si el elemento existe en el ABB, entonces existen tres posibilidades:
- Si el elemento está almacenado en un nodo hoja, la eliminación es directa.
- Si el elemento está almacenado en un nodo con un solo hijo, el hijo sustituye al padre y se elimina el nodo correspondiente.
- Si el elemento está almacenado en un nodo con dos hijos, la regla que se adoptará será la de sustituirlo por el hijo más a la derecha del subárbol izquierdo (el mayor de los menores). También existe la regla simétrica del hijo más a la izquierda del subárbol derecho (el menor de los mayores), pero no se utilizará en el blog, por convención, se utilizará la primera.
Observe también que con el proceso de eliminación descrito con anterioridad:
- Se conserva la relación de orden que debe mantener un ABB.
- Se podría incurrir en un intento de eliminación de un ABB vacío lo cual, desde el punto de vista de la implementación generaría una excepción, por lo que sería conveniente tener una forma de verificar dicha situación.
 |
| Diagrama de clases UML para un ABB con eliminación (Java). |
 |
| Diagrama de clases UML para un ABB con eliminación (C++). |
En función de lo anterior, los diagramas de clases UML de las figuras anteriores complementan al presentado en la entrada ABB (representación y diseño). Observe que se han realizado las siguientes modificaciones en la clase ABB:
- La incorporación de un atributo privado numérico (n) con la finalidad de llevar el control del número de elementos insertados en el ABB. Respecto a la implementación de éste, se debe considerar:
- Inicializar explícitamente dicho atributo a cero en el constructor.
- Proporcionar únicamente el método de tipo get para dicho atributo: obtenN( ) (obten_n( )).
- La adición del método elimina, el cual realiza la eliminación de elemento si éste existe en el ABB devolviendo true como caso de éxito; en caso contrario, el método regresa false. Respecto a la implementación de este método, se debe considerar:
- Seguir las reglas de eliminación descritas con anterioridad.
- Lanzar la excepción ExcepcionEDVacia (excepcion_ED_vacia) ante un intento de eliminación de un ABB vacío, tal y como lo describe la relación que se muestra en los diagramas de clases.
- La incorporación del método estaVacio (esta_vacio( )), el cual regresa true si el ABB está vacío y false en caso contrario.
La implementación de las clases descritas en el diagrama UML correspondiente al lenguaje que utilice como medio, así como su correspondiente prueba, se dejan como ejercicio para el lector.
