Arbres binaires

Résolu/Fermé
Signaler
Messages postés
252
Date d'inscription
mardi 4 mars 2008
Statut
Membre
Dernière intervention
25 novembre 2014
-
Messages postés
30503
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
13 janvier 2022
-
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

Messages postés
30503
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
13 janvier 2022
7 266
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