Arbre binaire de recherche

Algo 09

Résumé

Un arbre binaire de recherche est un arbre binaire auquel on impose une contrainte pour chaque nœud:

  • les valeurs du sous-arbre gauche sont plus petites que celle du nœud,
  • les valeurs du sous-arbre droit sont plus grandes que celle du nœud.
À retenir

Dans un arbre binaire de recherche équilibré, la complexité temporelle de l’algorithme de recherche est logarithmique

def rechercher(val: int, abr: list, i_pere: int) -> bool:
    if abr[i_pere] == 0: # non trouvé
        return False
    elif abr[i_pere] == val: # trouvé
        return True
    elif val < abr[i_pere]: # gauche
        return rechercher(val, abr, 2*i_pere+1)
    else: # droit
        return rechercher(val, abr, 2*i_pere+2)