Arbres - EngineeringPropriétés des arbres binaires pleins h = hauteur= Le nombre maximal d’ancêtres que peut avoir une des feuilles (le niveau maximal d’une feuille de l’arbre)

CSI2510 1

CSI2510 1

Arbres

• Arbres• Arbres binaires• Propriétés des arbres binaires• Traversées d’arbres• Structures de données pour arbres

CSI2510 2

Arbres

Un graphe G = (V,E) consiste en une série V deSOMMETS et une série E de liens, avec

E = {(u,v): u,v ∈V, u ≠ v}

Un arbre est un graphe connecté acyclique (sans cycles)

∃ un chemin entre chaque paire de sommets

CSI2510 2

CSI2510 3

A

B DC

G HE F

I J K

Arbres

parent

enfant

CSI2510 4

Sous-arbre

• Sous-arbre: arbreconsistant en un nœudet ses descendants

Terminologie Arbre

Racine: nœud sans parent (A)

A

B DC

G HE F

I J K

Descendants du nœud: enfants, petits-enfants, etc.

Ancêtres du nœud: parent, grand parent, grand-grand parent, etc.

Nœuds extérieurs ( ou feuilles): nœuds sans enfants (E, I, J, K, G, H, D)

Nœuds intérieurs: nœud avec au moins un enfant (A, B, C, F)

CSI2510 3

CSI2510 5

Profondeur (depth) du nœud:

Hauteur (height) de l’arbre:

A

B DC

G HE F

I J K

Distance entre deux nœuds:

Terminologie Arbre

nombre d’ancêtres (= distance à la racine)

profondeur maximale de n’importe quel nœud (ici 3)

nombre de “liens” entre eux

CSI2510 6

Le TAD Arbres (Trees)• Méthodes génériques:

size(), isEmpty(), iterator(), positions()

• Méthodes de manipulation de positions:swapElements(p,q), replaceElement(p,e)

• Méthodes de requête:isRoot(p), isInternal(p), isExternal(p)

• Méthodes assesseurs:root(), parent(p), children(p)

CSI2510 4

CSI2510 7

Traversée en pré-ordre

• Une traversée visite lesnœuds d’un arbre dans unemanière systématique

• Dans traversée en pré-ordre,un nœud est visité avant sesdescendants

• Application: imprimer undocument structuré

Algorithm preOrder(v)visit(v)for each child w of v

preorder (w)

Traversée d’arbres

7

Gagner de l’argent facile

1. Motivations 3. Références2. Méthodes

2.1 Fraude 2.2 Pyramidede Ponzi

1.1 avidité2.3 Vol d’une

banque

1

2

3

4

5 6 7

8

CSI 2510 Aut09 - Arbres

CSI2510 8

Traversée en post-ordre• Dans traversée en post-

ordre, un nœud est visitéaprès ses descendants

• Application: calcul del’espace occupé par lesfichiers dans un dossier etses sous dossiers

Algorithm postOrder(v)for each child w of v

postOrder (w)visit(v)

Traversée d’arbres

8

cs16/

homeworks/todo.txt

1Kprograms/

DDR.java10K

Stocks.java25K

h1c.doc3K

h1nc.doc2K

Robot.java20K

9

3

1

7

2 4 5 6

8

CSI 2510 Aut09 - Arbres

CSI2510 5

CSI2510 9

Arbres - Parcours en Largeur

Dans un parcours en largeur l’arbre est visité niveau parniveau en commençant par la racine

1

32

65

10

12

7 9

4

8

11

1,2,3,4,5,6,7,8,9,10,11

CSI2510 10

Arbres binaires

Les enfants de chaque nœud sont ordonnés

Chaque nœud a au plus deux enfants: [0, 1, ou 2]

Enfant droitEnfant gauche

CSI2510 6

CSI2510 11

Arbre binaire “plein”(ou “propre”)

est une feuille, ou

