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 33076 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 17 avril 2024 - 16 avril 2008 à 10:23
mamiemando Messages postés 33076 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 17 avril 2024 - 16 avril 2008 à 10:23
A voir également:
- Arbres binaires
- Codes binaires - Guide
- Arbres bioluminescents - Guide
- Quel nombre des binaires de taille 5 ✓ - Forum C
- Fichiers binaires - Guide
- Les données de chaîne ou binaires seront tronquées. ✓ - Forum SQL Server
1 réponse
mamiemando
Messages postés
33076
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
17 avril 2024
7 748
16 avril 2008 à 10:23
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
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
