Aller au contenu

Arbre binaire de recherche (2 classes)

graph TB;
    A((8))-->B((3))
    A-->C((10))
    B-->D((1))
    B-->E((6))
    C-->F((9))
    C-->G((14))
    E-->H((4))
    E-->I((7))

On donne une partie de la classe ABR pour implémenter les Arbres Binaires de Recherche sans doublon : un ensemble fini de nœuds, éventuellement vide, organisés de manière hiérarchique. C'est une arborescence d'éléments comparables.

Un ABR est une structure de nature récursive :

  • Soit c'est un ABR vide,
  • Soit il possède une valeur et a deux enfants qui sont aussi des ABRs.
    Dans ce dernier cas, il existe une contrainte concernant les valeurs présentes dans les sous-arbres gauche et droit, par rapport à la valeur en cours :
    • Toutes les valeurs présentes dans le sous-arbre gauche sont inférieures à la valeur en cours.
    • Toutes les valeurs présentes dans le sous-arbre droit sont supérieures à la valeur en cours.

On considérera ici des ABRs sans doublons : il ne sera pas possible d'y insérer plusieurs fois la même valeur.


Choix d'implémentation⚓︎

Dans cet exercice on choisit d'implémenter les ABR à l'aide de deux classes :

Attributs⚓︎

class ABR:
    racine: None|Noeud

class Noeud:
    element: Comparable
    gauche: ABR
    droit: ABR


  • L'ABR vide est une instance de la classe ABR où l'attribut racine prend la valeur None.
  • Un ABR non vide est une instance de la classe ABR avec une instance de Noeud en racine.
    C'est l'instance de Noeud qui porte la valeur et les enfant gauche et droit :
    • gauche : le sous-ABR à gauche
    • element : un élément comparable aux autres (des entiers, des chaînes de caractères, ...)
    • droit : le sous-ABR à droit

Constructeurs⚓︎

  • Les objets ABR sont créés vides avec ABR().

  • Les objets Noeud sont créés avec une valeur et deux sous-ABR vides: Noeud(ABR(), element, ABR()).

Contrats & Méthodes⚓︎

  • Les objets ABR peuvent être mutés pour ajouter de nouvelles valeurs à la structure.

  • Les objets Noeud n'ont pas de méthodes implémentées.

  • Les objets ABR ont, ou devront, implémenter les méthodes suivantes :

    • abr.est_vide() -> bool, qui indique si l'ABR contient des valeurs ou non.
    • abr.insere(v) -> None, qui permet d'ajouter la valeur v à un emplacement approprié dans l'ABR en cours.
    • abr.contient(v) -> bool, qui permet de savoir si l'ABR en cours contient la valeur v ou pas.
    • abr.infixe() -> str, qui renvoie une chaîne de caractères représentant le contenu de l'ABR, traversé en mode infixe.


Conséquences

Ce choix d'implémentation à deux classes permet d'utiliser le cas de base "arbre vide", dans les implémentations récursives.

Il présente cependant un léger désavantage concernant l'impact sur la mémoire, car pour stocker une valeur, il faut systématiquement deux objets (+ tous les arbres vides des feuilles de l'ABR).


Exemples
>>> nombres = ABR()
>>> nombres.est_vide()
True


>>> for x in [3, 7,  9, 1, 9]:
...     nombres.insere(x)
>>> nombres.est_vide()
False
>>> nombres.contient(7)
True
>>> nombres.contient(8)
False
>>> nombres.infixe()
'|1|3|7|9|'


>>> panier = ["kiwi", "pomme", "abricot", "mangue", "poire"]
>>> fruits_ranges = ABR()
>>> for fruit in panier:
...     fruits_ranges.insere(fruit)
>>> fruits_ranges.contient("pomme")
True
>>> fruits_ranges.contient("cerise")
False
>>> fruits_ranges.infixe()
'|abricot|kiwi|mangue|poire|pomme|'

Implémentation⚓︎

Compléter les méthodes de la classe ABR ci-dessous, en prenant soin de respecter la complexité en temps attendue pour la méthode contient.

Quelques remarques concernant les tests :

  • Dans les tests, la fonction insere_abr(lst, abr) ajoute toutes les valeurs de la liste lst dans abr, en utilisant sa méthode abr.insere(element), dans l'ordre des valeurs dans lst.

  • Durant les tests, le dernier ABR construit est systématiquement affiché dans la zone ci-dessous (il est conseillé de travailler en mode "2 colonnes". Les arbres des tests de performances ne sont pas affichés).

  • Une fois que toutes les méthodes sont implantées et renvoient des réponses correctes, la complexité en temps de la méthode abr.contient(element) est testée, pour vérifier qu'elle respecte les spécifications attendues pour un ABR. Ces tests peuvent être relativement long...


