Tas-Min
Définition d'un Tas
On définit un Tas-Min comme une structure arborescente de type arbre binaire, mais en plus :
- presque complet à gauche,
- telle que tous les nœuds portent des informations comparables,
- un nœud porte une information inférieure ou égale à celle de toute valeur des sous-arbres.
Ainsi, la racine (si elle existe) porte la valeur minimale du Tas. De plus, on constate qu'un sous-arbre d'un Tas-Min est un Tas-Min également, éventuellement vide.
Un exemple numérique
graph TD
R{10} --> N1{42}
R --> N2{23}
N1 --> N3{55}
N1 --> N4{67}
N2 -.-> N5( )
N2 -.-> N6( )
N3 -.-> N7( )
N3 -.-> N8( )
N4 -.-> N9( )
N4 -.-> N10( )- C'est un arbre binaire, chaque nœud possède deux sous arbres, un à gauche, un à droite qui sont des arbres binaires (éventuellement vides).
- L'arbre est presque complet à gauche : tous les niveaux sont remplis, sauf éventuellement le dernier, pour lequel les nœuds sont groupés à gauche. Dit autrement : il ne manque, éventuellement, que des nœuds à droite au dernier niveau pour obtenir un arbre binaire parfait.
- On a bien \(55 \geqslant 42 \geqslant 10\), mais aussi \(67 \geqslant 42 \geqslant 10\) et \(23 \geqslant 10\)
Avec des chaines de caractères
On peut utiliser l'ordre lexicographique (l'ordre du classement des mots).
On n'est pas obligé de dessiner les arbres Nil (les arbres vides).
graph TD
R{'brrr'} --> N1{'chut'}
R --> N2{'ouille'}
N1 --> N3{'dring'}
N1 --> N4{'tada'}
N2 --> N5{'vroum'}
N2 --> N6{'wahou'}
N3 --> N7{'paf'}
N3 --> N8{'hehe'}Avec l'ordre lexicographique, on a bien 'brrr' qui est le minimum de la structure.
Il ne manque des nœuds qu'au dernier niveau, les nœuds y sont groupés à gauche.
Modélisation d'un Tas-Min
Comme tous les arbres binaires presque complets à gauche, on peut utiliser un tableau pour modéliser un Tas-Min : celui obtenu à l'issu d'un parcours en largeur.
>>> # indices 0 1 2 3 4
>>> tas_de_nombres = [10, 42, 23, 55, 67]
>>> # indices 0 1 2 3 4 5 6 7 8
>>> tas_de_mots = ['brrr', 'chut', 'ouille', 'dring', 'tada', 'vroum', 'wahou', 'paf', 'hehe']
Avec un tas d'effectif \(n\), stocké dans un tableau de taille \(n\), les propriétés importantes avec cette modélisation sont :
- Si \(n > 0\), le nœud d'indice \(0\) est la racine. Si \(n = 0\), le tas est vide.
- Pour \(i > 0\), l'élément
tableau[i]a pour ancêtretableau[(i - 1) // 2] - Si \(2i+1 < n\), l'enfant à gauche de
tableau[i]esttableau[2*i + 1] - Si \(2i+2 < n\), l'enfant à droite de
tableau[i]esttableau[2*i + 2].
Par exemple,
>>> tas_de_mots[3]
'dring'
>>> tas_de_mots[3 // 2] # l'ancêtre de 'dring'
'chut'
>>> tas_de_mots[3*2] # l'enfant à gauche de 'dring'
'paf'
>>> tas_de_mots[3*2 + 1] # l'enfant à droite de 'dring'
'hehe'
L'objectif de l'exercice est d'écrire une fonction telle que est_tas_min(tableau) détermine, en renvoyant un booléen, si tableau modélise un Tas-Min. On garantit que tableau sera rempli de valeurs comparables.
Exercice
Coder une fonction est_tas_min qui prend en paramètre la liste issue du parcours_largeur d'un arbre binaire ab presque complet à gauche et qui renvoie un booléen : True si ab est un tas-min, False sinon.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)