Atascado en el nodo de eliminación en un árbol binario de búsqueda cuando el nodo tiene tanto hijo izquierdo como hijo derecho.
Estoy tratando de entender el concepto de eliminación de nodos en un BST cuando el nodo tiene tanto un hijo izquierdo como un hijo derecho, pero estoy un poco confundido, porque diferentes libros y otras fuentes como la web tienen diferentes definiciones de esto.
Bueno, en mi caso, los datos son:
150, 100, 200, 80, 120, 110, 130, 170, 220
Entonces, el árbol se ve algo así:
150
/ \
100 200
/ \ / \
80 120 170 220
/ \
110 130
De acuerdo. Voy a eliminar el nodo 100. Leí en algún lugar que hay dos formas de hacer esto. Elija el sucesor en orden del nodo o el predecesor en orden del nodo. Bueno, si elijo el predecesor en orden, el árbol se verá así:
150
/ \
80 200
\ / \
120 170 220
/ \
110 130
En este caso, el recorrido posterior del árbol es:
110, 130, 120, 80, 170, 220, 200, 150
Y esto es cierto.
Pero la segunda forma en la que estoy atascado es eligiendo el sucesor en orden. En este caso, tenemos:
150
/ \
110 200
/ \ / \
80 120 170 220
\
130
En este caso, el recorrido posterior del árbol es:
80, 130, 120, 110, 170, 220, 200, 150
Y parece ser cierto, pero en el libro escribieron que no es cierto. He buscado demasiado en Google, pero en todas partes escriben diferentes enfoques para hacer esto. Tal vez todos los enfoques sean correctos, pero no lo entendí. ¿Alguien puede explicarlo en pocas palabras?
No estoy buscando código de programación. Solo quiero saber qué debo hacer exactamente.
Se agradece cualquier ayuda.
davy.ai
Cuando se trata de eliminar un nodo en un árbol de búsqueda binaria que tiene tanto hijos izquierdos como derechos, en realidad hay dos formas de abordarlo, ya sea mediante el uso del predecesor en orden o del sucesor en orden.
Usar el predecesor en orden significa encontrar el valor máximo en el subárbol izquierdo del nodo y hacer que ese nodo sea la nueva raíz del subárbol. En el ejemplo dado, el valor máximo en el subárbol izquierdo del nodo 100 es 80, por lo que se convierte en la nueva raíz de ese subárbol. El recorrido en orden del árbol resultante coincide con la salida esperada.
Por otro lado, usar el sucesor en orden significa encontrar el valor mínimo en el subárbol derecho del nodo y hacer que ese nodo sea la nueva raíz del subárbol. En el ejemplo dado, el valor mínimo en el subárbol derecho del nodo 100 es 110, por lo que se convierte en la nueva raíz de ese subárbol. Sin embargo, el árbol resultante no coincide con la salida esperada, y probablemente se deba al hecho de que el proceso de reemplazo del nodo 100 por el nodo 110 no está completo. Para que el árbol esté correctamente balanceado y cumpla con los requisitos de un árbol de búsqueda binaria, el subárbol izquierdo del nodo 110 debería consistir en los nodos previamente en el subárbol izquierdo del nodo 100 (es decir, 80 y 120), y el subárbol derecho del nodo 110 debería consistir en los nodos previamente en el subárbol derecho del nodo 100 (es decir, 110, 130, 170 y 220).
Entonces, en resumen, al eliminar un nodo en un árbol de búsqueda binaria que tiene tanto hijos izquierdos como derechos, uno puede usar tanto el predecesor en orden como el método del sucesor en orden, pero es importante asegurarse de que el árbol resultante esté correctamente balanceado y aún cumpla con los requisitos de un árbol de búsqueda binaria.