¿Cómo eliminar un nodo del árbol BST con 2 niños?

Question

I Googled, lee varios tutoriales y vimos varias explicaciones de algoritmo de eliminación de nodos BST antes de publicar esta pregunta. Por alguna razón, no puedo encontrar una explicación completa de los algoritmos de eliminación de nodos BST.

He encontrado 4 algoritmos para eliminar el nodo con 2 niños del árbol de búsqueda binario:

1) Encuentre el nodo más pequeño del subbobrador derecho y reemplácelo con el nodo que queremos eliminar.
2) Encuentre el nodo más grande del subbobrador izquierdo y reemplácelo con el nodo que queremos eliminar.
3) Encuentre el nodo más profundo más profundo del Subree derecho y reemplácelo con el nodo que queremos eliminar.
4) Encuentre el nodo más profundo más profundo del subrador izquierdo y reemplácelo con el nodo que queremos eliminar.

Aparentemente, ninguno de esos algoritmos funciona para el siguiente caso de uso (lo más probable es que me esté perdiendo o no entiendo algo). El caso de uso es eliminar el elemento 5 del siguiente árbol:

Para el primer algoritmo, eligió el elemento 6 y perderíamos su Subree derecho. Para el segundo algoritmo, eligimos el elemento 4 y perderíamos su subbobrador izquierdo. Para el 3er algoritmo, eligió el elemento 7 y lo que violaría las reglas de BST. Para el cuarto algoritmo, eligió el elemento 3 que también violaría las reglas de BST.

¿Cuál es el algoritmo adecuado para tal caso de uso?

Answer 1

Usted tiene razón, en BST generalmente el caso en el que un nodo tiene dos hijos se reduce al caso donde un nodo tiene un niño.

Considerar un nodo con dos hijos. Cambie este nodo con su predecesor en el BST (que es el nodo casi más a la derecha en el subárbol izquierdo), o --totalmente simétrico, intercambie con el sucesor (el nodo más a la izquierda en el subárbol derecho).

El nodo que se eliminará ahora tiene a la mayoría de un niño (en caso de que fuimos al predecesor, no puede tener un niño derecho). Si no tiene hijos, eliminamos el nodo, y estamos terminados.

En caso de que el nodo tenga un solo hijo, eliminamos el nodo y lo reemplacemos por su subárbol. Volvemos a obtener un BST.

En su ejemplo, queremos eliminar 5 y intercambiarlo con su predecesor 4. Ahora 4 está en la raíz, y 5 ha dejado al niño 3. Finalmente, eliminamos 5 y ponemos a su hijo 3 en su lugar. Ahora 3 es el hijo correcto de 2.

ps. Este método a veces se llama "eliminación al copiar", porque los valores se copian de un nodo a otro. Algunos no aprueban este proceso por dos razones. La primera copia podría ser una operación costosa, y se pierden las segundas referencias (si otra armazón de datos apunta a un nodo con un cierto valor). En cambio, uno solo cambia los punteros.