Terminale NSI — Arbres

Séance 3 — Arbre binaire de recherche

Définition, recherche, insertion, tri par ABR · 2h

1. Définition d'un ABR

Un arbre binaire de recherche (ABR) a ses clés ordonnées : pour tout nœud x, les clés du sous-arbre gauche sont ≤ à x, celles du sous-arbre droit sont ≥.

Propriété remarquable
Le parcours infixe d'un ABR renvoie toujours les clés dans l'ordre croissant.

2. Exercice 1 — Vérifier la propriété d'ABR

Sur les arbres fournis : est-ce un ABR ? Sinon, quel nœud viole la propriété ?

3. Exercice 2 — Recherche dans un ABR

def recherche_abr(A, k):
    if A is None:
        return False
    if k == A.etiquette:
        return True
    elif k < A.etiquette:
        return recherche_abr(A.gauche, k)
    else:
        return recherche_abr(A.droit, k)

a) Recherche de 13. b) Recherche de 16 (absente). c) Version itérative. d) Complexité selon l'équilibre ?

Voir la réponse
def recherche_abr_ite(A, k):
    x = A
    while x is not None and k != x.etiquette:
        x = x.gauche if k < x.etiquette else x.droit
    return x is not None
Équilibré : O(log₂ n) (comme la dichotomie). Filiforme : O(n) (comme une liste non triée).

4. Exercice 3 — Insertion dans un ABR

def insertion_abr(A, y):
    if A is None:
        return Noeud(y)
    if y < A.etiquette:
        A.gauche = insertion_abr(A.gauche, y)
    else:
        A.droit = insertion_abr(A.droit, y)
    return A

a) Insertion de 16. b) Teste sur [10, 5, 15, 3, 7, 12, 20]. c) Adapte pour éviter les doublons.

Voir la réponse
def insertion_abr_sans_doublon(A, y):
    if A is None:
        return Noeud(y)
    if y < A.etiquette:
        A.gauche = insertion_abr_sans_doublon(A.gauche, y)
    elif y > A.etiquette:
        A.droit = insertion_abr_sans_doublon(A.droit, y)
    return A

5. Exercice 4 — Le tri par ABR

a) Complète tri_par_abr(liste). b) Teste sur [5,3,8,1,9,2,7,4,6]. c) Efficace dans tous les cas ?

Voir la réponse
def tri_par_abr(liste):
    arbre = None
    for e in liste:
        arbre = insertion_abr(arbre, e)
    resultat = []
    remplir_infixe(arbre, resultat)
    return resultat
En moyenne O(n log n), mais si la liste est déjà triée, l'arbre dégénère en peigne : O(n²).

Exercices défis (bonus)

Défi 1 — Le chasseur de minimum défi
Voir la réponse
def minimum(a):
    if a is None:
        return None
    if a.gauche is None:
        return a.etiquette
    return minimum(a.gauche)
Défi 2 — Doublons flexibles défi
Voir la réponse
def compte(x, a):
    if a is None:
        return 0
    nb = 1 if x == a.etiquette else 0
    if x < a.etiquette:
        nb += compte(x, a.gauche)
    elif x > a.etiquette:
        nb += compte(x, a.droit)
    else:
        nb += compte(x, a.gauche) + compte(x, a.droit)
    return nb
Défi 3 — Ouverture : arbres équilibrés défi

Renseigne-toi sur les arbres AVL, qui rééquilibrent l'arbre après chaque insertion.