Chapitre 5 arbres binaires

CHAPITRE V:

ARBRES BINAIRES

Université Saad Dahlab de Blida

Faculté des Sciences

Département d’Informatique

Licence d’Informatique

Semestre 3 (2ème année)

Algorithmique et Structures de Données

Mme AROUSSI

2016-2017

Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/

https://sites.google.com/a/esi.dz/s-aroussi/



Introduction

Définitions et Terminologies

Les Arbres Binaires

Les Arbres Binaires de Recherche (ABR)

Les Arbres AVL

2

PLAN DU CHAPITRE V

3

Dans les tableaux, nous avons :

Un accès direct par indice (rapide)

L’insertion et la suppression nécessitent des décalages

Dans les Listes Linéaires Chaînées, nous avons :

Un accès séquentiel lent

L’insertion et la suppression se font uniquement par modification de

chaînage

Les arbres représentent un compromis entre les deux :

Un accès relativement rapide à un élément à partir de sa clé

L’insertion et la suppression non coûteuses

INTRODUCTION

4

De plus, les arbres sont des structures de données

fondamentales en informatique, très utilisés dans tous les

domaines, parce qu’ils sont bien adaptés à la

représentation naturelle d’informations homogènes

organisées, et d’une grande commodité et rapidité de

manipulation.

INTRODUCTION

5

Leur usage est multiple, car il capte l’idée de hiérarchie; à

titre d’exemples, nous pouvons citer:

Découpage d’un livre en parties, chapitres, sections,

paragraphes…,

INTRODUCTION

Livre

C1 C2 C3

S1.1 S1.2 S2.1 S2.2 S2.3

S2.1.1 S2.1.2

6



Hiérarchies de fichiers,

INTRODUCTION

/

etc/ var/ tmp/

run/rc.d/ apache/

httpd.conf

inet.conf

rc.localrc.inet1

7



Expressions Arithmétiques

INTRODUCTION

-

A *

+ F

B *

C -

D E

L’expression A - (B + C * (D - E)) * F

se représente facilement par un arbre

où apparaît clairement la priorité des

opérations:

8

DÉFINITIONS & TERMINOLOGIES

Un arbre est une structure de données (souvent dynamique)

représentant un ensemble de valeurs organisées

hiérarchiquement (non linéaire). Chaque valeur est stockée dans

un nœud. Les nœuds sont connectés entre eux par des arêtes

qui représentent des relations parent/fils.

A

C D B

E G H F I

L K J

Nœuds Arêtes

9


Racine: est le nœud qui n'a

pas de prédécesseur (parent) et

possède zéro ou plusieurs fils. La

racine constitue la caractéristique

d'un arbre.

Feuille : est un nœud qui n'a

pas de successeur (fils). Une

feuille est aussi appelée un nœud

externe.

Nœud interne : est tout nœud

qui admet au moins un

successeur (fils).

A

C D B

E G H F I

L K J

Racine

Nœud interne

Feuilles

10


Fils d’un nœud : sont ses

successeurs. Dans l'exemple, F,

G, H, et I sont les fils du nœud D.

Frères : sont les successeurs

ou les fils issus d'un même nœud

(parent direct). Dans l'exemple,

B, C et D sont des frères.

Père : est un nœud qui admet

au moins un successeur (fils).

Dans l'exemple, D est le père des

nœuds F, G, H et I.

A

C D B

E G H F I

L K J

11


Sous arbre : est une portion

de l'arbre. Dans l'exemple, le

nœud G avec ces deux fils J et K

constituent un sous arbre.

Une branche est une suite de

nœuds connectés de père en fils

(de la racine à une feuille).

A-B-E

A-C

A-D-F

A-D-G-J

…..

A

C D B

E G H F I

L K J

12


Descendants d’un nœud :

sont tous les nœuds du sous arbre

de racine nœud. Dans l'exemple,

les descendants de D sont F, G,

H, I, J, K et L.

Ascendants d’un nœud :

sont tous les nœuds se trouvant

sur la branche de la racine vers

ce nœud. Dans l'exemple, les

ascendants de J sont G, D et A.

Les ascendants de E sont B et A.

A

C D B

E G H F I

L K J

13


Taille d’un arbre: est le

nombre de nœuds qu’il possède.

Taille de l’arbre ci contre = 12

Un arbre vide est de taille

égale à 0.

Degré d’un nœud : est le

nombre de ses fils. Dans

l'exemple, le degré de B est 1, le

degré de D est 4.

Degré d’un arbre : est le

degré maximum de ses nœuds.

Degré de l’arbre ci contre = 4

A

C D B

E G H F I

L K J

14


Le niveau d'un nœud: est la distance qui le sépare de la

racine:

Le niveau de la racine = 0

Le niveau de chaque nœud est égale au niveau de son père plus 1

Le niveau du nœud contenant ‘G' est égal à 2.

Racine

…..…………..…………………………………………….......

………………..…………………………………………….......

……………………………….......

.…………………………………………….......

A

C D B

E G H F I

L K J

Niveaux

0

1

2

3

15


La profondeur d'un arbre (ou sa hauteur) : est le plus

grand niveau, c-à-d la distance entre la racine et la feuille la plus

lointaine. Dans l'exemple, la profondeur de l'arbre est égal à 3

Racine

…..…………..…………………………………………….......

………………..…………………………………………….......

……………………………….......

.…………………………………………….......

A

C D B

E G H F I

L K J

Niveaux

0

1

2

3

16


Forêt : est un ensemble d'arbres.

A

C D B

E

G

H F I

L

K J

17


Définition récursive

Cas particulier: NIL est un arbre vide, contenant zéro nœud

T1

T’1

Racine

Racine de T1

Racine de T’1

Cas général: SI n est un

nœud et si T1, T2, ...Tm sont

des arbres, ALORS on peut

construire un nouvel arbre en

connectant T1, T2, ...Tm

comme des fils à n.

Chaque Ti est définit de la

même manière (récursivement).

T1, T2, ...Tm sont alors des

sous- arbres de n.

PARTIE II:

ARBRES BINAIRES

Définition

Modèle

Parcours

Représentation contigüe

Exemple d’application 19

PLAN DE LA PARTIE II

20

DÉFINITION

Un arbre binaire est un arbre où chaque nœud est connecté à

deux sous-arbres (un sous-arbre gauche et un sous-arbre droit).

Donc, un arbre binaire est un arbre de degré 2, c’est-à-dire que

chaque nœuds a au plus deux fils. Ainsi, le premier fils d'un nœud

n est appelé Fils-Gauche (FG) et le deuxième fils est appelé Fils-

Droit (FD). A

B

C K G

F

H I

J

racine

D

NIL

21

DÉFINITION

Un arbre binaire est dit strictement binaire si chaque nœud

interne (non feuille) a exactement 2 fils différents de NIL.

Si un arbre strictement binaire a n feuilles Alors :

le nombre total de ses nœuds = 2n-1.

le nombre de ses nœuds non feuilles (nœuds internes) = n-1

A

B

C K G

F

H I

J

racine

D

M

Le nombre de feuilles : n=6

(C, D,H, M, J, K)

Le nombre total de nœuds :

2n-1=11

Le nombre de nœuds

