1 Árboles binarios de búsquedaEliminar un nodo

2 Casos posibles Si el nodo a eliminar es un: Nodo hoja Nodo con un hijoBuscar el Nodo Padre del nodo a borrar. Desconectarlo. Liberar el nodo. Nodo con un hijo Conectar el hijo con el padre del nodo a borrar. Nodo con dos hijos Localizar el nodo predecesor o sucesor del nodo a borrar. Copiar la información. Eliminar el predecesor o sucesor según sea el caso.

3 Caso: Eliminar Nodo hojaEliminar el valor 25 Paso 1 21 Nodo Padre localizado 33 13 Paso 2 40 10 18 25 21 13 33 40 10 18 25 Desconectarlo y liberar el nodo

4 Caso: Eliminar Nodo con un hijoEliminar el valor 25 Paso 1 21 Nodo Padre localizado 33 13 Paso 2 40 10 18 25 21 29 13 33 25 27 30 40 10 18 29 Conectar el Nodo Padre con el Nodo Hijo y liberar el nodo. 27 30

5 Caso: Eliminar nodo con dos hijosLocalizar el nodo predecesor o sucesor del nodo a borrar. El PREDECESOR es “el Mayor de los Menores”. El SUCESOR es “el Menor de los Mayores”. Para la implementación es igual de eficiente programar la búsqueda del predecesor que del sucesor. El valor del Predecedor (o sucesor) se copia al nodo a borrar. Eliminar el nodo del predecesor (o sucesor según sea el caso).

6 Predecesor El predecesor de: Es: 33 30 21 13 29 27Uno a la IZQUIERDA y todo a la DERECHA 21 El predecesor de: Es: 33 30 21 13 29 27 33 13 40 10 25 29 27 30

7 Sucesor El sucesor de: Es: 21 25 33 40 29 30Uno a la DERECHA y todo a la IZQUIERDA 21 El sucesor de: Es: 21 25 33 40 29 30 33 13 40 10 18 25 29 27 30

8 Caso: Eliminar Nodo con dos hijos usando el predecesorEliminar el valor 21 Paso 2 Paso 1 Localizar el valor a borrar 21 21 13 33 13 33 40 10 40 18 25 10 18 25 Localizar el Predecesor Paso 4 Copiar el valor del Predecesor al nodo que contenía el valor a borrar Paso 3 18 18 13 33 13 33 10 40 18 25 10 40 18 25 Desconectar y liberar el nodo del Predecesor

9 Caso: Eliminar Nodo con dos hijos usando el sucesorEliminar el valor 21 Paso 2 Paso 1 Localizar el valor a borrar 21 21 13 33 13 33 40 10 40 18 25 10 18 25 Localizar el Sucesor Paso 4 Copiar el valor del Sucesor al nodo que contenía el valor a borrar Paso 3 18 25 13 33 13 33 10 40 18 25 10 40 18 25 Desconectar y liberar el nodo del Sucesor

10 Implementación int eliminar(PARBOL *a, int dato) {void sustituir(PARBOL *a, PARBOL *aux); PARBOL *aux; if (*a == NULL) return 0; if ((*a)->dato < dato) eliminar(&(*a)->der, dato); else if ((*a)->dato > dato) eliminar(&(*a)->izq, dato); else if ((*a)->dato == dato) { aux = *a; if ((*a)->izq == NULL) *a = (*a)->der; else if ((*a)->der == NULL) *a = (*a)->izq; else sustituir(&(*a)->izq, &aux); free(aux); } return 1; void sustituir(PARBOL *a, PARBOL *aux) { if ((*a)->der != NULL) sustituir(&(*a)->der, aux); else { (*aux)->dato = (*a)->dato; *aux = *a; *a = (*a)->izq; }