BST Augmentat T56142

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.