Naviguer dans le tableau

Exercice · OCaml (option informatique), chapitre 19 — Files de priorité : le tas binaire

Énoncé

Donner les indices du parent, du fils gauche et du fils droit du nœud 4. Dessiner l'arbre du tableau [| 1; 3; 2; 7; 5 |] et vérifier que c'est un tas.

Corrigé

Parent de 4 : (4-1)/2 = 1 ; fils gauche : 2*4+1 = 9 ; fils droit : 10. Pour [|1;3;2;7;5|] : racine 1, enfants 3 et 2 ; enfants de 3 (indice 1) : 7 et 5. Chaque nœud est $\leq$ ses enfants ( $1 \leq 3, 2$ ; $3 \leq 7, 5$ ) : c'est bien un tas, de minimum 1.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.