5.2.3 Eliminacion Arboles Binarios

Eliminación en un árbol binario de búsqueda

La operación de eliminación en un árbol binario de búsqueda es un poco más complicada que la de inserción. Esta consiste en eliminar un nodo sin violar los principios que definen un árbol binario de búsqueda. Se deben distinguir los siguientes casos:

a)  Si el elemento a eliminar es terminal u hoja, simplemente se suprime redefiniendo el puntero de su predecesor.
b)  Si el elemento a eliminar tiene un solo descendiente, entonces tiene que sustituirse por ese descendiente.
c)  Si el elemento a eliminar tiene los dos descendientes, entonces se tiene que sustituir por el nodo que se encuentra más a la izquierda en el subárbol       derecho o por el nodo que se encuentra más a la derecha en el subárbol izquierdo.

Cabe destacar que antes de eliminar un nodo, se debe localizar éste en el árbol. Para esto se utiliza el algoritmo de búsqueda presentado anteriormente.

Eliminacion_ABB(APNODO, INFOR)
{El algoritmo realiza la eliminación de un elemento en un árbol binario de búsqueda. APNODO es una variable, por referendo, de tipo ENLACE. INFOR es un parámetro de tipo entero que contiene la información del nodo que se desea eliminar}
{AUX, AUXI y OTRO son variables auxiliares de tipo puntero. BO es una variable de tipo booleano}

1 Si (APNODO ≠ NULO)
        entonces
                1.1 Si (INFOR < APNODO^.INFO)
                        entonces 
                                Regresar a Eliminacion_ABB con APNODO^.IZQ e INFOR
                        si no 
                                1.1.1 Si (INFOR > APNODO^.INFO)
                                        entonces
                                   Regresar a Eliminacion_ABB con APNODO^.DER e INFOR
                                        si no
                                                Hacer OTRO <- NODO
                                                        1.1.1.1  Si (OTRO^.DER = NULO)
                                                                entonces
                                                                        Hacer APNODO <- OTRO^.IZQ
                                                                si no 
                                                                        1.1.1.1.1 Si (OTRO^.IZQ = NULO)
                                                                                entonces
                                                                                  Hacer APNODO <- OTRO^.DER
                                                                                si no
                                                                                        Hacer AUX <- APNODO^.IZQ
                                                                                        BO <- FALSO
                                                        1.1.1.1.1.A Mientras (AUX^.DER ≠ NIL) Repetir
                                                                                                Hacer AUX1 <- AUX
                                                                        Hacer AUX <- AUX^.DER     
                                                                        Hacer BO <- VERDADERO
                                                       1.1.1.1.1.B {Fin del ciclo del paso 1.1.1.1.1.A }
                                                                     Hacer APNODO^.INFO <- AUX^.INFO
                                                                                        OTRO <- AUX
                                                      1.1.1.1.1.C Si (BO = VERDADERO)
                                                                                                entonces
                                                                  Hacer AUX1^.DER <- AUX^.IZQ
                                                                                                si no
                                                                  Hacer APNODO^.IZQ <- AUXMZQ
                                                      1.1.1.1.1.D Fin del condicional del paso  1.1.1.1.1.C
                                                     1.1.1.1.2 Fin del condicional del paso 1.1.1.1.1
                                                         1.1.1.2 Fin del condicional del paso 1.1.1.1
                                                         Quitar (OTRO) Se libera el espacio de memoria
                                1.1.2 Fin del condicional del paso 1.1.1
                1.2. Fin del condicional del paso 1.1
        si no
                Escribir “La información a eliminar no se encuentra en el árbol"
2. Fin del condicional del paso 1