internes: n-1=5 (A, B, F, G, I)

22

DÉFINITION

Un arbre binaire complet est un arbre strictement binaire où

toutes les feuilles sont au même niveau.

Dans un arbre binaire complet de profondeur « d » :

le nombre total de nœuds n = 20 + 21 + 22 + ... 2d = 2d+1-1

ainsi, d = log2(n+1) – 1

le nombre de nœuds internes = 2d-1

le nombre de feuilles = 2d

le nombre de nœuds dans le niveau i = 2i

racine

D

A

B

C K G

F

23

DÉFINITION

Un arbre binaire complet est un arbre strictement binaire où

toutes les feuilles sont au même niveau.

Dans l’exemple ci dessous:

d = 2

le nombre total de nœuds n = 23-1 = 7

le nombre de nœuds internes = 22-1 = 3

le nombre de feuilles = 22 = 4

le nombre de nœuds dans le niveau 1 = 2

racine

D

A

B

C K G

F

24

MODÈLE

L'arbre est implémenté souvent de manière dynamique

comme un ensemble de maillons (nœuds) chaînés entre eux.

La structure d'un nœud de l'arbre est la suivante :

Structure de Données

TYPE Tnoeud = STRUCTURE

Info : Typeqq

FG : * Tnoeud

FD : * Tnoeud

FIN

VAR Arbre : * Tnoeud

25

MODÈLE

On définit le modèle (machine abstraite) suivant d’un arbre

binaire:

Fonction Rôle

Info(p) permet d'accéder à l'information du nœud p

FG(p) permet d'accéder à l'information de fils gauche du nœud p

FD(p) permet d'accéder à l'information de fils droit du nœud p

Aff_info(p, x) permet de modifier l'information du nœud p

Aff_FG(p, q) permet de modifier l’adresse de fils gauche du nœud p

Aff_FD(p, q) permet de modifier l‘adresse de fils droit du nœud p

Créer_noeud(x) permet de créer un nœud avec x comme information et retourne la référence du nœud. Le nœud créé a Nil comme fils

gauche et droit.

Liberer_noeud(p) permet de libérer le nœud référencé par p.

26

EXERCICE 01

Ecrire des algorithmes récursifs pour déterminer dans un

arbre binaire contenant des entiers:

a. le nombre de nœuds,

b. le nombre de feuilles,

c. le nombre des nœuds internes

d. la profondeur.

e. la somme des contenus de tous les nœuds,

f. le minimum des valeurs contenues.

g. le maximum des valeurs contenues

h. l’existence d’un élément x

27

PARCOURS

Le parcours d’un arbre consiste à passer par tous ses

nœuds.

Les parcours permettent d’effectuer tout un ensemble de

traitement sur les arbres.

On distingue deux types de parcours :

Des parcours en profondeur (depth-first) explorent

l'arbre branche par branche. Parmi lesquels: le Préordre,

l‘Inordre et le Postordre.

Des parcours en largeur (breadth-first) explorent

l'arbre niveau par niveau

28

PARCOURS EN PROFONDEUR

Dans un parcours en profondeur, on descend le plus

profondément possible dans l’arbre puis, une fois qu’une

feuille a été atteinte, on remonte pour explorer les autres

branches en commençant par la branche « la plus basse »

parmi celles non encore parcourues.

Le parcours en profondeur peut se faire en :

Préordre (Préfixe) : où on affiche la racine avant ses fils (Racine

FG FD),

Inordre (Infixe) : où on affiche le fils gauche avant sa racine et

son frère droit (FG Racine FD),

Postordre(Postfixe) : où on affiche les fils avant leur racine (FG

FD Racine).

29


Ces parcours (préordre, inordre et postordre) sont des

parcours simples à définir et à programmer (en récursif).

Soit R un arbre binaire (pouvant être vide : R=NIL).

S'il n'est pas vide (n pointe le nœud racine), alors il a la forme

suivante (avec T1 et T2 des sous arbres définis de la même manière

que n) : R

T1 T2

Sous arbre gauche G Sous arbre droit D

30

PARCOURS PREORDRE

Le parcours préordre de R (s'il n'est pas vide) consiste à

visiter le nœud racine (R) ensuite parcourir récursivement

en préordre les sous arbres T1 (sous arbre gauche) puis T2

(sous arbre droit) ce qui donne : [ R , T1 , T2 ou RGD]

R

T1 T2


31

PARCOURS PREORDRE

Le parcours préordre de R (s'il n'est pas vide) consiste à

visiter le nœud racine (R) ensuite parcourir récursivement

en préordre les sous arbres T1 (sous arbre gauche) puis T2

(sous arbre droit) ce qui donne : [ R , T1 , T2 ou RGD]

A

B C

E G D F

H I

H I D E B F G A C Résultat de parcours:

32

PARCOURS PREORDRE

La procédure (récursive) qui affiche les valeurs en

parcours préordre d’un arbre de racine R est :

Procédure Préordre( R:* Tnoeud )

Début

SI R ≠ NIL

ecrire( Info(R) )

Préordre( FG(R) )

Préordre( FD(R) )

FSI

fin

33

PARCOURS INORDRE

Le parcours inordre de R (s'il n'est pas vide) consiste

d'abord à parcourir récursivement en inordre le sous arbre

gauche T1, puis visiter le nœud racine (R) ensuite parcourir

récursivement en inordre le sous arbre droit T2 ce qui donne

[ T1 , R , T2 ou GRD ]

R

T1 T2


34

PARCOURS INORDRE

Le parcours inordre de R (s'il n'est pas vide) consiste

d'abord à parcourir récursivement en inordre le sous arbre

gauche T1, puis visiter le nœud racine (R) ensuite parcourir

récursivement en inordre le sous arbre droit T2 ce qui donne

[ T1 , R , T2 ou GRD ]

A

B C

E G D F

H I

Résultat de parcours: H I D E B F G A C

35

PARCOURS INORDRE


parcours inordre d’un arbre de racine R est :

Procédure Inordre( R:*Tnoeud )

Début

SI R ≠ NIL

Inordre( FG(R) )

ecrire( Info(R) )

Inordre( FD(R) )

FSI

fin

36

PARCOURS POSTORDRE

Le parcours postordre de R (s'il n'est pas vide) consiste

d'abord à parcourir récursivement en postordre les sous

arbres T1 puis T2 ensuite visiter le nœud racine (R) ce qui

donne [ T1 , T2 , R ou GDR]

R

T1 T2


37

PARCOURS POSTORDRE

Le parcours postordre de R (s'il n'est pas vide) consiste

d'abord à parcourir récursivement en postordre les sous

arbres T1 puis T2 ensuite visiter le nœud racine (R) ce qui

donne [ T1 , T2 , R ou GDR]

A

B C

E G D F

H I

Résultat de parcours: H I D E B F G A C

38

PARCOURS POSTORDRE


parcours postordre d’un arbre de racine R est :

Procédure Postordre( R: *Tnoeud)

Début

SI R≠NIL

Postordre( FG(R) )

Postordre( FD(R) )

ecrire( Info(R) )

FSI

fin

39


On peut faire ces trois parcours sans utiliser la

récursivité. Il faudra alors un moyen pour pouvoir remonter

