Volem fer una classe BST_Augmented tal
que a cada node (instància de _Node) del
BST es guardi la mida del subarbre del que aquest node és arrel. Si el
node és una fulla, aquesta mida és 1, ja que l’arrel s’inclou en aquest
comptatge. En un node qualsevol, aquest nombre és 1 més la mida del fill
esquerre més la mida del fill dret. És el concepte de mida
d’arbre que tots ja coneixem.
A més, les instàncies d’aquests
BST_Augmented només creixeran, no caldrà
considerar l’eliminació d’elements. Així, en lloc de fer una subclasse
de BST, definirem la classe
BST_Augmented de nou (inspirant-nos, això
sí, en la classe BST que ja coneixem), on
afegirem una variable d’instància _size a
la classe interna _Node, i només
modificarem els mètodes afegeix i
_afegeix (hem tret els mètodes relacionats
amb l’eliminació d’elements, i altres que no serveixen en aquest
exercici). El mètode _inordre també ha
patit una molt lleugera modificació. Vegeu el fitxer
code.py.
L’únic que queda pendent en el fitxer
code.py per acabar d’implementar la classe
BST_Augmented és adaptar el mètode
_afegeix als canvis que hem fet. És a dir,
el mètode _afegeix haurà de tenir en
compte que afegir un node canvia la mida de cada instància de
_Node present en el camí de l’arrel del
BST fins al lloc on hem afegit la nova instància de
_Node.
La resta del codi que hi ha a code.py
no s’ha de tocar!!. Ja està bé com està.
Així, resumint, l’exercici consisteix en adaptar el mètode
_afegeix de la classe
BST_Augmented als canvis especificats més
amunt, dins el fitxer code.py.
Entrada
L’entrada al programa serà: un nombre n i una llista
d’n nombres enters diferents amb els que construirem el
BST_Augmented.
Vegeu els exemples del joc de proves públic.
Sortida
La sortida són una llista de parelles
(valor node, mida subarbre) ordenada segons el valor de
cada node. Això és el resultat d’invocar el mètode
elements, que ja està fet, com podeu veure
al fitxer code.py.
Vegeu els exemples del joc de proves públic.
Observacions
Heu de baixar-vos el fitxer code.py
(icona de la serp). Aquest fitxer és un programa amb
tot el que cal per executar els jocs de prova públics.
Només falta, clar, que modifiqueu el mètode que demana l’enunciat.
Aquest fitxer l’heu de completar amb el vostre codi, i això,
tot, és el que heu d’enviar al Jutge com a solució.
L’eficiència i la qualitat de la solució es tindran en compte a la correcció manual.
Autoria: Jordi Delgado
Generació: 2026-06-27T11:59:33.473Z
© Jutge.org, 2006–2026.
https://jutge.org