En el ejericicio de 8086, en la parte 2, quisiera entender bien el cálculo de stack.
No entiendo del todo porque es que el máximo consumo del stack no se cuando el árbol degenera en una lista, quedando asi n+1 llamadas recursivas. Entiendo que el máximo consumo se da en el peor caso cuando el árbol degenera en una lista.
Porque es que queda en función de log_2 ?
Estimada,
El tema es que el consumo máximo tenés que realizarlo en función de algo. Típicamente se realiza en función de la cantidad de nodos, y típicamente, lo que ocurre es que en el caso extremo, N = cantidad de nodos = altura del árbol. Este caso era un poco más complejo, porque por construccion, sin importar las estrucutra del árbol, un árbol de altura H ocupa 2^H nodos en memoria. Para ver esto hay que hacerse un dibujito, quizás, pero sale de esta frase:
En la representación propuesta, el nodo con índice i en el arreglo 'arbol' tiene sus hijos en los bytes con
índices 2i + 1 (para el hijo izquierdo) y 2i + 2 (para el hijo derecho). A su vez, el arreglo 'mapaDeBits'
indica en el bit i-ésimo si la entrada correspondiente del árbol es válida.
Tomando esto en cuenta, para N nodos (MAX_LARGO), la altura es techo( log_2(N) ), y de ahí el cálculo.
Saludos,
Federico
Federico, sigo sin entender una cosa, como es que la altura no depende de la estructura del árbol.
Te adjunto un dibujo, donde para 2 árboles de 3 nodos, me cambia la distribución del árbol y por ende el tamaño en memoria.
"la altura del árbol se calcula como ceil( log_2( MAX_LARGO ) )."
No entiendo como la altura depende solo de la cantidad de nodos y no de la distribución.
Claro, lo que quiero decir, es que a efectos de la memoria utilizada, el árbol de la izquierda ocupa 3 nodos (MAX_LARGO = 3), y el árbol de la derecha ocupa 4 nodos (MAX_LARGO = 4), no 3 (el arreglo de la posición 3 no se usa, pero consume memoria). Entonces, la altura del árbol de la izquierda es ceil( log_2( 3 + 1 ) ) = 2, y el de la derecha es ceil(log_2(4 + 1)) = 3 **
Después, habría que considerar que MAX_LARGO tiene que ser múltiplo de 8 para que el mapa de bits tenga sentido, pero eso no afecta a la explicación de arriba.
Saludos!
Federico
** haciendo estas cuentitas acabo de ver que falta un + 1, la cuenta correcta es ceil( log_2(MAX_LARGO + 1) )
Entonces MAX_LARGO no es la máxima cantidad de nodos, sino mas bien seria aquel árbol que ocupe mayor cantidad de memoria posible para una cantidad de nodos.
En el caso del ejemplo, para un árbol con 3 nodos una distribución dio MAX_LARGO = 3 y otra distribución MAX_LARGO=4.
Entonces con ese criterio, no deberíamos de hallar que tipo/forma de árbol es el que da mayor consumo de memoria para misma cantidad de nodos?
Ya lo logré entender bien! Muchas gracias por la ayuda!!!!
Buenas,
No logro entender porque para obtener arbol[indice], se multiplica por dos el indice antes de acceder al segmento de memoria en donde esta el arreglo (la porción de codigo abajo del comentario //suma de árbol)
Gracias
Santiago,
Se multiplica por 2 el índice porque el arreglo arbol es de enteros (de 2 bytes cada uno). Entonces al índice 0 le corresponden las direcciones arbol y arbol+1, al índice 1 las direcciones arbol+2 y arbol+3, y así sucesivamente.
Es decir que al índice i le corresponden las direcciones arbol + i*2 y arbol + i*2+1. Fijate que la suma ADD AX, DS:[SI + BX] se hace sobre palabras de 16 bits (2 bytes).
Saludos,
Gustavo
Claro, entendí, muchas gracias
Saludos