Tri par tas
Bonjour,
avant de définir le tri par tas, on crée une procédure ENTASSER-MAX(A, i), qui suppose que les arbres binaires à gauche et à droite du noeud i sont déjà des tas max (la valeur d'un noeud autre que la racine est au plus égale à celle de son parent), mais qu'éventuellement A[i] est inférieur à l'un de ses enfants. Je n'arrive pas à comprendre pourquoi le pire cas se réalise lorsque la dernière rangée de l'arbre est exactement à moitié remplie.
Réponses
-
Bonjour
"Le pire des cas" est ici à comprendre comme "étant donné le nombre de noeuds d'un arbre, la plus grande taille possible du sous arbre".
Par exemple, si il y a 11 noeuds, la dernière rangée de l'arbre est remplie à moitié, et le plus grand sous-arbre possible est de taille 7 (l'arbre gauche du noeud racine en l'occurence)
FB
PS. Sans avoir le Cormen à côté, qui est probablement ta source, difficile de comprendre la question ! -
Merci. Effectivement, je lis le Cormen. Désolé pour le manque de précision.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 5
