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/

Introduction

Définitions et Terminologies

Les Arbres Binaires

Les Arbres Binaires de Recherche (ABR)

Les Arbres AVL

PLAN DU CHAPITRE V

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

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

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

C1 C2 C3

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

S2.1.1 S2.1.2

Hiérarchies de fichiers,

INTRODUCTION

etc/ var/ tmp/

run/rc.d/ apache/

httpd.conf

inet.conf

rc.localrc.inet1

Expressions Arithmétiques

INTRODUCTION

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

se représente facilement par un arbre

où apparaît clairement la priorité des

opérations:

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.

E G H F I

Nœuds Arêtes

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).

E G H F I

Racine

Nœud interne

Feuilles

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.

E G H F I

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-D-G-J

E G H F I

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.

E G H F I

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

E G H F I

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

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

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

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

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

E G H F I

Niveaux

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

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

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

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

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

E G H F I

Niveaux

Forêt : est un ensemble d'arbres.

Définition récursive

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

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

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

racine

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

racine

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)

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ÉFINITION

Un arbre binaire complet est un arbre strictement binaire où

toutes les feuilles sont au même niveau.

Dans l’exemple ci dessous:

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

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

VAR Arbre : * Tnoeud

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.

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

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

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).

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

Sous arbre gauche G Sous arbre droit D

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]

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]

E G D F

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

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) )

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 ]

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 ]

E G D F

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

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) )

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]

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]

E G D F

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

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) )

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).

Exercice 02: Trouver les algorithmes itératifs du

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

un arbre binaire

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

E G D F

H I D E B F G A C

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;

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));

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

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

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

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

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

PLAN DE LA PARTIE III

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 ».

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

PARCOURS

Exemple: Appliquer les différents parcours vus sur

l’ABR suivant:

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

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

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é

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é

Exercice 07 : Trouver les algorithmes (récursifs et

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

dans un Arbre Binaire de Recherche (ABR).

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

Si R =Nil alors

Retourner (Nil)

Si Info (R) = x alors

Retourner (R)

Si Info(R)>x alors

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

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

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

TQ R ≠Nil faire

Retourner (R)

Si Info(R)>x alors

RFG(R)

RFD(R)

Retourner (Nil)

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

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

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

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

Si R =Nil alors

RCreerNoeud(x)

Si Info(R)>x alors

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

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

Retourner (R)

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

Var P, Q: *Tnoeud

PCreerNoeud(x)

Si R =Nil alors

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)

Si FD(R)=Nil alors

Aff_FD(R, P); inserer vrai

Sinon RFD(R)

Retourner (R)

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 :

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 »

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 »

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 »

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.

Le plus proche prédécesseur

Le plus proche successeur

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

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

petit du sous-arbre)

Racine: 71

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

RFD(R)

Si R≠Nil alors

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

Retourner (R) Fin

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

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

grand du sous-arbre gauche).

Racine: 50

Fonction Predecesseur (R: *Tnoeud): *Tnoeud

RFG(R)

Si R≠Nil alors

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

Retourner (R) Fin

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

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

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

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

≠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 »

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

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

Var P, Q: *Tnoeud

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

PèreR

Si Info(R)>x alors

RFG(R)

RFD(R)

Cette procédure

retourne l’adresse du

nœud contenant x

(soit Q) ainsi que

l’adresse de son père

(soit Père)

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

Var P, Q: *Tnoeud

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))

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

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

Var P, Q: *Tnoeud

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

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

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

Aff_FG(PèreQ, FilsQ)

Aff_FD(PèreQ, FilsQ)

Var P, Q: *Tnoeud

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

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)

Var P, Q: *Tnoeud

Si FG(Q) =Nil alors

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

Si (S≠Nil) alors

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

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

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

Aff_Info (Q, Info(S))

QS; PPS; xInfo(S)

LibererNoeud(Q)

Retourner (R)

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

Si R =Nil alors

Retourner (R)

Si Info(R)>x alors

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

Retourner (R)

Si Info(R)<x alors

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

Retourner (R)

Sinon // Info(R) = x

Retourner (SupprimerRacine (R))

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)

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

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

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

3 7 12

2. Parcourir l’ABR en inordre : GRD

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

3 7 12

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

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

Inordre (R, T); //Parcours Infixe

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

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.

INTRODUCTION

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

ABR Equilibré Filiforme

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

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.

EXEMPLE

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

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

EXEMPLE

Exemple: Cet ABR est un arbre AVL avant insertion

Insérer la valeur 5 100

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

arbre déséquilibré

+2 Après insertion, calculer le

facteur de déséquilibre de

chaque nœud.

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é

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).

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))

X (hauteur

h+1/h)

Déséquilibre gauche

Y (hauteur

Z (hauteur

h/h-1)

X (hauteur

h+1/h)

Y (hauteur

Z (hauteur

h/h-1)

+1 ou 0

+2 0 ou -1

0 ou 1

Rotation droite

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)

X (hauteur h/h-1)

Y (hauteur h)

Z (hauteur

h+1/h)

Déséquilibre droit

X (hauteur

h/h-1) Y (hauteur

(hauteur

h+1/h)

-1 ou 0

0 ou -1

0 ou +1 Rotation gauche

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

B A (h)

Rotation gauche Rotation droite

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))

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))

C D (h)

B C D (h)

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).

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.

INSERTION

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