Création d'arbre aléatoire de taille donnée

Grande utilité

Il y a de nombreuses situations où on souhaite tester un algorithme sur un grand arbre binaire.

Il est très utile de pouvoir en fabriquer un de manière aléatoire !

Exercice

Coder une fonction aléa_taille qui prend en paramètre t un entier positif et qui renvoie un arbre binaire aléatoire de taille t.

Dans cet exercice, pour chaque nœud :

La répartition des étiquettes doit être uniforme dans l'intervalle des entiers de [0..256[ ;
- prendre donc un entier au hasard dans [0..256[.
La répartition des nœuds dans les sous-arbres à droite et à gauche doit être uniforme ;
- choisir un nombre au hasard pour le partage en deux de ce qui reste après la racine : entre rien et tout à gauche, et le contraire.

Par exemple, pour un arbre de taille 10,

Il y a 1 nœud racine et 9 nœuds à répartir dans les sous-arbres.
Le sous-arbre à gauche doit avoir une chance sur 10 d'avoir une taille pour chacun des cas de 0 inclus à 9 inclus.
De même pour le sous-arbre à droite.
... De même pour chaque nœud des sous-arbres, de manière récursive.

Un arbre binaire de taille 4

graph TB
    N0("11")
    N0 --> N1("42")
    N0 --> N2("11")
    N1 --> N11(" ")
    N1 --> N12("21")
    N12 --> N121(" ")
    N12 --> N122(" ")
    N2 --> N21(" ")
    N2 --> N22(" ")

randrange du module random

Un exemple d'un tirage d'un des 10 chiffres : de 0 à 9 inclus.

🐍 Console Python

>>> from random import randrange
>>> randrange(10)
9

randrange fonctionne comme range avec 1, 2 ou 3 paramètres. C'est un excellent choix.
On trouve randint souvent utilisé, mais dans ce cours on recommande randrange. D'ailleurs, dans Python randint fait appel à randrange...

Fonction taille disponible

La fonction taille (déjà vue) est ici directement disponible. Elle vous permettra de vérifier que votre construction est bonne.

Rappel : La fonction taille prend en paramètre un arbre binaire défini à l'aide de la classe Noeud et renvoie la taille de l'arbre : son nombre de nœuds.

Évaluations restantes : ∞/∞

.128013,59/f.q78rnb N_o=ylaepcwgu)vdV4613kRméhtsP(S0à+L2[-i:050D0v0O0u0!0t0P0n0x0t0u0P0P0r010O0!0w010406050P0A0L0L0u0k0s040S0q0t0A0_0q0l050e101214160~0w04051m1f1p0e1m0~0D0!0C0.0:0=0@0N0!0z0N0t1D0N0O0|050)0m0t0v1y0;0?011C1E1G1E0O1M1O1K0O0k1n0O0N1Q1A010f0+0v0l0u0L0v010.190P0w0u0l0@0X1K1{1}1+1S1.1O1;1?0|0a0n0Q0k0q0w0q0P0!1c0l0n0%1_0k0k0v0x2k1f220l1n0e1)2x1$1(1%1L0D240@1G0l1:2h1K1v1x0/1R2H0!2J0l0q2N1K0w2q1n2v2x2#0 1|2l2P1,2U0k130t0|0n0H2u2)0}2(232+1S2-2/2;0X2@1}2_2v2G012~0u2:040n0I322w0~352|0@383a0n0F3e342)363k2;0c3o3g3q3i370q2.392;0G3v2`2*1z2}3A2 3b0i3F3h3I3j3K3C3b0j3O3x3Q3z3B3l0d3W2{3Y3s040H0T3%3H2Q3Z3L0H2?1g2^3w3(3:3*0H313^333`3/2,3S3a0H3d403f3G3r450|0H3n493p3{443!4e3u4h424c4l3+3E4o4b3y3}3N4h1q2Z1f2N2A0D1(2F3y0x2V1@1n4D1o4B2%4z4J0%2!3X3:0J0l0|0f2e0L3o4v3Y0y2;4%3P3|4Y040k1}0D0q4$4z4-1,4*3b4,4V1,4X0|0!0L2g0k0O3o0n4(3|0|4;0l0D5d0z0v3v4p3y0J0|0%0f4~4j1S4|594_4 2}0f0|390M0u0p0)0+1O5q431S0{040R5H3r0|575v5r0@5K0B0#3.365t0n5!5N3y0P0D0|015+5X5%5)3b5!0n0K1:0C0q0!1P0A2l140m2q0n0m2S0*605A0u0O5_602n5E0t1O0n5Q2#5k3Y5(2;5;0W0v0-0M0_0h0A0(0O6o0n0P0v2e0l0O2m6w1:0_6z0-66680!2q0-2n0Y0T0g0g0X0c0G0Y5-6j5/5;0n5+013v6!5a50525p4h594`2}5P586*1S0q0|0r0r6?6:0@0L0!0|3-5R5I5T0|5W4o6!6)6~015m4:0(0A0k1e6.6@0@0J0x0|0o1d5i795;7l7d0|0v0,7s2%7c5K786h7a7u7c4/0O0p0z6}5w0@6_046|7k7I5c4=5g7A2^7v5K5M745O046g7Z7C0|0B586/7O010x0H0|036D0n0T0n0U6f0Z0H0n2S0/0A0P6(7G7:5S375P0p0D7N8a7Q7S2#89758b7)8f8l7Q0Z8o36704e8s3y8q8w3)8c7M6.5#7c7?7^0n0M0z390v1?6B7`7|7~0O80820l84867t7G7v8G047_0E0M0k0!1.6z0n6s1P7K0z0n0V2=8?6f8d0n6{6f878Z7U040C8L7h8z3:8h962,7V5e7X5$3Y7#9e3:8u046T4t7B7;5U8 7a7v4/8K0A0x0N7Y338k36987T7;4/665D0*6d9y2w7!0|7$9n8a7J7L9h1,9p8Y9r915f5_6v996^6`9$3j5z0t5B9H5F9K4U8a9g7%4w8c8e9@9f7-9q7b7;7e2q0O7h7j8j9s7p0q0v0A9`9P8l9?ad7(931O959{3:5K0b9)8m9u9w9:9M04ao9D9Q5n2e2jat7,047.4u0e4S0v2x2YaJ4C1w4E2A2D2y0u1NaM0e4D0~aW0(9I0P04.