LOGO

Algorithmique et Structures de

données évoluées

Algorithmique et Structures de

données évoluées

Responsable du coursMlle Amina GHRAB : amina.ghrab@live.fr

1ère année IAG2009 - 2010

Institut Supérieur de Gestion de Tunis

Objectifs

Être capable de choisir la structure adéquate à chaque problème.

Savoir manipuler les structures arborescentes;

Pouvoir implémenter les structures de données arborescentes;

Connaître les avantages et les inconvénients de chaque structure arborescente;

Connaitre l’utilité des structures de données arborescentes;

L’étudiant devra :

2

Références

Michel Divay : Algorithmes et structures de données génériques;

Abdelali Guerid, Pierre Breguet, Henri Röthlisberger : Algorithmes et structures de données avec C++ et Java;

XU Philippe, VENANT Antoine: Arbres binaires de recherche;

Cours Mme Nahla Ben Amor : Algorithmes et structures de données , http://isgprog2.ifrance.com/

3

Plan

4

Les arbres binaires de recherche2

Exercices33

Définition et terminologie

Algorithmes de parcours

Définition

Opérations sur les ABRs

Structures de données arborescentes1

Les AVLs

Définition et terminologie(1)

5

Une arborescence est une structure en forme d'arbre qui permet d'organiser les données en mémoire ou sur disque, de manière logique et hiérarchisée.

Dictionnaire arborescent;

Organisation d’un répertoire;

Définition et terminologie(2)

Père :prédécesseur direct d’un nœud;

Fils: successeur direct d’un nœud;

Feuille: un nœud sans fils;

Degré d’un nœud: le nombre de ces fils;

Génération: les nœuds d’un même niveau;

Branche: un chemin qui commence par la racine et se termine par une feuille;

Sous-arbre: un nœud accompagné de toute sa descendance;

6

Définition et terminologie(3)

Taille: le nombre de nœud de l’arbre;

Profondeur: le nombre de nœud de la branche la plus longue;

Ordre d’un arbre: le degré maximum parmi tous ses nœuds;

Arbre binaire: un arbre d’ordre 2;

Arbre binaire complet: chaque nœud autre qu’une feuille admet deux descendants et toutes les feuilles sont au même niveau;

Arbre binaire dégénéré: tous les nœuds de cet arbre ont au plus un descendant.

7

Définition et terminologie(3)

IllustrationA

E

DB

L

F

N

G

MK

Taille:?Profondeur:?Ordre:?

Taille:10Profondeur:4Ordre:2

8

Définition et terminologie(4)

A

E

DB

L

C

H

F

N

G

MK

9

Parcours en largeurParcours en profondeur

Algorithmes de parcours

10

Algorithmes de parcours

A

E

DB

L

C

H

F

N

G

MK

1

2 43

65

8

7

11109 12

A,B,C,D,E,F

G,H,K,L,M,N

Largeur

11

Algorithmes de parcours

A

E

DB

L

C

H

F

N

G

MK

1

2

3

4 5 6

7 8

9 10

11 12

A,B,E,H,K,L,C,D

F,G,M,N

Profondeur

12

Algorithmes de parcours

Parcours en profondeur

parcours_profond(AB:arbre)DebutSi nonVide(AB) alors Afficher Racine(AB) parcours_profond(SAG(AB)) parcours_profond(SAD(AB))Fin siFin

13

Algorithmes de parcours

TAF:

Ecrire l’algorithme du parcours en profondeur pour un arbre n-aire;

Ecrire l’algorithme du parcours en largeur

14

Plan

15

Les arbres binaires de recherche2

Exercices(Quiz)33

Définition et terminologie

Algorithmes de parcours

Définition

Operations sur les ABRs

Structures de données arborescentes1

Les AVLs

Définition

Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé d’identification, et tel que chaque nœud du sous-arbre gauche a une clé inférieure à celle du nœud considéré, et que chaque nœud du sous-arbre droit a une clé supérieure à celle-ci.

Utiles pour ranger des valeurs ordonnées;

permettent de rechercher et de trouver un nœud de façon rapide et simple.

16

Opèrations sur les ABRs: insertion

Exemple:44,77,55,22,33

Insérer 44 44 Insérer 77

55

Insérer 5544

Insérer 22

77

Insérer 3322

44

77

55

44

77

22

55

44

77

33

17

0 fils1 seul fils

Opérations sur les ABRs: Suppression

2 fils

18

Opérations sur les ABRs: Suppression 1er cas: le nœud a 0 fils

On supprime le nœud et on remplace son adresse par NULL

Supprimer 33

22

55

44

77

33

22

19

Opérations sur les ABRs: Suppression 2éme cas: le nœud a un seul fils

On supprime le nœud et on remplace son adresse dans son père par l’adresse de son fils

Supprimer 22

22

55

44

77

33

33

20

Opérations sur les ABRs: Suppression 3eme cas: Le nœud a deux fils

o On supprime N et on le remplace par l’élément maximal de son sous arbre gauche puis on le supprime;

o On supprime N et on le remplace par l’élément minimal de son sous arbre droit puis on le supprime

22

55

44

77

3312

Supprimer 22

147

14

55

44

77

3312

7

21

Opérations sur les ABRs: Suppression

Algorithme

Delete(n:nœud)

Debut

n,q:nœud,racine:noeud;test,Supp:boolean;

Si

(n.compareto(ref-racine)==0;

Supp=vrai;test=vrai;

Fin si

Tant que(racine<>null)&&(!test)

Si

(n.compareto(racine)<0) alors q=racine;racine=racine.fils-gauche;

Sinon (si n.compareto(racine)>0) q=racine;racine=racine.fils-droit fin si;

Sinon test=vrai;

Fin si

22

Opérations sur les ABRs: Suppression

Si test=vrai alors

Si((racine.fils-droit<>null)&&(racine.fils-gauche<>null))

alors

Z=chercherMin(racine.fils-droit)

Racine=z;

Z=supprimermin(racine.fils-droit);

Fin si

Fin si

Fin tant que

23

Opérations sur les ABRs: Suppression

TAF

Terminer le traitement du premier et du deuxième cas de la suppression dans un arbre de recherche.

24

ABRs

Très éfficaces pour la recherche, les insertions et les suppressions;

24

Les AVLs

ABR Dégénéré !!!!!!!

Complexité est en O(n)

Il faut les équilibrer

25

Les AVLs

26

Un AVL est un arbre binaire de recherche tel que, pour tout nœud de l’arbre, les hauteurs des sous-arbres gauches et des sous-arbres droits diffèrent d’au plus de 1;

Remédier au problème de déséquilibre dans les arbres binaires de recherche;

Ce sont des arbres de recherche équilibrés dont les opérations de recherche, d'insertion et de suppression ne sont pas coûteuses en terme de complexité.

Les AVLs

FG Info BAL FD

BAL=hauteur(SAD)-hauteur(SAG)

BAL =0BAL=1BAL=-1

Principe

Nœud

28

AVLs

22

55

44

77

33

56

12 44

1

0 -1

0 0 0

0

22

55

44

77

33

56

12 44

-1

-2 -1

2 0 0

0

14

13-1

0

1

29

Questions

30