Curso 2023/2024
Añadimos en cada nodo un
atributo tallaIzquierdo
para saber la cantidad
de nodos de su subárbol izquierdo (valdrá 0 si el subárbol
izquierdo está vacío).
class Conjunto { struct Nodo { int dato; int tallaIzquierdo; // <------ MODIFICACION ...
Lo inicializamos a cero en el constructor de Nodo
:
Conjunto::Nodo::Nodo(int elDato) : dato{elDato}, tallaIzquierdo{0}, // <------ MODIFICACION izquierdo{nullptr}, derecho{nullptr} { }
Al insertar, sumamos 1 a cada nodo por el que pasamos si la
inserción se realiza en su subárbol izquierdo. Para ello,
hacemos que el método insertar
recursivo
devuelva un booleano que indique si la inserción se ha
realizado (es decir, el dato no estaba ya en el árbol,
puesto que no insertamos duplicados). Observa que todas las
llamadas al método recursivo devuelven el booleano:
bool Conjunto::insertar(int unDato, Nodo * & n) { // <------ MODIFICACION if (n == nullptr) { n = new Nodo(unDato); return true; // <------ MODIFICACION } else if (unDato < n->dato) if (insertar(unDato, n->izquierdo)) { // <------ MODIFICACION n->tallaIzquierdo++; // <------ MODIFICACION return true; // <------ MODIFICACION } else // <------ MODIFICACION return false; // <------ MODIFICACION else if (unDato > n->dato) return insertar(unDato, n->derecho); // <------ MODIFICACION else // No insertamos duplicados return false; // <------ MODIFICACION }
Al eliminar, restamos 1 a cada nodo por el que pasamos si la
eliminación se realiza en su subárbol izquierdo. Para ello,
hacemos que el método eliminar
recursivo
devuelva un booleano que indique si la eliminación se ha
realizado (es decir, el dato estaba en el árbol). Observa
que todas las llamadas al método recursivo devuelven el
booleano:
bool Conjunto::eliminar(int unDato, Nodo * & n) { // <------ MODIFICACION if (n == nullptr) return false; // <------ MODIFICACION else if (unDato < n->dato) if (eliminar(unDato, n->izquierdo)) { // <------ MODIFICACION n->tallaIzquierdo--; // <------ MODIFICACION return true; // <------ MODIFICACION } else // <------ MODIFICACION return false; // <------ MODIFICACION else if (unDato > n->dato) return eliminar(unDato, n->derecho); // <------ MODIFICACION else if (n->izquierdo != nullptr && n->derecho != nullptr) { n->dato = minimoEnSubarbol(n->derecho); return eliminar(n->dato, n->derecho); // <------ MODIFICACION } else { Nodo * basura = n; if (n->izquierdo != nullptr) n = n->izquierdo; else n = n->derecho; delete basura; return true; // <------ MODIFICACION } }
Teniendo el atributo tallaIzquierdo
actualizado
en todos los nodos, lo utilizamos para encontrar
recursivamente y eficientemente el
k-ésimo menor elemento:
int Conjunto::buscarKesimo(int k) const { if (k < 0) throw string("Usando buscarKesimo con un valor de k que no existe"); return buscarKesimo(k, raiz); } int Conjunto::buscarKesimo(int k, Nodo * n) const { if (n == nullptr) // Si tenemos laTalla, esto se podria sustituir por // comprobar que k < laTalla en el metodo anterior throw string("Usando buscarKesimo con un valor de k que no existe"); else if (k < n->tallaIzquierdo) return buscarKesimo(k, n->izquierdo); else if (k > n->tallaIzquierdo) return buscarKesimo(k - (n->tallaIzquierdo + 1), n->derecho); else return n->dato; }
En la solución anterior, la siguiente implementación
de insertar
sería incorrecta, porque no se
propaga el resultado booleano de las llamadas recursivas en
todos los casos:
bool Conjunto::insertar(int unDato, Nodo * & n) { if (n == nullptr) { n = new Nodo(unDato); return true; } else if (unDato < n->dato) { if (insertar(unDato, n->izquierdo)) { n->tallaIzquierdo++; return true; } } else if (unDato > n->dato) insertar(unDato, n->derecho); else // No insertamos duplicados return false; }
Alternativamente, en los métodos insertar
y eliminar
se puede utilizar un argumento
booleano por referencia para saber si la inserción y la
eliminación se han realizado. El resto de modificaciones
coincidirían con las de la solución 1.
void Conjunto::insertar(int unDato) { bool insertado = true; // <------ MODIFICACION insertar(unDato, raiz, insertado); // <------ MODIFICACION } void Conjunto::insertar(int unDato, Nodo * & n, bool & insertado) { // <------ MODIFICACION if (n == nullptr) n = new Nodo(unDato); else if (unDato < n->dato) { insertar(unDato, n->izquierdo, insertado); // <------ MODIFICACION if (insertado) // <------ MODIFICACION n->tallaIzquierdo++; // <------ MODIFICACION } else if (unDato > n->dato) insertar(unDato, n->derecho, insertado); // <------ MODIFICACION else // No insertamos duplicados insertado = false; // <------ MODIFICACION }
void Conjunto::eliminar(int unDato) { bool eliminado = true; // <------ MODIFICACION eliminar(unDato, raiz, eliminado); // <------ MODIFICACION } void Conjunto::eliminar(int unDato, Nodo * & n, bool & eliminado) { // <------ MODIFICACION if (n == nullptr) eliminado = false; else if (unDato < n->dato) { eliminar(unDato, n->izquierdo, eliminado); // <------ MODIFICACION if (eliminado) // <------ MODIFICACION n->tallaIzquierdo--; // <------ MODIFICACION } else if (unDato > n->dato) eliminar(unDato, n->derecho, eliminado); // <------ MODIFICACION else if (n->izquierdo != nullptr && n->derecho != nullptr) { n->dato = minimoEnSubarbol(n->derecho); eliminar(n->dato, n->derecho, eliminado); // <------ MODIFICACION } else { Nodo * basura = n; if (n->izquierdo != nullptr) n = n->izquierdo; else n = n->derecho; delete basura; } }
buscarKesimo
no recursivo)
El método buscarKesimo
de cualquiera de las
soluciones anteriores se puede sustituir por el siguiente,
en el que se hace el mismo cálculo de forma no recursiva:
int Conjunto::buscarKesimo(int k) const { if (k < 0) throw string("Usando buscarKesimo con un valor de k que no existe"); Nodo * n = raiz; while (n != nullptr) if (k < n->tallaIzquierdo) n = n->izquierdo; else if (k > n->tallaIzquierdo) { k -= (n->tallaIzquierdo + 1); n = n->derecho; } else return n->dato; // Si tenemos laTalla, lo siguiente se podria hacer al principio si k >= laTalla throw string("Usando buscarKesimo con un valor de k que no existe"); }
int Conjunto::buscarKesimo(int k) const { if (k < 0) throw string("Usando buscarKesimo con un valor de k que no existe"); Nodo * n = raiz; while (n != nullptr) if (k < n->tallaIzquierdo) n = n->izquierdo; else if (k > n->tallaIzquierdo) { n = n->derecho; k -= (n->tallaIzquierdo + 1); } else return n->dato; // Si tenemos laTalla, lo siguiente se podria hacer al principio si k >= laTalla throw string("Usando buscarKesimo con un valor de k que no existe"); }
Este código funciona incorrectamente por intentar acceder
a n->tallaIzquierdo
después de haber
cambiado n
con n = n->derecho
.