"Generador d'arbres AVL" P86567

Recordeu que un arbre AVL és un arbre binari de cerca on, per a cada node, la diferència en valor absolut de les alçades dels seus fills és, com a molt, 1.

Escriviu una funció @all_avl_trees_of_height(h: int) -> Iterator[Tree]@ que, donat un natural $h$, generi tots els arbres binaris d’alçada $h$ que tinguin forma d’AVL. No importa en quin ordre es generin, però s’han de generar tots i sense repetits.

Descarregeu-vos el fitxer code.py que ja conté la definició dels tipus i un programa principal per llegir una seqüència d’alçades i escriure, en ordre lèxicogràfic, tots els arbres AVL d’aquella alçada. Els arbres buits s’escriuen amb un guió, i els arbres que arrelen dos subarbres $a_1$ i $a_2$ s’escriuen amb $a_1$ i $a_2$ entre parèntesis. Per inspirar-vos, el fitxer code.py també conté una funció @all_trees_of_size@ d’exemple que genera tots els arbres binaris (no necessàriament AVLs) amb $n$ nodes.

Per raons de temps i espai, el Jutge només provarà el vostre programa per $h\in[0..5]$, però el vostre programa hauria de ser correcte per a qualsevol alçada. Per referència, hi ha 108675 arbres AVL d’alçada 5. Es demana que el generador sigui eficient, tenint en compte que el nombre d’arbres binaris és molt superior al nombre d’AVLs quan l’alçada és gran.

Només podeu modificar el codi de la funció requerida, sense canviar-ne la seva capçalera. Heu de respectar els tipus de dades donats. Podeu esborrar la funció @all_trees_of_size@.