Aller au contenu

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 None en Python.
  • Ensuite, on remplit le tableau avec un parcours en largeur de l'arbre.

🐍 Console Python
>>> # indices          0     1   2   3   4   5
>>> tas_de_nombres = [None, 10, 42, 23, 55, 67]
🐍 Console Python
>>> # 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être tableau[i // 2]
  • Si \(2i \leqslant n\), l'enfant à gauche de tableau[i] est tableau[2*i]
  • Si \(2i+1 \leqslant n\), l'enfant à droite de tableau[i] est tableau[2*i + 1].

Par exemple,

🐍 Console Python
>>> 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

🐍 Console Python
>>> 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
🐍 Console Python
>>> 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
###
# testsbksl-nlbksl-nl## exemplesbksl-nlassert estpy-undtaspy-undmin([None, 10, 42, 23, 55, 67]) == Truebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 'brrr', 'chut', 'ouille', 'dring', 'tada', 'vroum', 'wahou', 'paf', 'hehe']) == Truebksl-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-nlbksl-nl# autres testsbksl-nlbksl-nl## exemplesbksl-nlassert estpy-undtaspy-undmin([None, 110, 142, 123, 155, 167]) == Truebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 'zbrrr', 'zchut', 'zouille', 'zdring', 'ztada', 'zvroum', 'zwahou', 'zpaf', 'zhehe']) == Truebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 100.0, 100.0]) == Truebksl-nlbksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 110, 142, 123, 155, 167, 125, 123, 156, 157]) == Truebksl-nlassert estpy-undtaspy-undmin([None, 110, 142, 123, 155, 167, 125, 123, 156, 157, 168]) == Truebksl-nlbksl-nl## contre-exemplesbksl-nlassert estpy-undtaspy-undmin([None, 110, 12]) == Falsebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 'zba', 'zab']) == Falsebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 110, 142, 123, 130]) == Falsebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 110, 142, 123, 155, 140]) == Falsebksl-nlbksl-nl## lourdsbksl-nllourd = [None]bksl-nllourd.extend(range(10py-strpy-str5))bksl-nlassert estpy-undtaspy-undmin(lourd)bksl-nlbksl-nllourd = [None]bksl-nllourd.extend(range(10py-strpy-str5))bksl-nllourd[42] = 0bksl-nlassert not estpy-undtaspy-undmin(lourd)bksl-nlbksl-nl ∞/∞

def estpy-undtaspy-undmin(tableau):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nl## exemplesbksl-nlassert estpy-undtaspy-undmin([None, 10, 42, 23, 55, 67]) == Truebksl-nlbksl-nlassert estpy-undtaspy-undmin([None, 'brrr', 'chut', 'ouille', 'dring', 'tada', 'vroum', 'wahou', 'paf', 'hehe']) == Truebksl-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-nlNone

A

Z

Retour en haut de la page