Chap vii le tas

Diabolik

Sujets

• Informatique
• Marketing et communication

Informations

• Publié par: frerovic
• Nombre de lectures: 364
• Langue: Français

Extrait

Le tas

I. Définitions A. Arbrebinaire complet Arbre dans lequel chaque nœud admet deux descendants. De plus, toutes les feuilles sont au même niveauàun niveau prêt. B. Tas Un tas est un arbre binaire complet dans lequel tout nœud non terminal possède la propriétésuivante : ·Le nœud est toujours supérieuràson fils gauche etàson fils droit . . .

(*nœud).info >= max( ((*(*nœud).gauche).info, (*(*nœud).droit).info))) 12 Exemple: 7 9

7 53 8

4 64

Remarque:On décide que dans le cas oùun nœud n’ qu’un fils, c'est obligatoirement un fils gauche.

On a l’habitude de représenter un tas dans un vecteur de la manière suivante : V[1..n] V[i] >= V[2 x i]  >=V[2 x i + 1]

(Avec i >= 1 et 2i+1 <= n)

NeoXsysm & DiAboLiK er DUT info 1année

ALGORITHME

Pages 1/3