a deux enfants{Chaque nœud:

C’est un arbre binaire plein où toutes les feuilles sontau même niveau

Arbre binaire parfait

CSI2510 12

Arbre binaire complet

h - 1

Un arbre binaire complet de hauteur h estformé par un arbre parfait de hauteur h-1 etpar une ou plusieurs feuilles au niveau h

CSI2510 7

CSI2510 13

Arbres binaires

Dans le livre tous les arbres sont considérés pleins (ousont rendus pleins)

CSI2510 14

Arbre de décision

• Arbre binaire associé à un procédé de décision– Nœuds intérieurs : questions avec réponse « oui ou non »– Nœuds extérieurs : décisions

• Exemple: décision dans un jeu de poker

Exemples d’arbres binaires

Bonne main?

Jouer agressif? Bluffer?

Raise Call/Check All in Fold

Oui Non

Oui Non Oui Non

CSI2510 8

CSI2510 15

Expression arithmétique• Arbre binaire associé avec une expression

arithmétique– Nœuds intérieurs : operateurs– Nœuds extérieurs : opérandes

Exemples d’arbres binaires

+

××

-2

a 1

3 b

Exemple: arbre d’expressionarithmétique pourl’expression((2 × (a - 1)) + (3 × b))

CSI2510 16

Propriétés des arbres binaires pleins

• Propriétés:– e = i + 1– n = 2e - 1– h ≤ i– h ≤ (n - 1)/2– e ≤ 2h

– h ≥ log2 e– h ≥ log2 (n + 1) - 1

• Notation– n # de nœuds– e # de feuilles– i # de nœuds intérieurs– h hauteur

CSI2510 9

CSI2510 17

e = i + 1 Propriétés des arbres binaires pleins

CSI2510 18


CSI2510 10

CSI2510 19


CSI2510 20

n = 2e - 1

i=(n-1)/2

n = i + e

n = 2e - 1

e = i + 1 (prouvé juste avant) => i = e -1

aussi: i+e=n => i = n – e = n- (n+1)/2 => i = (2n -n-1)/2


CSI2510 11

CSI2510 21

h ≤ i

Ex: h=3,i=7

Ex: h=3, i=3

Il doit y avoir au moins un nœud intérieur pour chaque niveau (sauf le dernier) !


h = hauteur= Le nombre maximal d’ancêtres que peut avoirune des feuilles (le niveau maximal d’une feuille de l’arbre)

CSI2510 22

e ≤ 2hniveau i ------- Le nombre maximum de nœuds est 2i

h = 3

23 feuilles sitoutes au dernierniveau h

Autrement moins


CSI2510 12

CSI2510 23

Depuis e ≤ 2h

h ≥ log2 e

log2 e ≤ log2 2h

log2 e ≤ h

log(n+1) -1 ≤ h ≤ (n-1)/2

Nous savons que:

e= (n+1)/2 et h ≤ iDonc: h ≥ log[(n+1)/2] = log(n+1) -1

et: h ≤ i = (n-1)/2


CSI2510 24

Dans un Arbre binaire parfait de hauteur hil y a 2h+1 -1 nœuds

À chaque niveau il y a 2l nœuds, donc l'arbre a : h

∑ 2l = 1+ 2 + 4 + … + 2h = 2h+1-1

l=0

n = 2h+1 -1 l=1

l=2

l=3

l=0

Arbres binaires: propriétés - hauteur

CSI2510 13

CSI2510 25

Dans un arbre binaire:

log (n+1) ≤ h+1

h ≥ log (n+1) -1

Comme conséquence:

n ≤ 2h+1-1

n+1 ≤ 2h+1

évidemment n ≤ 2h+1 -1

CSI2510 26

Arbres binaires : propriétés - hauteur

h - 1

Un arbre binaire complet de hauteur hest formé par un arbre binaire parfaitde hauteur h-1 plus quelques feuilles =>n > 2h-1 => n≥ 2h

2h- 1

2h ≤n≤ 2h+1 -1 2h ≤n< 2h+1

h ≤ log(n) < h+1

Or h est un entier => h= partie entière de log(n)

CSI2510 14

CSI2510 27

h +1 ≤ n ≤ 2h+1 -1 1 ≤ e ≤ 2h h ≤ i ≤ 2h -1log(n+1) -1 ≤ h ≤ n-1

2h +1 ≤ n ≤ 2h+1 -1 h+1 ≤ e ≤ 2h h ≤ i ≤ 2h -1log(n+1) -1 ≤ h ≤ (n-1)/2

Arbres binaires pleins:

Arbres binaires:

Propriétés des arbres

CSI2510 28

Hauteur h d’un arbre:

Binaire: h ≥ log (n+1) -1

Binaire plein: log(n+1) -1 ≤ h ≤ (n-1)/2

Binaire complet: n ≥ 2h h = partie entière de log n

Binaire parfait: n = 2h+1 -1 h = log (n+1)-1

Arbres binaires : propriétés – hauteur

CSI2510 15

CSI2510 29

TADs pour Arbre binaire

• Méthodes accessoires -leftChild(p), rightChild(p), sibling(p)

• Méthodes de mise à jour -expandExternal(p), removeAboveExternal(p)

Autres méthodes spécifiques à l’application

CSI2510 30

Pré-, post-, in- (ordre)

• Se référer à l'endroit du parentrelatif aux enfants

• pré est avant: parent, enfant, enfant• post est après: enfant, enfant, parent• in est entre : enfant, parent, enfant

Traversée d’arbres binaires

CSI2510 16

CSI2510 31

Traversée d’arbres binaires Pré-ordre, Post-ordre

Algorithm preOrder(T,v) visit(v)

if v is internal: preOrder (T,T.LeftChild(v)) preOrder (T,T.RightChild(v))

Algorithm postOrder(T,v)if v is internal:

postOrder (T,T.LeftChild(v)) postOrder(T,T.RightChild(v)) visit(v)

CSI2510 32

In-ordre (Depth-first)

Algorithm inOrder(T,v)if v is internal:

inOrder (T,T.LeftChild(v)) visit(v) if v is internal: inOrder(T,T.RightChild(v))

Traversée d’arbres binaires

CSI2510 17

CSI2510 33

-

a b

Expressions arithmétiques

In-ordre: a – bPost-ordre: a b –Pré-ordre: – a b

+

××

-2

a 1

3 b2 × a - 1 + 3 × b

In-ordre:

2 a 1 - × 3 b × +Post-ordre:

PostOrder: gauche-droite-moiInOrder: gauche-moi-droite

PreOrder: moi-gauche-droite

CSI2510 34

Évaluer des Expressions Arithmétiques

• Spécialisation detraversée en post-ordre– la méthode récursive

retournant la valeur d'unsous-arbre

– en visitant un nœudintérieur, combiner lesvaleurs du sous-arbres

Algorithm evalExpr(v)if isExternal (v)

return v.element ()else

x ← evalExpr(leftChild (v))y ← evalExpr(rightChild (v))◊ ← operator stored at vreturn x ◊ y+

××

-2

5 1

3 2

CSI2510 18

CSI2510 35

+××

-2

5 1

3 2

+

Évaluer×

-2

5 1

×

3 2

Évaluer

-

152

Évaluer Évaluer×

3 2

Évaluer Évaluer

×

5 1-

Algorithm evalExpr(v)if isExternal (v)

return v.element ()else

x ← evalExpr(leftChild (v))y ← evalExpr(rightChild (v))◊ ← operator stored at vreturn x ◊ y

4

6

8

14

CSI2510 36

Imprimer des Expressions Arithmétiques

• Spécialisation de traverséeen in-ordre– imprimer l'opérande ou

l'opérateur en visitant lenœud

– imprimer “ (“ avant latraversée du sous-arbregauche

– imprimer “)“ après latraversée du sous-arbredroit

+

××

-2

a 1

3 b((2 × (a - 1)) + (3 × b))

2 × a - 1 + 3 × b

Algorithm printInOrder(v)if isInternal (v)

print(“(’’)printInOrder (leftChild (v))

print(v.element ())if isInternal (v)

printInOrder(rightChild (v))print (“)’’)

CSI2510 19

CSI2510 37

+

××

-2

a 1

3 b





( + )

CSI2510 38





+

××

-2

a 1

3 b

(( 2 ( a - 1 ) + ( 3 x b )x ))

CSI2510 20

CSI2510 39

Algorithm preOrderTraversalwithStack(T)

Stack S

TreeNode N

S.push(T) // pousser la référence à T dans la pile vide

While (not S.empty())

N = S.pop()

if (N != null) {

print(N.elem) // imprimer l'information

S.push(N.rightChild) // pousser la référence à

l'enfant gauche

S.push(N.leftChild) // pousser la référence à

l'enfant droit}

CSI2510 40


gb

dc

e f

h i

aT


N = S.pop()

print(N.elem)

CSI2510 21

CSI2510 41


gb

dc

e f

h i

aT


N = S.pop()

print(N.elem)

N

a

CSI2510 42


gb

dc

e f

h i

aT

S.push(N.rightChild) // pousser la référence à

l'enfant gauche

a

S.push(N.leftChild) // pousser la référence à

l'enfant droit

CSI2510 22

CSI2510 43


gb

dc

e f

h i

aT

N = S.pop()

a

CSI2510 44


gb

dc

e f

h i

aT

N = S.pop()

a

N

print(N.elem)

b

CSI2510 23

CSI2510 45


gb

dc

e f

h i

aT

ba

S.push(N.rightChild)

S.push(N.leftChild)

CSI2510 46


gb

dc

e f

h i

aT

ba

N = S.pop()

print(N.elem)

c

CSI2510 24

CSI2510 47


gb

dc

e f

h i

aT

ba

N = S.pop()

c

print(N.elem)

d

CSI2510 48


gb

dc

e f

h i

aT

ba c d


S.push(N.leftChild)

CSI2510 25

CSI2510 49


gb

dc

e f

h i

aT

ba c d

N = S.pop()

print(N.elem)

e

CSI2510 50


gb

dc

e f

h i

aT

ba c d

N = S.pop()

print(N.elem)

e f

CSI2510 26

CSI2510 51


gb

dc

e f

h i

aT

ba c d

N = S.pop()

print(N.elem)

e f g

CSI2510 52


gb

dc

e f

h i

aT

ba c d e f g


S.push(N.leftChild)

CSI2510 27

CSI2510 53

Traversée par tour d’Euler

• Traversée générique d’un arbre binaire• les traversées pré-ordre, in-ordre et post-ordre sont des

cas spéciaux de la traversée par tour d’Euler• “marche autour” de l’arbre et visite chacun des nœuds à

trois reprises:– à la gauche– par-dessous– à la droite

+

×

-2

5 1

3 2

LB

R×

CSI2510 54

Algorithm eulerTour(T,v)

visit v (à la gauche) if v is internal: eulerTour (T,T.LeftChild(v)) visit v (par-dessous)if v is internal: eulerTour(T,T.RightChild(v)) visit v (à la droite)

CSI2510 28

CSI2510 55

Réalisation d’arbre binaires

CSI2510 56

Réalisation d’arbre binaire avec unestructure chaînée

B

DA

C E

∅ ∅

∅ ∅ ∅ ∅

B

A D

C E

∅Un nœud est représenté par unobjet qui contient:

– Élément– Référence au nœud parent– Référence au nœud enfant gauche– Référence au nœud enfant droit

CSI2510 29

CSI2510 57

L’arbre binaire est formé par des nœuds de type BTNode

Element

Arbres binaires: TAD BTNode

Champs: element parent leftright

Méthodes: setelement(objet e)/getelement() setparent(objet e)/getparent() setleft(objet e)/getleft() setright(objet e)/getright()

CSI2510 58

replaceElement(v,obj) temp ← v.element v.element ← obj return temp

swapElements(v,w) temp ← w.element w.element ← v.element v.element ← temp

left (v) return v.left

right(v) return v.right

sibling(v) p ← parent(v) q ← left(p) if (v = q) return right(p) else return q


Element

CSI2510 30

CSI2510 59

swapElements(p,q),replaceElement(p,e)

isRoot(p),isInternal(p),isExternal(p)

leftChild(p), rightChild(p), sibling(p):

Complexité O(1)


CSI2510 60

expandExternal(v):new1 et new 2 sont les nouveaux nœudsif isExternal(v) v.left ← new1 v.right ← new2 size ← size +2

expandExternal(v): Transformer v d’un nœud extérieur enun nœud intérieur en créant deux nouveaux enfants

B

DA

C E

B

DA

C E

new1 new2


CSI2510 31

CSI2510 61

removeAboveExternal(v):

B

DA

C E

F G

B

DA

C

G

B

DA

CG


CSI2510 62

B

DA

C E

F G

B

DA

C

G

B

A Gv

pg

s

v

p

s

removeAboveExternal(v):if isExternal(v) { p ← parent(v) s ← sibling(v) if isRoot(p) {s.parent ← null and root ← s} else { g ← parent(p) if p isLeft(g) g.left ← s else g.right ← s s.parent ← g } size ← size -2 }

CSI2510 32

CSI2510 63

C

9

F

10

G

11

H

12

N

13

AOLEBIDH

87654321

1

32

4 5 6 7

8 9 10 11 12 13

H

D I

B E L O

A C F G H N

i

2i 2i+1

Arbres binaires complets: Implémentation avecun tableau

0

CSI2510 64

feuille? T[i]Le racine

Parent de T[i]

Enfant droit de T[i]

Enfant gauche de T[i]

swapElements(p,q),replaceElement(p,e)isRoot(p), isInternal(p),

isExternal(p)

1

2

4 5 6 7

8 9 10 11

I

3


n = 11

T[2i] si 2i ≤ n

T[2i+1] si 2i + 1 ≤ n

T[i div 2] si i > 1

T[1] si T ≠ 0

VRAI si 2i > n

CSI2510 33

CSI2510 65

swapElements(p,q),replaceElement(p,e)isRoot(p), isInternal(p),

isExternal(p)


complexité O(1)

CSI2510 66

∅

B

DA

C E

F

B

∅ ∅

A D F

∅

C

∅

E

• Un nœud est représenté par un objet qui contient:

– Élément– Référence au nœud parent– Référence a une séquence de nœuds enfants

Arbres généraux: Implémentation avec une structurechaînée

CSI2510 34

CSI2510 67

arbre T

Arbre binaire T' représentant T

Représenter un arbre général avec un arbre binaire

CSI2510 68

u dans T u’ dans T’

le premier enfant de u dans T est l'enfant gauche de u’ dans T’

le premier frère de u dans T est l'enfant droit de u’ dans T’

RÈGLES

CSI2510 35

CSI2510 69

T

T’

stupid

A

B

C

D

E

F

G H

I

LB

A

D

IC

E

GF

H

L

CSI2510 70

si u est une feuille dans T et n'a pas de frère,alors les enfants de u’ sont des feuilles

Si u est intérieur dans T et v est son premier enfantalors v’ est l’enfant gauche de u’ dans T’

Si v a un frère w qui le suit , w’ est l’enfantdroit de v’ dans T’

LL

C

D

E G

D

C

D

C

E

RÈGLES: à u dans T correspond u’ dans T’

Documents

Arbres - EngineeringPropriétés des arbres binaires pleins h = hauteur= Le nombre maximal d’ancêtres que peut avoir une des feuilles (le niveau maximal d’une feuille de l’arbre)