Buenas estaba viendo la solucion del ejercicio 2 y me quedaron las siguientes dudas :
En la parte a proponen una demostracion por induccion, inicialmente habia intentado demostrarlo por ese
lado pero me tranque, no estaba seguro de como plantear las cosas ni que cosas debia formalizar antes.
Habia pensado hacer induccion estructural en los arboles completos, pero no sabia como formalizar todo eso bien
Por otra parte si hago induccion sobre los naturales (en i), tampoco veo como deberia plantearlo. Ademas
el arreglo tiene una cantidad finita de elementos (N) e i <= N , entonces estaria haciendo una induccion
pero para los naturales 1,2,...,N , o sea como "cortada" , como hago esto?
Respecto a la parte b no entiendo como llegaron a padre i = (i+1)/2 - 1 (asumo que la division entera redondea
"para abajo" para simplificar la notacion). Agradeceria si me pudieran decir si lo que pense esta bien o no :
Llamamos a la forma original de asignar a cada nodo una posicion en el arreglo la forma A (la raiz en el 1)
y a la otra forma , forma B. Entonces dada una posicion en forma B tenemos la siguiente biyeccion que da
la posicion en la forma A. f(i) = i + 1. Su inversa (que noto por g) es g(i) = i - 1 y dada una posicion
en la forma A devuelve la posicion en la forma B (la raiz en el 0)
Sea un nodo i en la forma B. En la forma A tenemos f(i) = 1 + i. Por parte anterior los hijos del iesimo nodo
en la forma B son en la forma :
2(i + 1) y 2(i + 1) + 1 y el padre i/2. Aplicando g tengo la posicion de los hijos del iesimo nodo de la forma A
expresado en la forma A. Entonces
hijoIzq(i) = 2(i + 1) - 1 = 2i + 1; hijoDer(i) = 2i + 2; padre(i) = i/2 - 1
En resumen estoy pensando como una traslacion o cambio de coordenadas, de la forma de colocar los
nodos de la que no conozco la expresion de los hijos/padre a una forma en la que si los conozco.
Luego calculo en esas coordenadas los padres/hijos y vuelvo a mis coordenadas originales.
Sin embargo me queda un resultado distinto al que plantean, entonces supongo que algo de mi razonamiento esta mal,
pero no me estaria dando cuenta de que es. Me podrian indicar que estoy razonando mal?
hola rafael,
a) la inducción la plantearías en i y vamos a demostrarlo, en ppio, para todo i natural (aunque sabemos que los arreglos no pueden ser infinitos). si demostramos para los naturales también vale para un subconjunto.
la idea sería plantearte un paso base (i=1) y formular hijo_izq, hijo_der, padre(hijo_izq) y padre(hijo_der) pensando en cómo quedan los primeros elementos en el vector y verificando que dichos índices se corresponden con las expresiones de la letra.
luego en el paso inductivo vamos a asumir que la formulación de hijo_izq, hijo_der, padre(hijo_izq) y padre(hijo_der) se cumplen para i=k (hipótesis); y probar que son válidas para i=k+1. para esta parte nuevamente vamos a utilizar las posiciones relativas de los padres k y k+1, y de los hijos de esos padres en el arreglo. así podremos demostrar la tesis.
b) tu razonamiento y estrategia son correctos pero te faltó considerar que el padre no es i/2 sino el mayor entero más chico que i/2.
considerando eso tu resultado para padre(i) en la forma B sería: el menor entero mayor que i/2-1. verificalo para i=0. en tu caso daría -1. por otro lado, este valor es igual a: el mayor entero menor que ( (i+1)/2 ) - 1.
espero por ahí se entienda mejor.
saludos