dans les branches de l'arbre:

On pourra par exemple utiliser une structure de pile pour

sauvegarder les adresses des nœuds par lesquels on est descendu et

les dépiler quand on en aura besoin pour remonter.

On peut aussi enrichir la structure des nœuds en incluant un

pointeur vers le nœud père.

Il existe d'autres types de parcours en profondeur, comme

par exemple:

Le préordre inverse (R T2 T1 ou RDG),

L'inordre inverse (T2 R T1 ou DRG),

Le postordre inverse (T2 T1 R ou DGR).

40


Exercice 02: Trouver les algorithmes itératifs du

parcours en profondeur (préordre, inordre et postordre ) dans

un arbre binaire

41

PARCOURS EN LARGEUR

Dans le parcours par niveau, tous les nœuds d’un même

niveau sont traités avant de descendre au niveau suivant

Résultat de parcours: A

B C

E G D F

H I

H I D E B F G A C

42

PARCOURS EN LARGEUR

Dans le parcours par niveau, tous les nœuds d’un même

niveau sont traités avant de descendre au niveau suivant

Procédure parcours_largeur( R:* Tnoeud )

Var F:filed’attente; P: *Tnoeud;

Debut

P←R;

Si R ≠ NIL Alors

Enfiler(F,P);

TQ (Non FileVide(F))

Defiler(F,P);

écrire(info(P));

Si FG(P) ≠ NIL Alors Enfiler(F,FG(P));

Si FD(P) ≠ NIL Alors Enfiler(F,FD(P));

FTQ

Fin

43

EXERCICE 01

Ecrire des algorithmes itératifs pour déterminer dans un

arbre binaire contenant des entiers:

a. le nombre de nœuds,

b. le nombre de feuilles,

c. le nombre des nœuds internes

d. la profondeur.

e. la somme des contenus de tous les nœuds,

f. le minimum des valeurs contenues.

g. le maximum des valeurs contenues

h. l’existence d’un élément x

44

REPRÉSENTATION CONTIGÜE

On peut présenter les arbres de manière statique en

utilisant les tableaux.

Représentation Standard:

Chaque élément du tableau possède quartes champs: un pour

l'information, un pour le fils gauche, un pour le fils droit et un champ

de type booléen pour indiquer si la case est libre ou occupée.

TYPE Tnoeud= STRUCTURE

Info : Typeqq

FG : entier

FD : entier

vide: booléen

FIN

45



Si la racine de l’arbre est toujours à la position 1 du tableau,

l’arbre sera défini comme suit:

VAR Arbre = TABLEAU[M] de Tnoeud

Indice Tnoeud

Vide FG Info FD

0 F 1 a 4

1 F 2 b 3

2 F -1 c -1

3 F -1 d -1

4 F -1 e -1

… V ? ? ?

M-1 V ? ? ?

Racine

46



Si on veut que la racine soit n'importe où dans le tableau, alors

l'arbre sera défini (le nœud reste inchangé):

TYPE Tarbre = STRUCTURE

T : TABLEAU[M] de Tnoeud

Racine : ENTIER

FIN

VAR Arbre : Tarbre

Indice Tnoeud

Vide FG Info FD

0 F -1 c -1

1 F 0 b 3

2 F 1 a 4

3 F -1 d -1

4 F -1 e -1

… V ? ? ?

M-1 V ? ? ?

PARTIE III:

ARBRES BINAIRES DE

RECHERCHE(ABR)

Définition

Complexité

Parcours

Opérations de Recherche et de mise à jours (Insertion et

Suppression)

Exemples d’application: Tri par ABR

48

PLAN DE LA PARTIE III

49

DÉFINITION

Un Arbre Binaire de Recherche (ABR) est un arbre

binaire ordonné tel que pour tout nœud « i »:

Toutes les valeurs du sous arbre gauche de « i » sont strictement

inférieures à la valeur (ou clé) de « i », et

Toutes les valeurs du sous arbre droit de « i » sont supérieures ou

égales à la valeur (ou clé) de « i ».

50

DÉFINITION

Un Arbre Binaire de Recherche (ABR) est un arbre

binaire ordonné tel que pour tout nœud « i »:

Toutes les valeurs du sous arbre gauche de « i » sont strictement

inférieures à la valeur (ou clé) de « i », et

Toutes les valeurs du sous arbre droit de « i » sont supérieures ou

égales à la valeur (ou clé) de « i ».

Intérêt de cette propriété : diminuer la complexité

temporel de recherche, d’insertion et de suppression dans

l’arbre

51

PARCOURS

Exemple: Appliquer les différents parcours vus sur

l’ABR suivant:

20

15 59

5

3 10

27 71

33

8 55

52

Le parcours inordre de cet arbre donne la liste ordonnée

suivante : 3, 5, 8, 10, 15, 20, 27, 33, 52, 55, 59, 71

52

OPÉRATION DE RECHERCHE

La recherche est dichotomique, à chaque étape, un sous

arbre est éliminé:

Rechercher (55)

Rechercher (FD(20))

Rechercher (FG(59))

Rechercher (FD(27))

Rechercher (FD (33))

Élément trouvé

20

15 59

5

3 10

27 71

33

8 55

52

55 ?

53


La recherche est dichotomique, à chaque étape, un sous

arbre est éliminé:

Rechercher (6)

Rechercher (FG(20))

Rechercher (FG(15))

Rechercher (FD(5))

Rechercher (FG (10))

Rechercher (FG (8))

Rechercher (Nil) Élément non trouvé

20

15 59

5

3 10

27 71

33

8 55

52

6 ?

54


Exercice 07 : Trouver les algorithmes (récursifs et

itératifs) de recherche, d'insertion et de suppression

dans un Arbre Binaire de Recherche (ABR).

55

OPÉRATION DE RECHERCHE Fonction RechercherABR_rec (R:*Tnoeud, x: entier) : * Tnoeud

Debut

Si R =Nil alors

Retourner (Nil)

Sinon

Si Info (R) = x alors

Retourner (R)

Sinon

Si Info(R)>x alors

Retourner (RechercherABR_rec(FG(R), x))

Sinon

Retourner (RechercherABR_rec(FD(R), x))

Fin

56

OPÉRATION DE RECHERCHE Fonction RechercherABR _iter(R:*Tnoeud, x: entier) : * Tnoeud

Debut

TQ R ≠Nil faire


Retourner (R)

Sinon

Si Info(R)>x alors

RFG(R)

Sinon

RFD(R)

FTQ

Retourner (Nil)

Fin

57

OPÉRATION D’INSERTION

L'insertion d'un élément se fait toujours au niveau d'une

feuille. Cette insertion dans un ABR doit maintenir la

propriété d’ordre des arbres de recherche. Ainsi:

1. Rechercher la position d’insertion

2. Raccorder le nouveau nœud à son parent

58


RechercherPosition (25)

Rechercher (FD(20))

Rechercher (FG(59))

Position trouvé pour l’insertion, le père est le nœud 27

Insérer 25 au niveau de la feuille dont le père est 27

20

15 59

5

3 10

27 71

33

8 55

52

+ 25

25

59


Exercice 06 :

1. Soit R un arbre binaire de recherche (ABR)

a. Construire cet arbre partir des valeurs suivantes :

