SD leçon 3 2

Structure de données

Arbre binaire

Plan de la leçon

Les arbres pourquoi ?

Arbres binaires

Arbres Binaires de Recherche

Expressions algébriques

4-(3+12*(9-5))*6

La priorité des opérations apparaît clairement

-

*

+

*

-

4

3

12

9 5

6

Modèle pour les structures hiérarchisées

Les arbres pourquoi ?

Compilation

Arbres syntaxiques

Si a>b Alors c=a; sinon c=b;

Exp

Si-alors-sinon

Inst Inst

c =a c =b

Inst

> ba

Les arbres pourquoi ?

1

3

2

A

B

D

C

1

A 2

3

B

C

Dout

in

Les arbres pourquoi ?

Arbres de décision

IA

Arbres de jeuxDébut du jeu

Le gagnant

1

1 32Le joueur A

1

1 32Le joueur B

2 3

Les arbres pourquoi ?

IA

Atouts

Accélère la recherche

en diminuant le nombre de comparaisons

Les arbres pourquoi ?

Définition récursive

Un arbre de type de base T est

soit une feuille (parfois structure vide)

soit un nœud de type T, racine, auquel est associé un nombrefini de sous arbres

Les arbres c’est quoi ?

Terminologie

père

racine

fils

feuille

Les arbres c’est quoi ?

Les arbres binaires

Tout nœud internepossède au plus

deux fils

Un arbre est un graphe ?

Cyclique ?

non oui

perdu

perdu

gagné

ouinon

Connexe ?

perdu

Définition

Les arbres binaires

Représentation par structure pointée

Allocation dynamique des nœuds

A

CB

ED

racine

Les arbres binaires

Les arbres binaires

Représentation par structure pointée

A

CB

ED

racine

Des indices à la place de pointeurs

Les arbres binaires

Représentation par tableau

val gauche droit

0 A 1 2

1 B -1 -1

2 C 3 4

3 D -1 -1

4 E -1 -1

A

CB

ED

racine

Les arbres binaires

Représentation par tableau

A

CB

ED

racine

x

feuille

Les arbres binaires

TDA : Construction

Les arbres binaires

TDA : Construction

ag ad

x

pere

(Pour tous les arbres)

profondeur maximale

taille en nombre de nœuds

Exploration de l'arbre

…

Les arbres binaires

TDA : Opérateurs

r

Les arbres binaires

TDA : Opérateurs

Opération qui consiste à traiter chaque nœud une seule fois d'une façon systématique

55

49

5834

10 50

22

3825

20

Les arbres binaires

TDA : Opérateurs/Exploration

Il y a trois façons de traverser un arbre

pré ordre : R , G , D

in ordre : G , R , D

post ordre : G , D , R

R

G D

Les arbres binaires

TDA : Opérateurs/Exploration

Traversée en profondeur

G , R , D

55

49

5834

10 50

22

3825

20

Les arbres binaires

TDA : Exploration en inordre

Les arbres binaires

55

49

5834

10 50

22

3825

20

TDA : Exploration en inordre

Les arbres binaires

Appels : représentés par un arbre binaire

fibo(0)=1

fibo(1)=1

fibo(n)= fibo(n-1) + fibo(n-2) pour n>1

À quel parcours correspond ces appels ?

fibo(3)

fibo(2) fibo(1)

fibo(0) fibo(1)

R, G, D

Il faut conserver l'ordre et le contexte

Exemple

Arborescence de fichiers

Ne détruire un fichier ques'il est feuille de l'arbre

Les arbres binaires

TDA : Autres opérateurs

Pour les arbres ordonnés surtout

Ajout d'un élément

Recherche d'un élément

…

Extraction d'un nœud

Les arbres binaires

Il faut conserver l'ordre et le contexte

TDA : Autres opérateurs

Arbres Binaires de Recherche

Arbre ordonné horizontalement

La clé d'un nœud est:

inférieure à toutes cellesde son sous arbre droit

supérieure à toutes cellesde son sous arbre gauche

55

< 55 > 55

Arbres Binaires de Recherche

55 34 49 20 38 58 10 50 25 22

La forme finale dépend des valeurs et de l'ordre d'entrée de ces valeurs

55

49

34

20

58

10 50

22

3825

Arbres Binaires de Recherche

Arbre ordonné horizontalement

Construction d’un ABR

55

49

5834

10 50

22

3825

20

racine

recherche(38,racine);

Arbres Binaires de Recherche

Recherche dans un ABR

Dichotomique

55

49

5834

10 50

22

3825

20

r

r

r

r

Arbres Binaires de Recherche

Recherche dans un ABR

Arbres Binaires de Recherche

Recherche+

Insertion

racine

55

49

5834

10 50

22

3825

20

24

racine=ajout(24,racine);

Arbres Binaires de Recherche

Ajout dans un ABR

Recherche récursive de la place pour accrocher la feuille

10

22

25

20

24

Arbres Binaires de Recherche

Ajout dans un ABR

55

49

5834

10 50

22

3825

20

racine

x

rac

Arbres Binaires de Recherche

Accrocher la feuille

Ajout dans un ABR

Arbres Binaires de Recherche

Arbres Binaires de Recherche

ajout (58,racine):

ajout (x, r->droit)

r->droit =Malloc(); // qui change

Donc :

r->droit= ajout (x, r->droit); // obligatoire

racine

55

racine

55

58

r

Arbres Binaires de Recherche

racine

NULL

racine

55

r

ajout (55,racine);

r==racine == NULL

r = Malloc(); // r change

Donc :

racine = ajout(55,racine); // obligatoire

Arbres Binaires de Recherche