Insertion dans un ABR (3)

Dans cet exercice, on considère des arbres binaires de recherche qui sont :

• soit l’arbre vide identifié par None ;
• soit un nœud, contenant une clé et deux sous-arbres gauche et droit et représenté par un triplet (g, v, d) où g et d sont les sous-arbres gauche et droit et v la clé.

Ainsi, l’arbre binaire de recherche abr1 ci- contre est créé par le code python ci- dessous

🐍 Script Python

n0 = (None, 0, None)
n3 = (None, 3, None)
n2 = (None, 2, n3)
abr1 = (n0, 1, n2)

Écrire une fonction récursive insertion_abr(a, cle) qui prend en paramètres une clé cle et un arbre binaire de recherche a, et qui renvoie un arbre binaire de recherche dans lequel cle a été insérée. Dans le cas où cle est déjà présente dans a, la fonction renvoie l’arbre a inchangé.

Exemples

🐍 Console Python

>>> insertion_abr(abr1, 4)
((None,0,None),1,(None,2,(None,3,(None,4,None))))
>>> insertion_abr(abr1, -5)
(((None,-5,None),0,None),1,(None,2,(None,3,None)))
>>> insertion_abr(abr1, 2)
((None,0,None),1,(None,2,(None,3,None)))

Compléter le script ci-dessous

###

Lancer # Testsbksl-nlbksl-nln0 = (None, 0, None)bksl-nln3 = (None, 3, None)bksl-nln2 = (None, 2, n3)bksl-nlabr1 = (n0, 1, n2)bksl-nlbksl-nlassert insertionpy-undabr(abr1, 4) == ((None,0,None),1,(None,2,(None,3,(None,4,None))))bksl-nlassert insertionpy-undabr(abr1, -5) == (((None,-5,None),0,None),1,(None,2,(None,3,None)))bksl-nlassert insertionpy-undabr(abr1, 2) == ((None,0,None),1,(None,2,(None,3,None)))bksl-nlbksl-nl# Autres Testsbksl-nlbksl-nlabr2 = insertionpy-undabr(abr1, -5)bksl-nlassert insertionpy-undabr(abr2, -2) == (((None, -5, (None, -2, None)), 0, None), 1, (None, 2, (None, 3, None)))bksl-nlbksl-nlbksl-nl Valider 5/5 Télécharger Téléverser Recharger Sauvegarder

def insertionpy-undabr(a, cle): bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# Testsbksl-nlbksl-nln0 = (None, 0, None)bksl-nln3 = (None, 3, None)bksl-nln2 = (None, 2, n3)bksl-nlabr1 = (n0, 1, n2)bksl-nlbksl-nlassert insertionpy-undabr(abr1, 4) == ((None,0,None),1,(None,2,(None,3,(None,4,None))))bksl-nlassert insertionpy-undabr(abr1, -5) == (((None,-5,None),0,None),1,(None,2,(None,3,None)))bksl-nlassert insertionpy-undabr(abr1, 2) == ((None,0,None),1,(None,2,(None,3,None)))bksl-nlbksl-nldef insertionpy-undabr(a, cle): bksl-nl if a is None:bksl-nl return (None, cle, None)bksl-nl elif cle > a[1]:bksl-nl return (a[0], a[1], insertionpy-undabr(a[2], cle))bksl-nl elif cle < a[1]:bksl-nl return (insertionpy-undabr(a[0], cle), a[1], a[2])bksl-nl return abksl-nl bksl-nl

---

---

Aide

Réfléchir à une fonction récursive