Estructuras de datos | Árboles de búsqueda binarios | Pregunta 2

En la operación de eliminación de BST, necesitamos el sucesor en orden (o predecesor) de un Node cuando el Node que se eliminará tiene tanto el hijo izquierdo como el derecho como no vacíos. ¿Cuál de las siguientes afirmaciones sobre el sucesor en orden necesario en la operación de borrado es cierta?
(A) El sucesor en orden es siempre un Node hoja
(B) El sucesor en orden es siempre un Node hoja o un Node con un hijo izquierdo vacío
(C) El sucesor en orden puede ser un ancestro del Node
(D) El sucesor en orden siempre es una hoja Node o un Node con el hijo derecho vacío

Respuesta: (B)
Explicación: Sea X el Node que se eliminará en un árbol con la raíz como ‘raíz’. Hay tres casos para la eliminación

1) X es un Node hoja: cambiamos el puntero izquierdo o derecho del padre a NULL (dependiendo de si X es el hijo izquierdo o derecho de su padre) y eliminamos X
2) Un hijo de X está vacío: copiamos valores de no -hijo vacío a X y eliminar el hijo no vacío
3) Ambos hijos de X no están vacíos: En este caso, encontramos el sucesor en orden de X. Sea Y el sucesor en orden. Copiamos el contenido de Y a X, y elimine Y.

Sp necesitamos un sucesor en orden solo cuando tanto el hijo izquierdo como el derecho de X no están vacíos. En este caso, el sucesor en orden Y nunca puede ser un ancestro de X. En este caso, el sucesor en orden es el Node más a la izquierda en el subárbol derecho de X. Dado que es el Node más a la izquierda, el hijo izquierdo de Y debe estar vacío.