Curso 2024/2025
void Conjunto::insertar(int unDato) { Nodo * n = raiz; while (n != nullptr) { if (n->dato == unDato) return; else if (n->dato > unDato) n = n->izquierdo; else n = n->derecho; } n = new Nodo(unDato); laTalla++; }
Esta solución es incorrecta, porque al hacer n = new
Nodo(unDato)
la dirección del nuevo nodo no queda
almacenada en el atributo derecho
ni en el
atributo izquierdo
de ningún otro nodo, ni
en raiz
cuando el árbol estaba vacío. Ese bucle
solo sirve para no insertar el dato si está duplicado. Falta
enlazar el nuevo nodo en el árbol.
Si eres de los que piensan que n = new
Nodo(unDato)
sí que puede cambiar raiz
o el
atributo izquierdo
o derecho
de un
nodo porque antes se ha hecho n = raiz
, n = n->izquierdo
o n = n->derecho
, haz el mismo razonamiento con
variables enteras:
int a = 3, n = a; n = 7;
¿Estamos metiendo 7 en a
porque antes hemos
hecho n = a
? Evidentemente no. Pues lo mismo
pasa cuando n
es un puntero.
El mismo tipo de error se da en esta otra versión, en la que
solamente se ha resuelto el problema cuando hay que
modificar raiz
:
void Conjunto::insertar(int unDato) { if (raiz == nullptr) { raiz = new Nodo(unDato); laTalla++; } else { Nodo * n = raiz; while (n != nullptr) { if (unDato > n->dato) { n = n->derecho; } else if (unDato < n->dato) { n = n->izquierdo; } else return; } n = new Nodo(unDato); laTalla++; } }
Si tu solución es así, una vez entendido por qué no funciona intenta corregirla antes de seguir leyendo.
void Conjunto::insertar(int unDato) { if (raiz == nullptr) { raiz = new Nodo(unDato); laTalla++; } else { Nodo * actual = raiz; Nodo * anterior; while (actual != nullptr) { anterior = actual; if (unDato < actual->dato) actual = actual->izquierdo; else if (unDato > actual->dato) actual = actual->derecho; else return; // No insertamos duplicados } if (unDato < anterior->dato) anterior->izquierdo = new Nodo(unDato); else anterior->derecho = new Nodo(unDato); laTalla++: } }
Otro ejemplo de error sería que, por ejemplo en una solución como esta, faltase tratar el caso en que el nuevo nodo debe ser la raíz.
void Conjunto::insertar(int unDato) { if (raiz == nullptr) { raiz = new Nodo(unDato); laTalla++; } else { Nodo * actual = raiz; bool fin = false; while (! fin) if (unDato < actual->dato) if (actual->izquierdo != nullptr) actual = actual->izquierdo; else { actual->izquierdo = new Nodo(unDato); laTalla++; fin = true; } else if (unDato > actual->dato) if (actual->derecho != nullptr) actual = actual->derecho; else { actual->derecho = new Nodo(unDato); laTalla++; fin = true; } else fin = true; // No insertamos duplicados } }
También podemos separar en un método auxiliar lo que en la solución 2 se hace igual en tres casos: crear el nuevo nodo e incrementar la talla. Inténtalo y luego mira la solución siguiente.
void Conjunto::insertar(int unDato) { if (raiz == nullptr) insertar(unDato, raiz); else { Nodo * actual = raiz; bool fin = false; while (! fin) if (unDato < actual->dato) if (actual->izquierdo != nullptr) actual = actual->izquierdo; else { insertar(unDato, actual->izquierdo); fin = true; } else if (unDato > actual->dato) if (actual->derecho != nullptr) actual = actual->derecho; else { insertar(unDato, actual->derecho); fin = true; } else fin = true; // No insertamos duplicados } } void Conjunto::insertar(int unDato, Nodo * & n) { n = new Nodo(unDato); laTalla++; }
Observa que n
se pasa por referencia para modificarlo.
void Conjunto::insertar(int unDato) { insertar(unDato, raiz); } void Conjunto::insertar(int unDato, Nodo * & n) { if (n == nullptr) { n = new Nodo(unDato); laTalla++; } else { bool fin = false; while (! fin) if (unDato < n->dato) if (n->izquierdo != nullptr) n = n->izquierdo; else { n->izquierdo = new Nodo(unDato); laTalla++; fin = true; } else if (unDato > n->dato) if (n->derecho != nullptr) n = n->derecho; else { n->derecho = new Nodo(unDato); laTalla++; fin = true; } else fin = true; // No insertamos duplicados } }
Esta solución es incorrecta, porque al hacer n =
n->izquierdo
o n = n->derecho
estamos
modificando la raíz del árbol que hemos pasado por
referencia.
Observa que para resolver eso no basta quitar
el &
para que n
no se pase por
referencia: de ese modo la asignación n = new
Nodo(unDato)
no dejaría la dirección del nuevo nodo
en el atributo raiz
. Hay que hacer más cambios.
Una forma de corregir este código es convertirlo en el de la
solución 2, no estamos ganando nada con esta forma de
dividir el código en dos métodos.