Fonctions ou méthodes avec types

Python n'est pas un langage à typage fort, mais il est possible de renseigner les types des données manipulées, à titre informatif.

Ils sont intéressants notamment dans les signatures de fonctions ou de méthodes, pour rappeler succinctement quels sont les types des données attendus en arguments, ainsi que le type de ce que la fonction renvoie.

Les deux signatures suivantes sont strictement équivalentes, la seconde ajoutant les informations de typage :

🐍 Script Python
def compteur(lst):
    ...

def compteur_avec_type(lst: list[int]) -> dict[int,int] :
    ...
  • lst: list[int] indique que l'argument lst est une liste python d'entiers.
  • La flèche après les parenthèses définissant les arguments, ->, permet d'indiquer le type des données renvoyées par la fonction. Ici, il s'agit de dict[int,int], soit un dictionnaire avec des entiers en clés et en valeurs.


Il peut aussi arriver que l'on trouve des signatures avec None en type de renvoi :

🐍 Script Python
def mélange_liste(lst: list) -> None:
    ...
⚠ Cette annotation -> None indique en fait que la fonction ne renvoie rien.
Comme son nom le suggère, cette fonction a à priori pour but de mélanger une liste en place, par mutation. Elle ne comporte donc pas de return.


Dernier ABR créé:

