Arbres binaires
Résolu
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
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
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
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