25, 60, 35, 10, 5, 20, 65, 45, 70, 40, 50, 55, 30, 15

b. Ajouter à l'arbre obtenu et dans l'ordre, les

éléments suivants : 22, 62, 64, 4, 8

c. Supprimer de l'arbre obtenu et dans l'ordre les éléments

suivants : 15, 70, 50, 35, 60, 25

60





61


Fonction InsererABR_rec (R:*Tnoeud, x: entier) : * Tnoeud

Debut

Si R =Nil alors

RCreerNoeud(x)

Sinon

Si Info(R)>x alors

Aff_FG(R, InsererABR_rec(FG(R), x))

Sinon

Aff_FD(R, InsererABR_rec(FD(R), x))

Retourner (R)

Fin

62

OPÉRATION D’INSERTION Fonction InsererABR_iter (R:*Tnoeud, x: entier) : * Tnoeud

Var P, Q: *Tnoeud

Debut

PCreerNoeud(x)

Si R =Nil alors

RP

Sinon

Inserer faux

TQ (non inserer) faire

Si Info(R)>x alors

Si FG(R) =Nil alors

Aff_FG(R, P); inserer vrai

Sinon RFG(R)

Sinon

Si FD(R)=Nil alors

Aff_FD(R, P); inserer vrai

Sinon RFD(R)

Retourner (R)

63

OPÉRATION DE SUPPRESSION

Pour supprimer le nœud « i » d’un ARB, il faudra le

rechercher. Une fois le nœud « i » trouvé, on se trouve

dans une des situations suivantes :

64


Cas 1: Suppression d'une feuille

Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.

Exemple: supprimer le nœud i qui contient la valeur 8

1. Rechercher(8)

2. Libérer le nœud « i »

« i »

20

15 59

5

3 10

27 71

33

8 55

52

12

65


Cas 2: Suppression d'un nœud avec un fils

Il faut l'enlever de l'arbre en le remplaçant par son fils.

Exemple: supprimer le nœud « i » qui contient la valeur 10

1. Rechercher(10)

2. Chainer le père de i avec le FD(i)


« i »

20

15 59

5

3 10

27 71

33

12 55

52

66


Cas 2: Suppression d'un nœud avec un fils

Il faut l'enlever de l'arbre en le remplaçant par son fils.

Exemple: supprimer le nœud i qui contient la valeur 10

1. Rechercher(10)

2. Chainer le père de i avec le FG(i)


« i »

20

15 59

5

3 10

27 71

33

55

52

8

67


Cas 3: Suppression d'un nœud avec deux fils

Etape 1: On échange le nœud à supprimer avec son successeur

le plus proche (le nœud le plus à gauche du sous-arbre droit) ou

son plus proche prédécesseur (le nœud le plus à droite du

sous-arbre gauche). Cela permet de garder une structure d'arbre

binaire de recherche.

34

66

50

56

55

71

70

69

81

22

8

17

9

29

25

23 32

Le plus proche prédécesseur

Le plus proche successeur

68



Etape 1 Cas A: On échange le nœud à supprimer avec son

successeur le plus proche (le nœud le plus à gauche ou le plus

petit du sous-arbre)

Racine: 71

La plus petite valeur : 69

34

66

50

56

55

71

70

69

81

22

8

17

9

29

25

23 32

69




successeur le plus proche (le nœud le plus à gauche ou le plus

petit du sous-arbre)

Racine: 71


34

66

50

56

55

71

70

69

81

Fonction Successeur (R: *Tnoeud): *Tnoeud Debut

RFD(R)

Si R≠Nil alors

TQ FG(R)≠Nil faire RFG(R)

Retourner (R) Fin

70




plus proche prédécesseur (le nœud le plus à droite ou le plus

grand du sous-arbre gauche).

Racine: 50

La plus grande valeur : 56

34

66

50

56

55

71

70

69

81

22

8

17

9

29

25

23 32

71




plus proche prédécesseur (le nœud le plus à droite ou le plus

grand du sous-arbre gauche).

Racine: 50


34

66

50

56

55

71

70

69

Fonction Predecesseur (R: *Tnoeud): *Tnoeud

Debut

RFG(R)

Si R≠Nil alors

TQ FD(R)≠Nil faire RFD(R)

Retourner (R) Fin

72



Etape 2: on applique à nouveau la procédure de suppression qui

est maintenant une feuille ou un nœud avec un seul fils.

Ainsi, si on choisit d’échanger le nœud « 66 » avec son plus proche

successeur « 69 », on obtient

34

66

50

56

55

71

70

69

81

22

8

17

9

29

25

23 32

69

73


Puis on applique à nouveau la procédure de suppression qui est

maintenant une feuille ou un nœud avec un seul fils.

Ainsi, si on choisit d’ échanger le nœud « 66 » avec son plus proche

prédécesseur « 56 », on obtient

34

66

50

55

71

70

69

81

22

8

17

9

29

25

23 32

56


74


En conclusion, pour supprimer le nœud « i » d’un ARB, il

faudra le rechercher. Une fois trouvé, on rencontre une

des situations suivantes :

Cas « i »

Action FG FD

Feuille Nil Nil Libérer le nœud « i »

Avec un

fils

Nil ≠Nil Chaîner le père au fils de « i » (FG(i) ou

FD(i)) ensuite libérer le nœud « i » ≠Nil Nil

Avec

deux

fils

≠Nil ≠Nil

1. Rechercher le plus proche

prédécesseur ou successeur de « i »,

soit « P ».

2. Remplacer Info(i) par Info(P)

3. Supprimer le nœud « P »

75

Exercice 06 :

1. Soit R un arbre binaire de recherche (ABR)


25, 60, 35, 10, 5, 20, 65, 45, 70, 40, 50, 55, 30, 15

b. Ajouter à l'arbre obtenu et dans l'ordre, les éléments

suivants : 22, 62, 64, 4, 8

c. Supprimer de l'arbre obtenu et dans l'ordre les

éléments suivants : 15, 70, 50, 35, 60, 25


76





77


Fonction SupprimerABR_iter (R:*Tnoeud, x: entier) : * Tnoeud

Var P, Q: *Tnoeud

Debut

RechercherABR (R, x, Q, P)

Procedure RechercherABR (R: *Tnoeud, x:

entier, Var Q: *Tnoeud, Var Père: *Tnoeud)

Père Nil; Q Nil;

TQ R ≠Nil faire


QR

Sinon

PèreR

Si Info(R)>x alors

RFG(R)

Sinon

RFD(R)

FTQ

Cette procédure

retourne l’adresse du

nœud contenant x

(soit Q) ainsi que

l’adresse de son père

(soit Père)

78


Fonction SupprimerABR_iter (R:*Tnoeud, x: entier) : * Tnoeud

Var P, Q: *Tnoeud

Debut


Si Q ≠Nil alors

// l’élément x existe dans Q

Si FG(Q) =Nil alors

Si FD(Q) =Nil alors

//Cas n°1: Q est une feuille

Chaîner (R, P, Q, Nil)

Sinon //Cas n°2: Q possède un FD

Chaîner (R, P, Q, FD(Q))

Sinon

Si FD(Q) =Nil alors

