Re: primer parcial 2010 ejercicio 3b
Hola Juan:
Me parece que no estás entendiendo bien la solución.
el ejercicio al que te referís es
B) Implemente un procedimiento recursivo borrarMayores que dados un árbol binario de búsqueda de enteros A de tipo ABB (sin elementos repetidos) y un entero x, elimine de A todos los elementos mayores a x. El árbol resultado debe ser un árbol binario de búsqueda.
La solución propuesta consiste en una función auxiliar que borra todos los nodos de un árbol (borrarNodos) y el procedimiento borrarMayores, que recursivamente se mueve sobre el árbol parámetro decidiendo cuándo puede invocar a borrarNodos.
Cuando se llama a borrarMayores con x=5 y el árbol que aparece como ejemplo en la letra pasa lo siguiente:
1er invocación borrarMayores- se llama sobre la raiz y como 5 no es >= 8 entra al ELSE. Como es un abb sabemos que el nodo raiz debe ser borrado, pero también hay que borrar TODO el subárbol derecho (si la raiz es más grande que el valor x, todo el subárbol derecho también). Por lo tanto :
-- nos quedamos con la porción de árbol que tiene sentido recorrer (A := A^.izq;)
-- se "desengancha" el subárbol izquierdo (aBorrar^.izq := NIL;)
-- se borra TODO el subárbol cuya raíz es referenciada por aBorrar.
-- se llama borrarMayores con A (cuya raíz es el nodo con valor 3) y x=5
2da invocación borrarMayores- la raiz tiene valor 3, y como 5 >= 3 entra al IF. En ese caso sabemos que el nodo que está en la raíz DEBE conservarse en el árbol y también sabemos que no tiene sentido buscar elementos mayores a 5 en el lado izquierdo del árbol, por lo tanto se llama a borrarMayores sobre el subárbol derecho de A (cuya raíz es el nodo con valor 7).
3ra invocación borrarMayores- la raiz tiene valor 7, y como 5 no es >= 8 entra al ELSE. Como es un abb sabemos que el nodo raiz debe ser borrado, pero también hay que borrar TODO el subárbol derecho (si la raiz es más grande que el valor x, todo el subárbol derecho también). Por lo tanto volvemos a quedarnos con el subárbol izquierdo, a desenganchar el izquierdo (aBorrar^.izq := NIL;) y borramos todo lo que sabemos que es mayor (que en este caso es el subárbol vacío pero NO discriminamos este caso, la recursión lo resuelve). Luego se llama borrarMayores con A (cuya raíz es el nodo con valor 4) y x=5
4ta invocación borrarMayores- la raiz tiene valor 4, y como 5 >= 4 entra al IF. En ese caso sabemos que el nodo que está en la raíz DEBE conservarse en el árbol y también sabemos que no tiene sentido buscar elementos mayores a 5 en el lado izquierdo del árbol, por lo tanto se llama a borrarMayores sobre el subárbol derecho de A (cuya raíz es el nodo con valor 6).
5ta invocación borrarMayores- la raiz tiene el valor 6, se borra esta y todo su subárbol derecho (que es vacio) y se llama a borrarMayores sobre el izquierdo (que también es vacio)
6ta invocación borrarMayores- como el árbol es vacío el procedimiento no hace nada. Alcanzamos el caso base y se empieza a volver atrás en la recursión.
Espero que ahora quede claro
saludos
Lorena
Lorena, el ejercicio lo estabamos haciendo con juan, cuando decís que borra el nodo 7 lo desenganchás del nodo 4, es por eso que me parece que queda colgado, ya que después no queda el árbol resultante que figura en la letra del ejercicio, ya que el nodo 3, no está enganchado con el nodo 4. Espero haberme explicado lo mejor posible.
Re: primer parcial 2010 ejercicio 3b
Si no entendí mal la pregunta, en ese momento A quedaría apuntando al nodo 7.
Por lo tanto las siguientes líneas de la solución hace que el subárbol que empieza en 4 ni se borre ni quede colgado:
A := A^.izq; (* acá se dice que el árbol resultante debe apuntar al nodo 4, para que no quede colgado*)
aBorrar^.izq := NIL; (* acá se desengancha ese subárbol del árbol a liberar *)
Re: primer parcial 2010 ejercicio 3b
Claro, cuando hacés A := A^.izq y borrás el nodo 7 que es el hijo derecho del nodo 3, como hacen para conectar después el hijo derecho del nodo 3 con el nodo 4? Para mi, antes de ir de nuevo en la recursión, se debería preguntar si los hijos del 7 existen y si el izquierdo es menor, conectarlo con el hijo derecho del 3 y ahí borrás el nodo 7.