Votre tracé sera ici

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.128013oé{3IpRaA7gq 6U!/09yeBmit=ld.k2v:1b,N}cu)hx58nà4_|f;rSwzTF(-sP050C0v0z0i0y0B0-0n0N0B0i0-0-0A010z0y0g010406050-0O0x0x0i0#0u040$0b0B0O120b0U050r191b1d1f170g04051v1o1y0r1v170C0y0G0`0|0~100Q0y0l0Q0B1M0Q0z15050=0J0B0v1H0}0 011L1N1P1N0z1V1X1T0z0#1w0z0Q0`1i0-0g0i0U100F011Z1J010Z0@0v0U0i0x0v1T1_1{201#231X2628150a0n0.0#0b0g0b0-0y1l0U0n0:1@0#0#0v0N2t1o2b0U1w0r1=2G1/1;1:1U0C2d101P0U252q1T1E1G0{1!2Q0y2S0U0b2W1T0g2z1w2E2G2.181`2u2Y212%0#1c0B150n0I2D2=162;2c2@1#2_2{2}0F301{322E2P01370i2|040n0e3b2F173e35103h3j0n0W3n3d2=3f3t2}0S3x3p3z3r3g0b2`3i2}0o3E332?1I363J383k0k3O3q3R3s3T3L3k0T3X3G3Z3I3K3u0t3)343+3B040I0s3:3Q2Z3,3U0I2 1p313F3;3|3?0I3a413c433{2^3#3j0I3m493o3P3A4e150I3w4i3y444d3-4n3D4q4b4l4u3@3N4x4k3H463W4D3Y454m3@3(4I3*4K4A0I3/4O4s3S4A0F3_4U4c4W3U0F402.4y4F4L0F484*4E3=4-4h4:4J4t4%4p4^4P4`3$0F4w4}4V3!4X4C534#554%4H584z4%4N5d4,4X4T5h4=4A0e4Z5l4Q3U0e4)424;5r3$0e4/5v4_4$5y4@5B4~5D3j0e4|5G543}5y525M595O5J575R5e5y5c5W5i5s5g5!5m5s5k5(5x3j0W5p5,4 5.5u4a5w5=150W5A5^5C5a3$0W5F5~5H605.5L645N3?0W5Q695S6b5V6e5X5.5Z6i5#615%6m5)615+3c1z2,1o2W2J0C1;2O3H0N2(291w6y1x6w2:4q056E0:2-65010E15353x5_1#0%2}6W5 3g0N150L0b0v0O0C6#6R14040H3E060n6_0n6X106T040:0Z6/5N6Z3k725S0Z0x150X0X2#2s7b763f6;0+7g3H0J6;0-0v0B716M6$6;0K3x6{6$0U150l0i0O0N0Q0v7k3+7u7w6|3g157p0v280U0z7H3|7J4q7x6R7z6 2n2s7T216;0P6?4x6`7-7X5N7m157o7q7%1#0b150D7^3s7A7C7E7G7W7L7`040A7K7y7 7D7F3E7.6`7L7;047?7r2:6$857|7s7Y7N1X7Q7S838m15878v8q047O8t8d8e7/5S8h8j7}018n8K7Z0C7#8u2.8G3f858y8S7L8O8Q6@4+3+6~6V8p736!8*6f6(040j0w0h8K6;7+4*6^8f6$6~708K746{8-3f787a7c0U7e0X8@157j937l7n7p8k317L7)8_428F8T9f7=9h8K8M9e3=150#0i0N2#828X8w86886R0E8/6*2S8#7-7L8~0v9i6u6$918N0Z7N0-0z0X0G0y0:9b049d8l6R8I9s9v7U150P9G5N850,020l0z0!9?6f0J150J0b1i9(9m4a9o9O9x0;0O0#1n8z7:9g7@9/219u9+6a9x9z9B9~8U740y0-ar3H9I6)1m9C42068{6_a96 9Q908,am6f9W042#7o2z9(9*9j6$9-aiaL7h157vaf6f8r7P258RaU6:9;aw3+9^9`9|a/3|ay049KaB9Sa-6=8E8eaG0y9R2F9p3+aWb46Q9@7{8N9X9Z9#9%aj1#7i7*b09ob63|b89tbcbi7~049y9A9La$8U8xa@2^az6,6.bt017ibd8:8=aS0Pa#9D8A8Ca*9(bP31bobDbL8?bHbk9=7,8FaG7pb3bC36a(8Dbz3H85020Ba?b;b7ahb984bsaY4Faobxa|2Fb~048oc09w8B8sbTb`9:a b(bnbX1#bqbHala,anbvapbyc93|cna}cp7B8bc4ba5Scvc589aO0UaQcA9k9cbKbS7R9(b%4*a88}8rb,ce21clctakb coa%cqc3brc7cMcccOcW7_15b@b_bQcpcNa+3ccj108^bmcS9,b|c*c8c$3Ac2aqcmc#cwc%8P0b7$d9c+bH7ZaP0vaRb#cLdib/cdcZbja.ch7.b*0^cJ7t15a63ociaFcT041`0~b-100N0I15030n6*0z0v0(0n0m0O02030e0t0!0@0n0UdYd!0!0u0n0i0n0#0y250n0V0n0Z0?2z0n0y9A0`1d0n1X0_0C0b0O1W1m0_0-1m0zd}0l2_0c0_0q9M8|9H158 bH9UdiaN6E7Rd=c.dsc}doex01cYd53H7Vc@c%c_cPdK8L159_9{9}c/3sa004a2a4dncgcRb)dGcVeG3feCdbbAdheA7Z0v9Y9!9$dza~0+bldvd05N6~2z0zacaee$ax8/0*3i7oc ele{cUb9c|7Mcba)ewbWc6c=ePf1b{9raXeDa:dacE8Abwd8eAcDcBd6feb:flcfdC16dEfce|abadeKe(fsbbe+fp45d7csfQc!fPe)c104cy81d3bKet12drfUdt9)c,ffc`fN5S7)f7dFemcbe#fhaVd2dgd4fXcafufTg1cufrfyfYeIeQeL04fjeKe-c-f:75dAeX9ndEaGe}e fLf~fwg78YfSe=fOg0f;fzdddfgtfWgAfYf(evgicKf-dpfAf*g57(dueYb1dG7pf6eWfEaEbngofJf0f|9H8/0)0#0OcAdw6$dMdO0n0f9A0K0n8j0Dg30v0Dc_0n0G7Cedh1ej4xaD9NdGeoeAeqe,aN2#230Rgxf=ezf+10fMg87IgSg)fOeNc?ht9 7=1/a5f@fH15f{c{8ggshngcgzhqfR8Be/bghkaZ9)e^gTg#dGgpfKgb0-1~gddW0b9|0Y02h(hw4ag!ha8A0ieK8Vgrfnb}9EhLgvc(fvhJfxh~f!8cf bKhh0yhjbNhCh~0Jh@bBgbhpc6h}cFg~f$gNgahVh;cp0Nif9FihhIgQc:gFhMbYimi6gNgCgKh|i70UhihReE9ccQgmgUf_hYg(hG6$0-0i15h{6Rh#c;h-fkhJ2r150daJ75gNh?epaKi*0y150Mi-i=i/e,a1i.92eAi+04i`j0f%j6bHj30M8Ki$h%0Oh)i)a7gng;dN04dP0p121PiX2t2vd*d#0O2Sd_0,9Yd;0U0l0n0+0g1j0_0c0B0c7B7RdVg.e2d/et0N0i0z0c262tiP5^0r6O0v2G2+j%6x1F6z2J2M2H0i1Wj*0r6y17j@0;0?0^04.

Tests de performances

Votre tracé sera ici