//Cas n°2: Q possède un FG

Chaîner (R, P, Q, FG(Q))

Cette procédure

permet de chaîne le

père de Q (P) avec le

Fil de Q selon la

valeur de Q

79

OPÉRATION DE SUPPRESSION Fonction SupprimerABR_iter (R:*Tnoeud, x: entier) : * Tnoeud

Var P, Q: *Tnoeud

Debut


Si Q ≠Nil alors

// l’élément x existe dans Q

Si FG(Q) =Nil alors

Si FD(Q) =Nil alors

//Cas n°1: Q est une feuille




Sinon

Si FD(Q) =Nil alors

//Cas n°2: Q possède un FG


Procedure Chaîner (Var R:

*Tnoeud , PèreQ, NoeudQ, FilsQ:

*Tnoeud)

Si PèreQ =Nil alors

RFilsQ

Sinon

Si Info(PèreQ)>info(NoeudQ)

alors

Aff_FG(PèreQ, FilsQ)

Sinon

Aff_FD(PèreQ, FilsQ)

80


Var P, Q: *Tnoeud

Debut


Si Q ≠Nil alors // l’élément x existe dans Q

Si FG(Q) =Nil alors

Si FD(Q) =Nil alors //Cas n°1: Q est une feuille




Sinon

Si FD(Q) =Nil alors //Cas n°2: Q possède un FG


Sinon // Cas n°3: Q possède deux fils

Successeur (Q, S, PS)

Cette procédure retourne l’adresse du successeur

de Q (S) ainsi que l’adresse de son père (PS)

81


Var P, Q: *Tnoeud

Debut



Si FG(Q) =Nil alors





Sinon





Procédure Successeur (R: *Tnoeud, Var S, PS: *Tnoeud) PSR; SFD(R)

Si (S≠Nil) alors

TQ FG(S)≠Nil faire PSS; SFG(S)

82



Fin faux

TQ non fin faire

Si FG(Q) =Nil alors


Chaîner (R, P, Q, Nil); Fin vrai


Chaîner (R, P, Q, FD(Q)); Fin vrai

Sinon


Chaîner (R, P, Q, FG(Q)); Fin vrai



Aff_Info (Q, Info(S))

QS; PPS; xInfo(S)

FTQ

LibererNoeud(Q)

FSI

Retourner (R)

83


Fonction SupprimerABR_rec (R:*Tnoeud, x: entier) : * Tnoeud

Debut

Si R =Nil alors

Retourner (R)

Sinon

Si Info(R)>x alors

Aff_FG(R, SupprimerABR_rec(FG(R), x))

Retourner (R)

Sinon

Si Info(R)<x alors

Aff_FD(R, SupprimerABR_rec(FD(R), x))

Retourner (R)

Sinon // Info(R) = x

Retourner (SupprimerRacine (R))

Fin

84


Fonction SupprimerRacine (R:*Tnoeud) : * Tnoeud Debut

Si FG(R) =Nil alors

Si FD(R) =Nil alors //Cas n°1: R est une feuille

LibérerNoeud(R)

Retourner (Nil) Sinon //Cas n°2: R possède un FD

DFD(R)

LibérerNoeud(R)

Retourner (D)

Sinon Si FD(Q) =Nil alors //Cas n°2: R possède un FG

GFG(R)

LibérerNoeud(R)

Retourner (G)

Sinon // Cas n°3: R possède deux fils SSuccesseur (R)

Aff_Info (R, Info(S))

Aff_FD(R, SupprimerABR_rec(DF(R), Info(S)))

Retourner (R)

Fin

85

EXEMPLE D’APPLICATION: TRI PAR ABR

Exercice 10: Étant donné un tableau d’entiers T (n: sa

taille), dire comment peut on trier ce tableau en utilisant

un Arbre Binaire de Recherche (ABR)?

Exemple:

20 15 10 35 19 13 5 3 12 7 16 40 25 38

86

1. Insérer toutes les éléments du tableau dans un

ABR

20 15 10 35 19 13 5 3 12 7 16 40 25 38

20

15 35

10

19

5 13

3 7 12

25 40

38

16


87

2. Parcourir l’ABR en inordre : GRD

3 5 7 10 12 13 15 16 19 20 25 35 38 40

20

15 35

10

19

5 13

3 7 12

25 40

38

16


88

Procedure Tri_ARB(Var T: Tableau, n: entier)

Debut

RNil

Pour i0 à n-1 faire RInsererABR (R, T[i]).

Inordre (R, T); //Parcours Infixe

Fin


Indice est une variable globale initialisée à 0

Procedure Inordre (R: *Tnœud, Var T: Tableau)

Si ( R Nil) alors //Arbre n’est pas vide

Inordre(FG(R), T))

T[indice]Info(R) //Écrire la valeur dans le tableau

indice++

Inordre(FD(R), T)

PARTIE IV:

ARBRES BINAIRES DE

RECHERCHE ÉQUILIBRÉS

(ARBRES AVL)

Introduction

Définition

Techniques d’équilibrage

Opérations de Base: Recherche, Insertion et

Suppression 90

PLAN DE LA PARTIE IV

91

INTRODUCTION

La complexité au meilleur des cas de la recherche, de

l’insertion et de la suppression dans un ABR est O(h), où

h est la hauteur (ou profondeur) de l’arbre. Ce cas est

atteint par des arbres équilibrés

Cependant, la complexité au pire cas pour un arbre à n

nœuds, est O(n). Ce cas est atteint par des arbres très

déséquilibrés, ou «filiformes».

Plusieurs espèces des arbres équilibrés ont été

développés: les arbres AVL, les arbres 2-3, les arbres

rouge et noir, etc.

92

INTRODUCTION

O (n) O (h) tel que h = log2(n)

87 ?

ABR Equilibré Filiforme

93

DÉFINITION

Les arbres AVL ont été introduits par les finlandais Adelson-

Velskii et Landis dans les années 60.

Un arbre AVL est un ABR équilibré dont:

la différence de hauteur (ou profondeur) entre le sous-

arbre gauche et le sous-arbre droit d'un nœud « R » diffère

d'au plus 1.

|Profondeur(FG(R) ) – Profondeur(FD(R)) | ≤ 1

les arbres gauches et droits d'un nœud sont des arbres

AVL.

Un champs supplémentaire est ajouté à tous les nœuds: c’est le

facteur de déséquilibre (appelé aussi facteur de balance «

Bal ») qui est calculé après chaque insertion/suppression.

94

EXEMPLE

100

50

30 80

200

10

150

40

Exemple: soit l’ABR suivant. Est-il un arbre AVL?

+1

+1 +1

0 0 0

0

Notons:

que l’arbre vide a la

hauteur −1,

Et qu’une feuille est un

arbre de hauteur 0.

L’arbre vide et l’arbre

réduit à une feuille,

sont des arbres AVL

Cet arbre est un arbre AVL

À vérifier pour chaque nœud R, on a:

| Profondeur(FG(R) ) – Profondeur(FD(R)) | <= 1

0

95

EXEMPLE

Exemple: Cet ABR est un arbre AVL avant insertion

Insérer la valeur 5 100

50

30 80

200

10

150

40

Cet arbre n’est pas un arbre AVL après insertion de 5

