Curso 2022/2023
vector<int> Conjunto::obtenerOrdenados() const { vector<int> v(laTalla); int i = 0; obtenerOrdenados(raiz, v, i); return v; } void Conjunto::obtenerOrdenados(Nodo * n, vector<int> & v, int & i) const { if (n != nullptr) { obtenerOrdenados(n->izquierdo, v, i); v[i++] = n->dato; obtenerOrdenados(n->derecho, v, i); } }
Presta atención a estos aspectos de la solución anterior:
No utilizamos push_back
para insertar datos en el vector,
que lo que haría internamente es duplicar la capacidad del vector cada
vez que se llena. Para evitar eso, como conocemos la talla del conjunto,
le damos ese dato al constructor del vector.
El vector se crea en el primero de esos dos métodos y se devuelve
con return
una sola vez. El
segundo método no lo devuelve con return
, lo que hace es
actualizar el vector y la posición que le pasamos por referencia y que
todas las llamadas recursivas comparten.
El coste temporal de este algoritmo es O(n) debido a que se hacen O(n) llamadas recursivas y el coste propio de cada llamada es O(1).
Su coste espacial es O(n) debido a que tenemos un árbol de talla n y un vector de talla n, a lo que se suma el coste de la pila de llamadas recursivas que en el peor caso, si tuviéramos un árbol de altura n, también sería O(n).
Piensa por qué la siguiente solución es incorrecta.
vector<int> Conjunto::obtenerOrdenados() const { vector<int> v(laTalla); obtenerOrdenados(raiz, v, 0); return v; } void Conjunto::obtenerOrdenados(Nodo * n, vector<int> & v, int i) const { if (n != nullptr) { obtenerOrdenados(n->izquierdo, v, i); v[i++] = n->dato; obtenerOrdenados(n->derecho, v, i); } }
Al no pasar i
por referencia, lo que se incremente es una copia que no ven todas las llamadas.
Piensa por qué la siguiente solución es incorrecta.
vector<int> Conjunto::obtenerOrdenados() const { vector<int> v(laTalla); obtenerOrdenados(raiz, v, 0); return v; } void Conjunto::obtenerOrdenados(Nodo * n, vector<int> & v, int & i) const { if (n != nullptr) { obtenerOrdenados(n->izquierdo, v, i); v[i++] = n->dato; obtenerOrdenados(n->derecho, v, i); } }
No podemos pasar un valor constante (en este caso, 0) en un argumento por referencia.
Piensa por qué la siguiente solución es incorrecta.
vector<int> Conjunto::obtenerOrdenados() const { vector<int> v(laTalla); int i = 0; return obtenerOrdenados(raiz, v, i); } void Conjunto::obtenerOrdenados(Nodo * n, vector<int> & v, int & i) const { if (n != nullptr) { obtenerOrdenados(n->izquierdo, v, i); v[i++] = n->dato; obtenerOrdenados(n->derecho, v, i); } }
El segundo método no devuelve nada, no podemos devolver con return
lo que no devuelve.