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 toujours supérieure ou égale à celle de tout ancêtre.
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.
On pourrait définir un Tas-Max de manière similaire où un nœud porte une information inférieure à celle tout ancêtre.
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 de nœuds, 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.
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.
- L'élément d'indice 0 n'est pas utilisé. On utilisera
Noneen Python. - Ensuite, on remplit le tableau avec un parcours en largeur de l'arbre.
>>> # indices 0 1 2 3 4 5
>>> tas_de_nombres = [None, 10, 42, 23, 55, 67]
>>> # indices 0 1 2 3 4 5 6 7 8 9
>>> tas_de_mots = [None, 'brrr', 'chut', 'ouille', 'dring', 'tada', 'vroum', 'wahou', 'paf', 'hehe']
Avec un tas d'effectif \(n\), stocké dans un tableau de taille \(n + 1\), les propriétés importantes avec cette modélisation sont :
- Si \(n > 0\), le nœud d'indice \(1\) est la racine. Si \(n = 0\), le tas est vide.
- Pour \(i > 1\), l'élément
tableau[i]a pour ancêtretableau[i // 2] - Si \(2i \leqslant n\), l'enfant à gauche de
tableau[i]esttableau[2*i] - Si \(2i+1 \leqslant n\), l'enfant à droite de
tableau[i]esttableau[2*i + 1].
Par exemple,
>>> tas_de_mots[4]
'dring'
>>> tas_de_mots[4 // 2] # l'ancêtre de 'dring'
'chut'
>>> tas_de_mots[4*2] # l'enfant à gauche de 'dring'
'paf'
>>> tas_de_mots[4*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 débutera avec None, puis sera rempli de valeurs comparables.
Exemples et contre-exemples
>>> est_tas_min([None, 10, 42, 23, 55, 67])
True
>>> est_tas_min([None, 'brrr', 'chut', 'ouille', 'dring', 'tada', 'vroum', 'wahou', 'paf', 'hehe'])
True
>>> est_tas_min([None])
True
>>> est_tas_min([None, 10, 10])
True
>>> est_tas_min([None, 10, 2])
False
>>> est_tas_min([None, 'ba', 'ab'])
False
>>> est_tas_min([None, 10, 42, 23, 30])
False
>>> est_tas_min([None, 10, 42, 23, 55, 40])
False
def estpy-undtaspy-undmin(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl## exemplesbksl-nlassert estpy-undtaspy-undmin([None, 10, 42, 23, 55, 67]) == Truebksl-nlbksl-nlassert (bksl-nl estpy-undtaspy-undmin(bksl-nl [bksl-nl None,bksl-nl "brrr",bksl-nl "chut",bksl-nl "ouille",bksl-nl "dring",bksl-nl "tada",bksl-nl "vroum",bksl-nl "wahou",bksl-nl "paf",bksl-nl "hehe",bksl-nl ]bksl-nl )bksl-nl == Truebksl-nl)bksl-nlbksl-nlassert estpy-undtaspy-undmin([None]) == Truebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 10, 10]) == Truebksl-nlbksl-nl## contre-exemplesbksl-nlassert estpy-undtaspy-undmin([None, 10, 2]) == Falsebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, "ba", "ab"]) == Falsebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 10, 42, 23, 30]) == Falsebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 10, 42, 23, 55, 40]) == Falsebksl-nlbksl-nldef estpy-undtaspy-undmin(tableau):bksl-nl n = len(tableau) - 1bksl-nl for i in range(2, n + 1):bksl-nl if tableau[i // 2] > tableau[i]:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nl
A
\(n+1\) est bien la taille de tableau, les indices pour les éléments (hors None) sont de \(1\) à \(n\) inclus.
Les indices des éléments qui possèdent un ancêtre sont de \(2\) inclus à \(n+1\) exclu.
Il suffit juste de vérifier que chaque ancêtre n'est pas supérieur.
Z