arbre déséquilibré

5 0

+1

+1

0

+1

0 0

+2 Après insertion, calculer le

facteur de déséquilibre de

chaque nœud.

96

EXEMPLE

Exemple: Cet ABR est un arbre AVL avant insertion

Insérer la valeur 45

Cet arbre n’est pas un arbre AVL après insertion de 45

arbre déséquilibré

100

50

30 80

200

10

150

40

45 0

0

-1

-1

+1

0 0

+2

97

TECHNIQUES D’ÉQUILIBRAGE

L’opération d’équilibrage, appelée rotation, s’applique à tous les

arbres binaires.

Le but des rotations est de pouvoir rééquilibrer un ABR.

On opère donc une rotation gauche lorsque l’arbre est

«déséquilibré à droite», i.e. son sous-arbre droit est plus haut

que son sous-arbre gauche.

On opère une rotation droite dans le cas contraire à savoir son

sous-arbre gauche est plus haut que son sous-arbre droit.

Les rotations ne sont donc définies que pour les arbres binaires non

vides dont le sous-arbre gauche (pour rotation gauche) et sous-arbre

droit (pour rotation droite) n’est pas vide.

Les rotations préservent l’ordre des données d’un ABR (parcours

inordre).

98


Rotation simple : Rotation droite

Soit A=(B, R, Z) un arbre binaire tel que B=(X, P, Y).

La rotation droite est l’opération:

((X, P, Y), R, Z) → (X, P, (Y, R, Z))

R

P

X (hauteur

h+1/h)

Déséquilibre gauche

Y (hauteur

h/h)

Z (hauteur

h/h-1)

P

R

X (hauteur

h+1/h)

Y (hauteur

h/h)

Z (hauteur

h/h-1)

+1 ou 0

+2 0 ou -1

0 ou 1

Rotation droite

99


Rotation simple : Rotation gauche

Soit A=(X, R, B) un arbre binaire tel que B=(Y, P, Z).

La rotation gauche est l’opération:

( X, R, (Y, P, Z)) → ((X, R, Y), P, Z)

P

R

X (hauteur h/h-1)

Y (hauteur h)

Z (hauteur

h+1/h)

R

P

Déséquilibre droit

X (hauteur

h/h-1) Y (hauteur

h) Z

(hauteur

h+1/h)

-1 ou 0

-2

0 ou -1

0 ou +1 Rotation gauche

100


Rotation double : double rotation gauche-droite

C’est une rotation gauche sur le sous arbre-gauche du nœud R

suivie d’une rotation droite sur le nœud R

P

Q

R

D(h)

C B

A (h)

Q

P

R

D (h)

C

B A (h)

Rotation gauche Rotation droite

Q

P R

D (h)

C B A (h)

((A, P, (B, Q, C)), R, D) → (((A, P, B), Q, C), R, D) → ((A, P, B), Q, (C, R, D))

-1

+2

0 +2

101


Rotation double : double rotation droite-gauche

C’est une rotation droite sur le sous arbre-droit du nœud R suivie

d’une rotation gauche sur le nœud R

Rotation droite Rotation gauche

(A, R, ((B, Q, C), P, D)) → (A, R, (B, Q, (C, P, D))) → ((A, R, B), Q, (C, P, D))

P

Q

R

A (h)

+1

-2

B C

D (h)

Q

P

R

-2

A (h)

B

C D (h)

Q

R P

0

A (h)

B C D (h)

102

OPERATIONS DE BASE

La recherche est identique à celui des ABR car les

arbres AVL sont avant tout des ABR équilibrés.

L’insertion d’un élément dans un arbre AVL peut

provoquer un déséquilibre. Donc, pour rétablir l’équilibre

(rééquilibrer) de l’arbre après une insertion, une seule

rotation (simple ou double) suffit.

La suppression d’un élément dans un arbre AVL peut

provoquer un déséquilibre. Donc pour rétablir l’équilibre

(rééquilibrer) de l’arbre après une suppression, il faut

faire entre 1 et h rotations (h est la hauteur de l’arbre).

103

INSERTION

L’ajout d’un nœud se fait toujours au niveau d’une feuille,

puis on rééquilibre l’arbre AVL si l’insertion a

déséquilibré l’arbre.

Le déséquilibre est rencontré lorsque le facteur

d’équilibrage d’un nœud de l’arbre égale à ± 2.

104

INSERTION

Exemple: soit la série de nombres à insérer dans un

arbre AVL (2 10 12 4 16 8 6 14 )

2 10 12 4 16 8 6 14

2 0

2 10 12 4 16 8 6 14

2

10 0

-1

2 10 12 4 16 8 6 14

2

10

12 0

-1

-2

Rotation simple

10

12 2 0 0

0

105

INSERTION


arbre AVL (2 10 12 4 16 8 6 14 )

2 10 12 4 16 8 6 14

10

12 2

4 0

-1 0

1

2 10 12 4 16 8 6 14

10

12 2

4 16 0 0

-1 -1

0

106

INSERTION


arbre AVL (2 10 12 4 16 8 6 14 )

2 10 12 4 16 8 6 14

10

12 2

4 16

8 0

-1

-2

0

-1

1

Rotation

simple

10

12 4

8 16 2 0 0 0

-1 0

0

107

INSERTION


arbre AVL (2 10 12 4 16 8 6 14 )

2 10 12 4 16 8 6 14

10

12 4

8 16 2

6 0

1 0

-1

0

-1

1

108

INSERTION


arbre AVL (2 10 12 4 16 8 6 14 )

2 10 12 4 16 8 6 14

10

12 4

8 16 2

6 14 0

0

1

-2

1 0

-1

0

Rotation

double

10

14 4

8 16 2

6

12

0

1

0 0

0 -1

1

0

109

INSERTION

Exemple 2: soit l’arbre suivant, donner le résultat après

insertion de 7

10

14 4

8 16 2

6

12

1 9

110

INSERTION

Exemple 2: soit l’arbre ci-dessus, donner le résultat

après insertion de 7

0

10

14 4

8 16 2

6

12

-1

1

0 0

0

1

-1

2

1 0 9 0

7

Nœud inséré

10

14

4

8

16

2 6

12

-1

0

0 1

-1

1 0

9

0 7 0

0

0

0

Rotation

double

111

Exercice 06 :

1. Soit R un arbre AVL


25, 60, 35, 10, 5, 20, 65, 45, 70, 40, 50, 55, 30, 15

b. Ajouter à l'arbre obtenu et dans l'ordre, les

éléments suivants : 22, 62, 64, 4, 8

c. Supprimer de l'arbre obtenu et dans l'ordre les éléments

suivants : 15, 70, 50, 35, 60, 25

OPÉRATION DE MISES À JOURS SUR LES AVL

112

INSERTION

R

h

h

R

h

h+1

R

h

h+1

R

h

h+2

R

h

h+1

R

h+1 h+1

R

h

h+2

R

h+1 h+1

R

h

h+1

0

+1

-1

+1

+2

0

-1

0

-2

Avant Après insertion à gauche Après insertion à droite

Cas A

Cas B

113

INSERTION

Remarques:

Après une insertion, seules les nœuds qui sont sur le chemin du

