Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2023/2024
Añadimos en cada nodo un atributo tallaIzquierdo
con la cantidad de nodos de su subárbol izquierdo (vale 0 si
no hay subárbol izquierdo).
Para mantener ese atributo actualizado en todos los nodos, modificamos las operaciones de inserción y de eliminación como hemos hecho en el ejercicio 15 del tema 3:
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 la inserción recursiva 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).
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 la eliminación recursiva devuelva un booleano que indique si la eliminación se ha realizado (es decir, el dato estaba en el árbol).
Si tuviésemos un árbol AVL, al hacer cualquier rotación también habría que recalcular el nuevo atributo en los nodos afectados por la rotación; es fácil ver que eso puede hacerse en tiempo O(1).
El coste temporal de las operaciones de inserción y eliminación sigue siendo O(log n), puesto que el nuevo atributo solamente se actualiza en los nodos visitados por esas operaciones y la actualización cuesta O(1) en cada nodo.
La operación de búsqueda no se ve modificada.
int Conjunto::tallaEntreLimites(int a, int b) {
int resultado = contarMenores(b) - contarMenores(a);
if ( buscar(b) )
resultado++;
return resultado;
}
int Conjunto::contarMenores(int x) {
return contarMenores(raiz, x);
}
int Conjunto::contarMenores(Nodo * n, int x) {
if (n == nullptr)
return 0;
else if (x == n->dato)
return n->tallaIzquierdo;
else if (x < n->dato)
return contarMenores(n->izquierdo, x);
else
return n->tallaIzquierdo + 1 + contarMenores(n->derecho, x);
}
Aquí con un argumento más hacemos que
contarMenores sirva para contar menores (si
le pasamos 0) o para contar menores o iguales (si le
pasamos 1). Así nos ahorramos la llamada
a buscar(b) o hacer dos métodos
(contarMenores
y contarMenoresEIguales), aunque con ello el
código es más críptico y habría que documentarlo mejor.
int Conjunto::tallaEntreLimites(int a, int b) {
return contarMenores(b, 1) - contarMenores(a, 0);
// 1 para contar b si esta, 0 para no contar a si esta
}
int Conjunto::contarMenores(int x, int incluirlo) {
return contarMenores(raiz, x, incluirlo);
}
int Conjunto::contarMenores(Nodo * n, int x, int incluirlo) {
if (n == nullptr)
return 0;
else if (x == n->dato)
return n->tallaIzquierdo + incluirlo;
else if (x < n->dato)
return contarMenores(n->izquierdo, x, incluirlo);
else
return n->tallaIzquierdo + 1 + contarMenores(n->derecho, x, incluirlo);
}
El mismo cálculo se puede hacer de forma iterativa en vez de recursiva:
int Conjunto::tallaEntreLimites(int a, int b) {
return contarMenores(b, 1) - contarMenores(a, 0);
// 1 para contar b si esta, 0 para no contar a si esta
}
int Conjunto::contarMenores(int x, int incluirlo) {
int resultado = 0;
Nodo * n = raiz;
while (n != nullptr)
if (x == n->dato)
return resultado + n->tallaIzquierdo + incluirlo;
else if (x < n->dato)
n = n->izquierdo;
else {
resultado += n->tallaIzquierdo + 1;
n = n->derecho;
}
return resultado;
}
En todas las versiones anteriores, el coste temporal
de contarMenores es O(h), siendo h la
altura del árbol, puesto que en el peor caso se desciende por el árbol
siguiendo un camino desde la raíz hasta una hoja, y las operaciones que
se hacen en cada nodo visitado cuestan O(1).
El coste temporal de
tallaEntreLimites es
O(h), puesto que lo es el de los
métodos contarMenores y buscar
a los que llama.
En un árbol AVL, eso sería O(log n).
Otra solución válida consistiría en devolver
talla() - contarMenores(x) - contarMayores(y), o un cálculo equivalente a ese.