Arbres binaires

Résolu/Fermé
k-23 Messages postés 252 Date d'inscription mardi 4 mars 2008 Statut Membre Dernière intervention 25 novembre 2014 - 15 avril 2008 à 20:42
mamiemando Messages postés 32123 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 7 février 2023 - 16 avril 2008 à 10:23
Bonjour,

un arbres binaire de recherche A contient n nombres on dit que la taille de A est n

je voudrais savoir quel est le nombre maximum de comparaison qu'une insertion d,un nombre dans un arbres binaires de recherche n peut faire?

on me dit qu'il y a une formule je la trouve pas

1 réponse

mamiemando Messages postés 32123 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 7 février 2023 7 542
16 avril 2008 à 10:23
Si c'est un arbre équilibre (arbre rouge noir par exemple) c'est du O(log(n))
https://en.wikipedia.org/wiki/Red-black_tree

Preuve "intuitive" : l'arbre est équilibré et à chaque branchement chaque individu est séparé en deux groupes de même taille (à 1 près). La hauteur de l'arbre est donc vérifie donc 2^h = n, soit h = log(n)/log(2). Comme il y a autant d'évaluation que d'étage dans l'arbre (soit h), la complexité est bien du O(log(n))

Bonne chance
0