point d’insertion à la racine sont susceptibles d’être déséquilibrés.

Cas A: L’arbre devient non équilibré quand le nouveau nœud

inséré est un descendant gauche d’un nœud qui avait un facteur

d’équilibrage égal à 1

Cas B: L’arbre devient non équilibré quand le nouveau nœud

inséré est un descendant droit d’un nœud qui avait un facteur

d’équilibrage égal à -1

114

INSERTION

R

h

h+2

+2

R

h

+1

P

h

h

0

Cas A

Si insertion dans le sous-arbre

gauche du fils gauche alors

Rotation Simple à droite

Si insertion dans le sous-arbre droit

du fils gauche alors Rotation

Double Gauche-Droite

R

h

+2

P

h

+1

h+1

R

h

+2

P

h

-1

h+1

Avant

115

INSERTION R

h

h+2

-2 Cas B

R

h

-1

P

h

h

0

R

h

P

h

-2

+1

h+1

R

h

P

h

h

-2

-1

Si insertion dans le sous-arbre

droit du fils droit alors Rotation

Simple à gauche

Si insertion dans le sous-arbre gauche

du fils droit alors Rotation Double

Droite-Gauche

Avant

116

SUPPRESSION

Le principe de la suppression d’un élément dans un arbre

AVL est le même que dans un ABR, c.à.d. recherche de

l’élément à supprimer, suppression et remplacement, le

cas échéant, par l’élément qui lui immédiatement

inférieur ou supérieur.

Après la première phase de la suppression, la hauteur de

l’arbre est diminué de 1. Le problème est que cet arbre

n’est plus forcément un arbre AVL. Il faut donc le

rééquilibrer.

117

SUPPRESSION

S’il y a déséquilibre, la rotation appliquée peut diminuer

à son tour la hauteur de l’arbre et générer un nouveau

déséquilibre. En fait les rotations peuvent s’enchainer en

cascade depuis l’élément supprimé jusqu’à la racine.

Ainsi, on peut faire jusqu’à h (hauteur de l’arbre initial)

rotations (simple ou double).

118

SUPPRESSION

Exemple: soit l’arbre suivant. Donner le résultat après la

suppression de 10:

10

14

4

8

16

2 6

12

-1

0

0 1

-1

1 0

9

0 7 0

0

0

0

12

14

4

8

16

2 6 -1

-1 1

-1

1 0

9

0 7 0

0

0

0 Remplacer par le successeur

119

SUPPRESSION


suppression de 8:

12

14

4

8

16

2 6 -1

-1 1

-1

1 0

9

0 7 0

0

0

0

12

14

4

9

16

2 6 -1

-1 1

-2

1 0 0 7 0

0

0 Remplacer par le successeur

120

SUPPRESSION


suppression de 8:

12

14

4

9

16

2 6 -1

-1 1

-2

1 0 0 7 0

0

0

14

12

4

9

16 2 6 -1

0 1

0

1 0 0 7

0

0

1

RSG

121

SUPPRESSION


suppression de 12 puis 16:

14

12

4

9

16 2 6 -1

0 1

0

1 0 0 7

0

0

1

14 4

9

2 6 -1 1

0

1 0 0 7

0

+2

122

SUPPRESSION


suppression de 12 puis 16:

14 4

9

2 6 -1 1

0

1 0 0 7

0

+2

9

4

14

2

6 -1

1 1

1 0

0

7

0

-1

RSD

123

SUPPRESSION


suppression de 30:

100

200

30

50

300

10 40 -1

-1

+1

20

80

60

0

+1

+1

-1

90 70 +1

0

0 0

0

40

50

300

10 -1

-1

+1

20

80

60

+2

+1

-1

90 70

+1

100

200

0

0

0 0

Remplacer par le successeur

124

SUPPRESSION


suppression de 30:

40

50

300

10 -1

-1

+1

20

80

60

+2

+1

-1

90 70

+1

100

200

0

0

0 0

RDG-D

20

50

300

10 -1

+1

40 80

60

0

0

+1

-2

90 70 +1

100

200

0 0

0

0

125

SUPPRESSION


suppression de 30:

RDD-G

20

50

300

10 -1

+1

40 80

60

0

0

+1

-2

90 70 +1

100

200

0 0

0

0

20

80

300 10

-1

-1

40

50

60

0

0

90 70 +1

100

200

0

0 0 0

0

0

126

Exercice 06 :

1. Soit R un arbre AVL


25, 60, 35, 10, 5, 20, 65, 45, 70, 40, 50, 55, 30, 15

b. Ajouter à l'arbre obtenu et dans l'ordre, les éléments

suivants : 22, 62, 64, 4, 8

c. Supprimer de l'arbre obtenu et dans l'ordre les

éléments suivants : 15, 70, 50, 35, 60, 25

OPÉRATION DE MISES À JOURS SUR LES AVL

127

Exercice 11 :

Un arbre AVL est un ABR équilibré dont tous les nœuds

possèdent, entre autre Info, FG et FD, un facteur de

déséquilibre (appelé Bal pour balance) qui est calculé après

chaque insertion/suppression.

1. Définir la structure d’un arbre AVL (TnoeudAVL).

2. Donner l’implémentation dynamique du modèle de l’arbre

AVL, notamment les modules suivants : CreerNoeud (P :

*TnoeudAVL, x : entier), Aff_Bal(Var P :*TnoeudAVL, b :

entier), Balance (P : *TnoeudAVL) : entier,

ALGORITHMES SUR LES AVL

128

Exercice 11 :

3. Développer les modules suivants permettant de

manipuler un arbre AVL:


Module Rôle

Procédure MAJ_Bal(Var R : *TnoeudAVL)

mettre à jour (calculer) le champs Bal du nœud R

Fonction RSG (R : * TnoeudAVL) : *TnoeudAVL

faire une Rotation Simple à Gauche de l’arbre R

Fonction RSD (R : * TnoeudAVL) : *TnoeudAVL

faire une Rotation Simple à Droite de l’arbre R

Fonction RDG-D (R : * TnoeudAVL) : *TnoeudAVL

faire une Rotation Double Gauche-Droite de l’arbre R

Fonction RDD-G (R : * TnoeudAVL) : *TnoeudAVL

faire une Rotation Simple Double Droite-Gauche de l’arbre R

Fonction Reequilibrer (R : *TnoeudAVL) : *TnoeudAVL

rééquilibrer l’arbre R

129

Exercice 11 :

4. En modifiant les algorithmes d’insertion/suppression

dans un ABR, trouver les algorithmes récursifs

d'insertion/suppression dans un AVL.


130

ALGORITHMES SUR LES AVL STRUCTURE DE DONNÉES

Un champs supplémentaire est ajouté à tous les nœuds:

c’est le facteur de déséquilibre (appelé aussi facteur de

balance « Bal ») qui est calculé après chaque

insertion/suppression Structure de Données

TYPE Tnoeud AVL= STRUCTURE

Info : entier

Bal: entier

FG : * TnoeudAVL

FD : * TnoeudAVL

FIN

VAR R: * TnoeudAVL

131


MODÈLE

Comparativement au modèle ABR, on modifie la fonction

CreerNoeud et on ajoute deux autres modules pour lire et écrire

dans le nouveau champs « Bal »:

