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

Question

El maestro nos explicó este algoritmo para eliminar un nodo en un árbol de búsqueda binario, pero no puedo entender cómo funciona cuando el nodo que se eliminará tiene solo un niño (ya sé cómo funciona en teoría).

algoritmo:

abc_delete(T, z) // z is the node that must be eliminated 
{
        if((z.left == NULL) && (z.right == NULL))
                y = z;
        else
                y = abr_successor(z);

        if(y.left != NULL)
                    x = y.left;
        else
                    x = y.right;

        if(x != NULL)
                x.p = y.p;

        if(y.p == NULL)
                T.root = x;
        else
        {
                if(y == (y.p).left)
                        (y.p).left = x;
                else
                        (y.p).right = x;
        }

        if(y != z)
                z.key = y.key;
        return y;
}

abr_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x == y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

Por ejemplo, quiero eliminar el número de nodo $ 7 $ :

Pero, ¿no debería el resultado final ser esto?

Answer 1

usted la opción es ciertamente correcta.

Sin embargo, tampoco hay nada de malo en el código de su maestro. Aquí hay un extracto de CLRS.

Las operaciones de inserción y eliminación causan el conjunto dinámico representado por un árbol de búsqueda binario para cambiar. La estructura de datos debe modificarse para reflejar este cambio, pero de tal manera que la propiedad de los árboles de búsqueda binaria continúe sosteniéndose.

Ciertamente preferimos que la operación se haga de la manera más fácil o la forma más rápida. Sin embargo, no hay ningún requisito que la modificación debe realizarse de la manera más fácil o incluso de ninguna manera. Tampoco requiere que la modificación se haga de la manera más rápida o incluso de cualquier manera rápida. Todo lo que requiere que la operación de eliminación debe producir otro árbol de búsqueda binario que tenga todos los nodos del árbol de búsqueda binario dado sin ese nodo específico (y no más nodos). Cómo los nodos restantes forman un árbol de búsqueda binario está completamente libre de restricciones.

El código de su maestro, por otro lado, es probablemente el código claro más corto que hace el trabajo. Cuanto más lo estudo, más ingenio encuentro.

Answer 2

Su dibujo es la solución correcta, sin embargo, su análisis a su código de maestros no es preciso (u MI intrepretó el código)

Cuando vi por primera vez que Qi no leí el código a fondo y pensé (desde la primera foto / dibujo), el maestro está realizando una operación de eliminación para un tipo especial de BST que tenga condiciones adicionales que la orden relativa, pero Este no es el caso

Al eliminar de un BST (intentar seguir las variables de código, Z es el nodo que se eliminará)

Si Z es un nodo de hoja (no hay niños), simplemente reemplace el puntero principal con NULL

Si Z tiene 1 niño (ya sea que la izquierda o la derecha no importa) haga que los Punteros de los Padres se apuntan a su único hijo

Es una codificación muy simple, en un código semi pseudo

if (z.left== null) {fishy_delete (z, zright); regreso(); // O bien, tenemos solo subárbol derecho o ninguno }

// Aquí están seguros de que hay un subárbol izquierdo

if (z. a la derecha== null) {físico_delete (z, z.left); regreso(); }

// físico_delete tiene el reemplazo como el segundo parámetro, todos los bucles en su código de maestro es averiguar qué es necesario en caso de que tengamos dos subárboles

Si Z tiene 2 hijos, entonces tienes que elegir a uno de ellos para que tome su lugar, y aquí viene el código de su maestro (no en el caso anterior)

En tu foto Imagine U r Eliminación de "5" Este código largo es para ajustar el subárbol restante de sus 2 niños (Cómo vincular 7 y 3 y sus hijos al nodo 12 Mantener el BST Requisit)

Si necesita un seguimiento detallado, podemos hacerlo, pero solo si encontró esto útil como un inicio