Fonction Rôle

balance(p) permet d'accéder à l'information du nœud p

Retourner (*p.Bal);

Aff_bal(p, b) permet de modifier l'information du nœud p

*p.Bal b;

Créer_noeud(x)

permet de créer un nœud avec x comme information et retourne la référence du nœud. Le nœud créé a Nil comme fils

gauche et droit.

Allouer (P); aff_info(P, x); aff_FG(P, Nil); aff_FD(P, Nil);

Aff_bal(P, 0); retourner (P)

132


MAJ LA BALANCE

La balance ou le facteur de déséquilibre est définie

comme suit:

Profondeur(FG(R) ) – Profondeur(FD(R))

Procédure MAJ_Bal (Var R: *TnoeudAVL)

Début

Si (R ≠ Nil ) alors

Aff_Bal (R, Profondeur (FG(R) – Profondeur (FD(R))

Fin

133

ALGORITHMES SUR LES AVL TECHNIQUES D’ÉQUILIBRAGE

Rotation simple : Rotation gauche

P

R

X (hauteur h

ou h-1)

Y (hauteur h)

Z (hauteur

h+1 ou h)

R

P

X (hauteur

h ou h-1) Y (hauteur

h) Z

(hauteur

h+1 ou h)

-1 ou 0

-2

0

0 Rotation gauche

Fonction RSG (R: *TnoeudAVL): *TnoeudAVL

P FD(R); Y FG(P); Aff_FD(R, Y); Aff_FG(P, R)

MAJ_Bal (R); MAJ_Bal (P)

Retourner (P)

134

Rotation simple : Rotation droite

R

P

X (hauteur

h+1 ou h)

Y (hauteur

h)

Z (hauteur

h ou h-1)

P

R

X (hauteur

h+1 ou h)

Y (hauteur

h)

Z (hauteur

h ou h-1)

+1 ou 0

+2 0 ou -1

0 ou +1

Rotation droite

Fonction RSD (R: *TnoeudAVL): *TnoeudAVL

P FG(R); Y FD(P); Aff_FG(R, Y); Aff_FD(P, R)

MAJ_Bal (R); MAJ_Bal (P)

Retourner (P)


135


P

Q

R

D

C B

A

Q

P

R

D

C

B

A

Rotation gauche Rotation droite

Q

P R

D C

B

A

-1

+2

1ère méthode

Fonction RDG-D (R: *TnoeudAVL): *TnoeudAVL

P FG(R); Q RSG(P); Aff_FG(R, Q); QRSD(R)

Retourner (Q)


136


P

Q

R

D

C B

A

Q

P R

D

C

B

A

-1

+2

2ère méthode

Fonction RDG-D (R: *TnoeudAVL): *TnoeudAVL

P FG(R); Q FD(P); B FG(Q); C FD(Q);

Aff_FD(P, B); Aff_FG(R, C); Aff_FG(Q, P); Aff_FD(Q, R)

MAJ_Bal (R); MAJ_Bal (P); MAJ_Bal (Q);

Retourner (Q)


137


Rotation droite Rotation gauche

P

Q

R

A +1

-2

B C

D

Q

P

R

A

B

C

D

Q

R P

A B C D

1ère méthode

Fonction RDD-G (R: *TnoeudAVL): *TnoeudAVL

P FD(R); Q RSD(P); Aff_FD(R, Q); QRSG(R)

Retourner (Q)


138


P

Q

R

A +1

-2

B C

D

Q

R P

A B C D

2ère méthode

Fonction RDD-G (R: *TnoeudAVL): *TnoeudAVL

P FD(R); Q FG(P); B FG(Q); C FD(Q);

Aff_FG(P, C); Aff_FD(R, B); Aff_FG(Q, R); Aff_FD(Q, P)

MAJ_Bal (R); MAJ_Bal (P); MAJ_Bal (Q);

Retourner (Q)


139


OPÉRATION DE RÉÉQUILIBRAGE Fonction Reequilibrer (R:*TnoeudAVL) : * TnoeudAVL

Debut

MAJ_Bal (R)

Si Balance (R) = +2 alors

P FG(R)

Si Balance (P) = -1 alors

RRDG-D(R)

Sinon // Balance (P) = 0 ou +1

RRSD(R)

Sinon

Si Balance (R) = -2 alors

PFD(R)

Si Balance (P) = +1 alors

RRDD-G (R)

Sinon // Balance (P) = 0 ou -1

RRSG(R)

Retourner (R)

Fin

140



Fonction InsererAVL_rec (R:*TnoeudAVL, x: entier) : * TnoeudAVL

Debut

Si R = Nil alors

RCreerNoeud(x)

Sinon

Si Info(R)>x alors

Aff_FG(R, InsererAVL_rec(FG(R), x))

Sinon

Aff_FD(R, InsererAVL_rec(FD(R), x))

Retourner (Reequilibrer (R))

Fin

141



Fonction SupprimerAVL_rec (R:*TnoeudAVL, x: entier) : *

TnoeudAVL

Debut

Si R = Nil alors

Retourner (Nil)

Sinon

Si Info(R)>x alors

Aff_FG(R, SupprimerAVL_rec(FG(R), x))

Sinon

Si Info(R)<x alors

Aff_FD(R, SupprimerAVL_rec(FD(R), x))

Sinon // Info(R) = x

RSupprimerRacine (R)

Retourner (Reequilibrer (R))

Fin

SOURCES DE CE COURS

N. EL-ALLIA , Cours d’Algorithmique et Structures de données dynamiques, Ecole

nationale Supérieure d’Informatique (ESI), 2014.

Djamel Eddine ZEGOUR, Cours de Structures de Données, Ecole nationale

Supérieure d’Informatique (ESI), Disponible sur

http://zegour.esi.dz/Cours/Cours_sdd.htm

W. K. Hidouci, Cours Structures De Données et Fichiers, École nationale Supérieure

d’Informatique, Disponible sur hidouci.esi.dz/algo/

B. Boutoumi, Cours d’Algorithmique et Structures de données, Université Saad

Dahlab de Blida, 2014, Disponible sur https://sites.google.com/a/esi.dz/s-

aroussi/algorithmique-et-structure-de-donnees/nouveau-programme .

A. Aroussi, Cours d’Algorithmique Avancé, Université Saad Dahlab de Blida, 2015,

Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/Algorithmique

A. Aroussi, Cours d’Algorithmique et Structures de données, Université Saad Dahlab

de Blida, 2013, Disponible sur https://sites.google.com/a/esi.dz/s-

aroussi/algorithmique-et-structure-de-donnees/annee-universitaire-2014-

2015/ancien-programme

142










http://www.zegour.netii.net/Site secondaire/Mcp/Cours ppt/1_o-notation.pdf hidouci.esi.dz/algo/cours_recursivite.pdf







https://sites.google.com/a/esi.dz/s-aroussi/algorithmique-et-structure-de-donnees/nouveau-programme





















https://sites.google.com/a/esi.dz/s-aroussi/Algorithmique











https://sites.google.com/a/esi.dz/s-aroussi/algorithmique-et-structure-de-donnees/annee-universitaire-2014-2015/ancien-programme





























Education

Chapitre 5 arbres binaires