Arbres

• Un arbre est une structure de données

organisées de façon hiérarchique, à partir d’un
nœud distingué appelé racine.
• Très importante en informatique!.
• Arbre de jeux (i.e., Echecs ), système de fichiers
UNIX/Windows, Arbres de tri etc.
• Nous étudierons deux types d’arbres : Arbre
Binaires de Recherches et Arbres équilibrés
1
 Arbres: définitions
• Un arbre est un ensemble de Nœuds, reliés par
des Arêtes. Entre deux nœuds il existe toujours
un seul chemin.

noeuds

arêtes
2
 Arbres: définitions
• Les arbres sont enracinés. Une fois la racine définit tous les
nœuds admettent un niveau.
• Les arbres ont des noeuds internes et des feuilles (nœuds
externes). Chaque noeud (à l’exception de la racine) a un
parent et admet zéro ou plusieurs fils.
racine
niveau 0
niveau 1 nœuds internes
niveau 2
parent
niveau 3 et
feuilles fils 3
 Arbres binaires
• Un Arbre Binaire est un arbre où chaque
nœud admet au plus 2 fils.

4
 Arbres Binaires: définitions
• Nœuds d’un arbre contiennent des clés (mots, nombres,
etc)
• Arbre Binaire parfait : les feuilles sont toutes situées
dans les deux derniers niveaux. Les feuilles du dernier
niveau sont toutes à gauche.
14

10 16

8 12 15 18
7 9 11 13 5
Arbres Binaires: représentation par
tableaux
• Un arbre binaire complet peut être
représenté par un tableau A avec un accès
en O(1) à chaque noeud:

– Mémoriser les neouds séquentiellement de la

racine aux feuilles et de gauche vers la droite.
– Fils gauche de A[i] est en A[2i]
– Fils droit de A[i] est en A[2i + 1]
– Parent de A[i] est en A[i/2]
6
Arbres Binaires: représentation par
tableau
1
14
2 3
10 16
4 5 6 7
8 12 15 18
8 9 10 11
7 9 11 13

1 2 3 4 5 6 7 8 9 10 11
tab A: 14 10 16 8 12 15 18 7 9 11 13
7
Arbres Binaires: représentation par
pointeurs
typedef struct n{
int clé;
struct n *fGauche, *fDroit;
}nœud;

typedef nœud * Arbre;

8
 Parcours : inOrdre
InOrdre est décrit réursivement :
• Visiter le sous-arbre gauche en InOrdre
• Visiter la racine
• Visiter le sous-arbre droit en InOrdre

9
 Parcours : préOrdre
PréOrdre est décrit réursivement :
• Visiter la racine
• Visiter le sous-arbre gauche en PréOrdre
• Visiter le sous-arbre droit en PréOrdre

10
 Parcours: non-récursif
PréOrdre itératif en utilisant une Pile.

Pile S
empiler racine dans S
répéter jusqu’à S=
v = dépiler S
si v <> nil
visiter v
empiler le fils droit de v dans S
empiler le fils gauche de v dans S

11
 Parcours: postOrdre
PostOrdre est décrit réursivement :

• Visiter le sous-arbre gauche en PostOrdre

• Visiter le sous-arbre droit en PostOrdre
• Visiter la racine

12
 Parcours: levelOrdre
LevelOrdre visite les noeuds niveau par niveau depuis la racine:
• Peut être décrit facilement en utilisant une File
(Comment??)
• Parcours appelé “Breadth First Search” (parcours en largeur)
dans les graphes

13
 Arbre Binaire de Recherche
• Un Arbre Binaire de Recherche (ABR) est
un arbre binaire avec les propriétés suivantes :

– La clé associée à un noeud est supérieur aux clés

des nœuds de son sous-arbre gauche

– La clé associée à un noeud est inférieur aux clés

des nœuds de son sous-arbre droit
14
Arbre Binaire de Recherche:
Exemples
racine
racine
14
C
10 16
A D
racine
8 11 15 18
14

10 16

8 11 15
15
 Arbre Binaire de Recherche
• ABR est un arbre avec la propriété suivante :
Clé.fGauche < Clé.parent <
Clé.fDroit

NOTER! Le parcours InOrdre visite les clés dans

l’ordre croissant.
void inOrdre(Arbre racine) {
inOrdre(racine->fGauche)
print(racine->key)
inOrdre(racine->fDroit)
} 16
 ABR: InOrdre
Exemple:

InOrdre visites :
14
(8)
(10)
10 16 (11)
(14)
8 11 15 18
(15)
(16)
(18)

17
 ABR : Rechercher un élément
Soit un ABR :

G D

Problème: rechercher un noeud avec une clé x ?

18
 ABR : Rechercher un élément
rechercher(racine, x) Exemple:
comparer x à la clé de racine:
14
- si x = clé return
- si x < clé => chercher dans G
10 16
- si x > clé => chercher dans D
8 11 15
chercher de la même manière
dans G ou D

x=8 (oui) x=17 (non)

19
 ABR : Rechercher un élément
bool searchABR(Arbre racine; typeCle clé){
if (racine==NULL) return false
if (racine->clé==clé)
return true;
else if (key < racine->clé)
return searchABR(racine->fGauche, clé);
else
return searchABR(racine->fDroit, clé)
}

Donner une version itérative ?

20
 ABR : Ajout d’un élément
Comment ajouter une clé? Exemple:

La même procédure que 10

searchABR s’applique:
Déterminer la position 8 ajout 4?
d’insertion par searchABR.
3 9 4
Ajouter la nouvelle clé si la
recherche échoue.
2 5

21
 Construction d’un ABR
Exemple: ajouter C A B L M (dans l’ordre!)

1) Ajouter C 2) ajouter A 3) ajouter B C

C
C A
A
B
4) Ajouter L C 5) Ajouter M
C
A L
A L
B 22
B M
 Construction d’un ABR
L’ABR est-il unique pour une séquence de
lettres A B C L M ?
NON! différentes séquences donnent
différents ABR
Ajout de : A B C L M Ajout de : C A B L M
A
C
B
C A L

L B M
23
M
 Trier avec un ABR
Soit un ABR, peut-on afficher les Example:
clés dans l’ordre?
Visiter l’ABR avec un parcours C
InOrdre:
- visiter le sous-arbre gauche A L
- afficher racine
B M
- visiter le sous-arbre droit

InOrdre affichage:
Comment trouver le minimum?
A B C L M
Comment trouver le maximum?
24
 ABR : supprimer un élément
Pour supprimer un nœud contenant x,
rechercher x, une fois trouvé appliquer l’un des trois
cas suivants:

CAS A: x est une feuille

p p
q q

r x r

supprimer x On obtient un ABR 25

 ABR : supprimer un élément
Cas B: x est un nœud interne avec un seul
sous-arbre

r r

x
q
q
suppr x L
L
On obtient un ABR 26
 ABR : supprimer un élément
Cas C: x est un nœud interne avec 2 sous-arbres

r
r
u suppr x
x suppr x
q u s Z
q
W Z
W t
ts
27
propriété ABR est conservé
 ABR : supprimer un élément
Cas C suite: … ou encore comme suit

q < x < u
r  q est inférieur au plus petit
élément de Z
q  r est supérieur au plus grand
W t élément de W
u

s Z D’autres façon ?
28
ABR : Compléxité de rechercher
• Quelle est la compléxité de searchABR ?
• Dépend de :
– la clé x
– des autres données
– De la forme de l’arbre

Analyse de la compléxité : On est intéréssé par

la compléxité dans le meilleur cas, pire cas et
en moyenne 29
 ABR : Compléxité de rechercher
niveau 0

niveau 1

niveau 2

niveau 3 (h =3)
• hauteur d’un ABR = niveau max
• hauteur d’un noeud
h(x) = 0 si x est la racine
h(x) = 1+ h(y), y = pere(x)
• hauteur d’un ABR B : h(B) = max{h(x), x nœud de B} 30
 ABR : Compléxité de rechercher

Si tout les nœuds de l’arbre Si tout les nœuds existent sauf

existent : ABR plein ceux du dernier niveau :
niveau-min ABR

31
 ABR : Compléxité de rechercher

Théorème: h+1
Un ABR plein (complet) de hauteur h a 2 - 1 noeuds
Preuve: Par induction

Cas de base: un arbre de hauteur 0 a 1 nœud (racine)

Hypothèse inductive: Supposant qu’un ABR de hauteur h a

h+1
2 - 1 noeuds
32
 ABR : Compléxité de rechercher
Etape d’induction: Connecter 2 ABR de hauteur h pour
construire un ABR de hauteur h+1. On a besoin d’ajouter
un noeud supplémentaire racine

h+1
h
G D

Par hypothèse inductive le nouveau nombre de noeuds est

h+1 h+1 h+2
(2 - 1) + (2 -1) + 1 = 2 -1 ……CQFD!
h h+1
Ou encore : n = 1+2+…+2 = 2 - 1 33
 ABR : Compléxité de rechercher

Lemme 1: pour un ABR ayant n nœud et de hauteur h :

log2 n <= h <= n -1

Remarque: Un ABR parfait avec n noeuds a pour hauteur

h = log2 n
car
h h+1
2 <= n <= 2 - 1
34
ABR : Compléxité de rechercher
Conséquence : pour un ABR plein avec N noeuds
la compléxité de searchABR:

meilleur cas ………… O(1)

Pire cas ………… O(log N)
en moyenne ………… ???

35
 ABR : Compléxité de rechercher

 compléxité en moyenne pour une recherche dans

un ABR plein est une fonction logarithmique du nombre
de nœuds de l’arbre

Complexité en moyenne pour des ABR quelconque

est approximativement 39% plus chère que la recherche
dans un ABR plein pour le même nombres de nœuds :

Tavg ( N ) 1.386 log 2 N  3

36
 ABR : compléxité de rechercher

• Maintenant que nous connaissons la

compléxité de searchABR que peut-on dire des
autres opérations?
Insertion ………… O(log N)
Suppression ………… O(log N)
Trouver le Min ………… O(log N)
Trouver le Max ………… O(log N)
Tri ABR = ………… O(N log N) Pourquoi?

Idée: ABR tri = (Construction de l’ABR : N insertions)

+ (Parcourir ABR) 37
ABR : Compléxité de rechercher
• En résumé, il est nécessaire d’avoir un
ABR plein ou niveau-min ABR

 garder un arbre le plus équilibré possible

à tout moment (Arbre AVL)

38
 Arbre AVL
• Arbre AVL (Adelson-Velskii et Landis):

– Le meilleur ABR maintenant à tout moment un arbre

raisonnablement équilibré.

– Idée : si l’insertion ou la suppression provoque un

désiquilibre de l’arbre, rétablir l’équilibre.

– Toutes les opérations insertion, suppression,… sur un

arbre AVL avec N noeuds en O(log N) (en moyenne
et dans le pire cas!) 39
 AVL Trees
Arbre AVL (propriété): c’est un ABR tq. la différence des
hauteurs du sous-arbre gauche et droit de la racine est d’au
plus 1 et les sous-arbres gauche et droit sont des AVL

Exemple:

40
 Arbres AVL
Pour plus lisibilité , remplaçer les clés associées aux
nœuds en utilisant /, \, -, // et \\ pour représenter le
facteur d’équilibre d’un nœud :

/ : léger déséquilibre à gauche h(G) = 1 + h(D)

\ : léger déséquilibre à droite h(D) = 1 + h(G)

- : équilibré h(D) = h(G)

\\ : déséquilibre droit h(D) > 1 + h(G)

// : déséquilibre gauche h(G) > 1 + h(D) 41

 Arbres AVL
Exemples :

/ -

- / // \\
- - - / \
- - - - - -

Les clés ne sont pas montré.

On suppose qu’elles satisfassent la propriété ABR 42
 Arbres AVL
Un arbre AVL n’est ni un arbre plein ni un arbre niveau-min.
Insertions et suppression sont éffectuées de la même manière
que pour les ABR. Après chaque opération, on a besion de vérifier
la propriété d’AVL!. Car l’arbre peut ne plus l’être!

/ //
- - / -
- - / -
h diffère de 2!
nouveau -
noeuds 43
 Arbres AVL
Après une insertion, si l’arbre est un AVL alors on ne fait rien.
Comme sur l’exemple ci-dessous :

- \ - /
- - - / -

- -
- /
/ \ - \ / \
- - - - - / - -
-
44
 Arbres AVL
\
/ -

- - / \
- - - - - -
- - - -

Quand une insertion provoque le déséquilibre de l’arbre?

45
Arbres AVL : insertion d’un noeud
L’arbre devient déséquilibré si l’élément ajouté est le
descendant gauche (droit) d’un nœud avec un léger
déséquilibre gauche (droit). Alors la hauteur de ce sous-arbre
augmente.

Dans les figure suivantes, on note :

U: nouveaux nœuds pouvant déséquilibrer l’arbre

B: nouveaux laissant l’arbre équilibré

46
 Arbres AVL: Insertion

\
/ -

- - / \
- - - - - -
B B - - - -
UU UU BBBB
U UUU U U UU
47
 Arbres AVL: Insertion
Noter que l’insertion d’un nœud peut provoquer des
déséquilibre sur plusieurs nœuds.
Déséquilibre
par insertion //
/
/ - // -
- - - - / - - -
- - / -
- Le plus jeune ancêstre
du nœud inséré où la
nouveau noeud propriété AVL est violée
48
 Arbres AVL: Insertion
Supposons que le sous-arbre le plus haut est celui de gauche
et qu’un nœud est inséré pour augmenter la hauteur de ce
sous-arbre. L’arbre obtenu est déséquilibré
Rétablir un arbre AVL en utilisant des rotations
=> Soit A le plus jeune ancêtre où apparaît le déséquilibre
A
Dans l’arbre AVL, avant /
l’insertion, T1, T2 et T3
ont une hauteur h B
-
h T3
Le même raisonnement peut être
utilisé si l ’arbre le plus haut est celui T1 h h T2
de droite 49
 Arbres AVL: Insertion
Cas I: un nouveau nœud est inséré dans T1

Rééquilibrer par rotation droite:

P < B < q < A < r =>
Arbre Original A => propriété ABR maintenue!
// B
B r
/ -
p q h T3 p A
T1 q
- r
h h
T1
h+2 h+1 T2 h+1
h T2 h T3
50
 Arbres AVL: Insertion
Cas I: rotation Droite ou rotation Gauche

void RD(Arbre *a){ void RG(Arbre *a){

Arbre aux= (*a)->fg; Arbre aux= (*a)->fd;
(*a)->fg = aux->fd; (*a)->fd = aux->fg;
aux->fd= *a; aux->fg= *a;
*a= aux; *a= aux;
} }

51
 Arbres AVL: Insertion
Cas II: nouveau noeud inséré dans T2

On a 3 cas a considérer :
A 1- nouveau nœud en C
/ 2- nouveau nœud ajouté à T2a
B s 3- nouveau nœud ajouté à T2b
-
p C h T3
T1 -
h
q s Les 3 cas sont similaires.
T2a h-1 h-1 T2b On considérera le cas 2.

52
 Arbres AVL: Insertion
Cas II - T2a :
Rééquilibrage de l’arbre
A AVL avec une double rotation
// (gauche sur B et ensuite droite sur A)
B s
\
p C h T3
T1 /
h
q r
Cas II - T2b :
T2a h-1 h-1 T2b
Insertion en T2b => rotation
droite sur B et ensuite gauche
sur A
53
 Arbres AVL: Insertion
Cas II - T2a :
Rotation gauche Rotation droite
sur B sur A

A
// C
C // s -
B - r h T3 B- A
\
p q h-1 T2b p q r s
T1 T2aT2b
h h-1 T2a T1 h h-1 h-1 h T3

La propriété ABR est maintenue! 54

 Arbres AVL: Insertion
Cas II: nouveau noeud inséré dans T2
Cas II - T2a : Cas II - T2b :

void RGD(Arbre *a){ void RDG(Arbre *a){

RG( &((*a)->fg) ); RD( &((*a)->fd) );
RD(a); RG(a);
} }

55
 Arbres AVL: Insertion
• Nous avons défini un arbre “équilibré” et nous
avons aussi montré comment insérer dans l’arbre
en utilisant les algorithmes ABR de manière à
maintenir l’équilibre (propriétés AVL) et la
propriété ABR.

56
Arbre AVL: Insertion (Algorithme)
• Propriété : Toute adjonction dans un AVL nécessite au
plus une rotation pour le rééquilibrer.
T
• Supposons que x soit ajouté en tant que feuille dans T.
C ’est uniquement sur le chemin de la racine à x que
vont intervenir des rotations éventuelles.
• On considère sur ce chemin le nœud le plus bas dont le
déséquilibre avant adjonction est non nul, et l ’on note A
le sous arbre enraciné en ce nœud A
• De par la nature des rotations, la hauteur de A n ’est 1
pas modifiée par l ’adjonction de x (y compris en
prenant compte une rotation)
=> Dans l ’AVL résultant de l ’adjonction de x, le père
de A et tous ses ascendants ont exactement le Y
déséquilibre qu ’ils avaient avant l ’adjonction de x, il
n ’y a donc jamais besoin d ’effectuer de rotation « au-
57
dessus » de A, ni de mise à jour du déséquilibre.
Arbre AVL: Insertion (Algorithme)
• Algorithme d ’adjonction dans un AVL
Pour conserver la valeur du déséquilibre en chaque nœud de l ’arbre, on utilisera les déclarations
suivantes.
typedef struct n {
int val;
int deseq;
struct n * fg, *fd;
} nœud;
typedef nœud *AVL;
Principe :
Lors de la descente dans l ’arbre à la recherche de la place où l ’on doit ajouter x, on mémorise
le dernier sous-arbre A pour lequel le déséquilibre est 1.
Après avoir ajouté x à la feuille Y, c ’est uniquement sur le chemin de A à Y qu ’il est nécessaire
de modifier les valeurs du déséquilibre. Il faut ensuite faire le cas échéant, un rééquilibrage en A.

58
Arbre AVL: Insertion (Algorithme)
Void ajouterAVL (AVL *t, int x){
AVL y, a, p, aa, pp;
/* création du nœud à ajouter */
y = nouveau(nœud); y->val =x; y->deseq =0;y->fg=y->fd=NULL;
If (*t==NULL) *t=y;
else {
a=*t; aa=NULL; p=*t; pp=NULL;
/*aa et pp sont les pères de a et p*/
while(p!=NULL){/*descente mémorisation du dernier nœud dont le déséquilibre est 1*/
if(p->deseq<>0){a=p;aa=pp;}
pp=p;
if(x<=p->val) p=p->fg; else p=p->fd;
}
/*adjonction*/
if (x<=pp->val) pp->fg=y; else pp->fd=y;

59

1 2
 Arbre AVL: Insertion (Algorithme)
/*modification du déséquilibre sur le chemin de A à Y*/
p=a;
while (p<>y)
if (x<=p->val){p->deseq=p->deseq+1;p=p->fg;}
else {p->deseq=p->deseq-1;p=p->fd;}
/* rééquilbrage*/
switch (a->deseq){
case 0:
case 1:
case -1: return;
case 2 : switch (a->fg->deseq){
case 1: { RD (&a); a->deseq=0;a->fd->deseq=0;break;}
case -1: {
RGD(&a);
switch (a->deseq){
case 1: {a->fg->deseq=0; a->fd->deseq=-1;break}
case -1: {a->fg->deseq=+1; a->fd->deseq=0;break}
case 0: {a->fg->deseq=0; a->fd->deseq=0;break} /*a=y*/
}
a->deseq=0;
break;
}
}
case -2 : /* situation symétrique ...*/
}

60

1 2
Arbre AVL: Insertion (Algorithme)
If(aa=NULL)
*t=a;
else if (a->val<=aa->val)
aa->fg=a;
else aa->fd=a;
1 2 }
}

61
 Arbre AVL: suppression
• La réorganisation de l ’arbre peut nécessiter plusieurs
rotations successives.
T -1
On veut supprimer 26, on le
26
remplace par 24, cette suppr
diminue la hauteur du sous-arbre
1 1 de racine 22 et le sous-arbre de
16 50 racine 16 est alors trop
1 déséquilibré.
-1
40
1
10
22 On le réorganise par une rotation
droite, mais cela accentue le
-1 déséquilibre du niveau
0 20 23
immédiatement supérieur et il faut
E faire une rotation droite gauche en
B
A 24 0
D 24. Les rotations peuvent ainsi
C
remonter en cascade jusqu ’à la
racine de l ’arbre.
=> 1.5 log2 n rotations.
=> la suppression est en O(log2 n)
62
 Arbre AVL: suppression
• L ’arbre n ’est plus un AVL

T -1

24

2 1

16 50
1
0
1 22 40
10

0
0 20 23
E
B D
A C

63
On distingue différents cas…
 Arbre AVL: suppression
• Cas I: Cas II:
T T

+1 0

A
A B B

• Rien à faire, car la hauteur • Ici la hauteur du sous-arbre

de l’arbre n’a pas été va évoluer(-1) localement :
modifié aucun déséquilibre n ’est
apparu, au contraire, le sous
• Avec -1 même situation
arbre devient équilibré. Des
déséquilibre peuvent
apparaître plus haut! 64
 Arbre AVL: suppression
• Cas III:
T

+2

B
A

Ici la hauteur du sous-arbre n’a pas évolué mais le déséquilibre

est passé à 2 : il faut intervenir; on distingue la différents cas de
figure qui sont liées au fils gauche :

65
 Arbre AVL: suppression
• Cas III.1: T
T
RD(T) p
q -1
q
+2
+1
p
A
0
B C
C

A B

Il y a arrêt du traitement ici, puisque :

•le sous-arbre est équilibré
• sa hauteur n’a pas été modifiée (il est donc inutile de propager
le résultat vers le haut) 66
 Arbre AVL: suppression
• Cas III.2: T
T
RD(T) p
q 0
q
+2
0
p
A
-1
B
C
C
B
A

Le sous-arbre est rééquilibré, mais la hauteur a été modifié

il faut remonter l ’information au dessus de T pour procéder
éventuellement à des rééquilibrage
=> appliquer le même principe que celui qui vient d ’être 67
appliqué en considérant I,II et les différents cas de III.
 Arbre AVL: suppression
• Cas III.3:
T T
RD(T)
r q
+2 0
p p r
-1,0
-1 1,0
q
-1,0,+1 D
A A B C
D

B C

Le sous-arbre est rééquilibré, mais sa hauteur a diminué de 1

=> remonté de l ’information comme en III.2
68
 Arbre AVL: suppression
Principe de l ’algorithme :
– Réorganisation de l ’arbre de la feuille supprimée
jusqu ’à la racine de l ’arbre avec éventuellement des
rotations (on s’arrête pour les cas I ou III.1)
• recalcul des déséquilibres occasionnés par la suppression et
éventuelle exécutions des rotations nécessaires du fait de
nouveaux déséquilibres
• la propagation continue tant que l ’arbre demeure déséquilibré
lors de la remontée

Au pire cas le nombre de rotation est log2 n

69
 Arbres AVL : analyse de
compléxité
Soit T(n) la compléxité de l’insertion d’un nœud dans
un arbre AVL.

Quelle est la meilleur structure d’arbre AVL possible?

– Arbre plein  T(n) = O(log n)

70
 Arbres AVL : analyse de
compléxité
Le pire cas d’arbres AVL qu’on peut rencontrer sont
les AVL ayant la partie gauche (ou droite) en léger
déséquilibre pour tous les nœuds.

/
/ /
/ / / -
/ - - -
-
71
 Arbres AVL : analyse de
compléxité
• Quelle est la hauteur maximale d’un AVL
avec N noeuds?
• Quelle est le plus petit nombre Nh de
noeuds d’un AVL avec une hauteur h :

Nh = 1 + Nh-1 + Nh-2

Chacun est le plus petit arbre avec les

72
tailles respectives
 Arbres AVL : analyse de
compléxité
• La hauteur d’un arbre AVL avec n nœuds
est au plus égale à 1.44 log2 (n+2).
• La hauteur d’un arbre binaire avec n
noeuds est au moins égale à log2 (n+1).

log2 (n+1) <= height <= 1.44 log2 (n+2)

73
Arbres AVL : analyse de compléxité
• Soit Nh = min # noeuds d’un arbre AVL avec une hauteur h.
• N0 = 0.
• N1 = 1.
• Nh, h > 1
• G et D sont des arbres AVL.
• La hauteur de l’un est h-1.
• La hauteur de l’autre est h-2.
• Le sous arbre ayant une hauteur h-1 à Nh-1 noeuds.
• Le sous arbre ayant h-2 à Nh-2 noeuds.
• alors, Nh = Nh-1 + Nh-2 + 1.
G D

74
Arbres AVL : analyse de compléxité
Séquence de nombre de Fibonacci
• F0 = 0, F1 = 1.
• Fi = Fi-1 + Fi-2 , i > 1.
• N0 = 0, N1 = 1.
• Nh = Nh-1 + Nh-2 + 1, h > 1.
• Nh = Fh+2 – 1.
• Fi ~ i/ .
 


5
sqrt
i
1 1 5 
Fi   
5 2 
75
 Arbres AVL : analyse de
compléxité
h3
1 1 5 
Nh   
5 2 
 h1.44 log2 Nh
 h  1.44 log2 N

Toutes les opérations AVL sont en O(log2 N)

76
 Arbres 2.3.4
• Pour éviter les cas d ’arbres de recherche dégénérés, on peut aussi
faire varier le nombre de directions de recherche à partir d ’un nœud.
• Définition générale : Un arbre de recherche est un arbre général
étiqueté dont chaque nœud contient un k-uplet d’éléments distincts
et ordonnées (k=1,2,3…). Un nœud contenant les éléments x1< x2 …
<xk a k+1 sous-arbres, tels que :
– tous les éléments du premier sous-arbre sont inférieurs ou égaux à x1
– tous les éléments du ième sous-arbre (i=2,…,k) sont strictement supérieurs à
xi-1 et inférieurs ou égaux à xi
– tous les éléments du (k+1)ième sous-arbre sont strictement supérieurs à xk

77
 Arbres 2.3.4
15

4 10 13 30 40

1 3 7 8 11 12 14 20 28 50 40
35

15 1 3 4 10 13
2-noeud 3-noeud 4-noeud
Définition : Un arbre 2.3.4 est un arbre de recherche dont
les nœuds sont de trois types, 2-nœud, 3-nœud, 4-nœud, et
dont toutes les feuilles sont situées au même niveau 78
 Arbres 2.3.4
• la hauteur reste logarithmique par rapport au nombre de
nœuds
  algos de rééquilibrages qui maintiennent un arbre 2.3.4 après
ajout ou suppr en effectuant une suite de rotations sur chemin
de la racine à une feuille
• O(log n) pour recherche, ajout et suppression
• implantation efficace sous la forme d’arbres binaires de
recherches bicolores

79
 Arbres 2.3.4
Propriété : La hauteur h(n) d ’un arbre 2.3.4 contenant n élément est en (log n). Plus précisément,
on a l’encadrement suivant :
log4(n+1) h(n)+1  log2(n+1)

Preuve : on considère les arbres 2.3.4 extrémaux:

– contenant le moins d’éléments : (que des 2-nœuds)
• puisque toutes les feuilles sont au même niveau,le nombre de nœuds : 2 0+ 21+... 2h= 2h+1-1
– contenant le plus d’éléments : (que des 4-nœuds)
40+ 41+... 4h= 4h+1-1
on en déduit qu ’un arbre 2.3.4 contenant n nœuds et de hauteur h(n) : 2 h(n)+1-1 <= n <= 4h(n)+1-1
d’où l’on tire l ’encadrement de la hauteur

80
Algorithme de recherche (principe)
Arbres 2.3.4
Soit M un arbre 2.3.4, Soit x un élément à rechercher dans M.
• x est comparé avec le(s) éléments x 1,.., xi (i[1..3]) de la racine de M
– si  j [1..i] tq. X= xj alors trouvé
– si x x1 => recherche dans le premier sous-arbre de M
– si xj <x<xj+1 (j [1..i-1] ) => recherche dans la (j+1)ième sous-arbre de M
– si x >xj => recherche dans le dernier sous-arbre de M
• si la recherche se termine sur une feuille qui ne contient pas x => x M
Exercice Implanter cet algorithme,
• on utilisera les déclarations suivantes :
typedef struct n {
int n /* nombre de pointeurs */
struct n * sArbre[4]; /* sous arbres */
int elements[3]; /* les éléments */
} nœud;
typedef nœud * Arbre234;
• Refaire le même exercice en utilisant le type union

81
typedef struct n {
Arbres 2.3.4 : Recherche
int n; /* nombre de pointeurs */
struct n * sArbre; /* sous arbres */
int *elements; /* les éléments */
} nœud;
typedef nœud * Arbre234;
void ELEMENT (int x; Arbre234 A )
{
int pos ;
if (A ==NULL )
return 0;
else {
pos = position (x, A) ;
if ( (x == A->elements [ pos ] ) )
return 1;
else
return ELEMENT (x, A->sArbre [ pos ] ) ;
}
}
int position (int x; Arbre234 A)
/* plus grand pos tel que A->elements[pos] x */
{
int pos, trouve =0;
for (pos=0; pos<A->n && !trouve; pos++){
trouve = (x<= A->elements[pos]);
}
return pos;
}

82
 Arbres 2.3.4
Adjonction d ’un élément
L’adjonction d ’un nouvel élément ne pose problème que si la feuille qui doit le recevoir contient
déjà 3 éléments.
Dans ce cas, il faut ajouter un nouveau nœud à l ’arbre et le réorganiser.
Adjonction avec éclatement en remonté :
On ajoute successivement 4, 35, 10, 13, 3, 30, 15, 12, 7, 40, 20, 11, 6

M ne peut plus contenir

Ce nœud M de nouveau éléments. M
On remarque4que du point de vue recherche,
4 35 M est équivalent à l ’arbre
4 10 binaire
35 :

Cet arbre est un arbre 2.3.4, on peut y ajouter de nouveaux éléments :

13, puis 3, puis 30 M
10
4 35

83
 Arbres 2.3.4
M M M
10 10 10
4 13 35 3 4 13 35 3 4 13 30 35 f

L ’ajout de 15 provoque l ’éclatement de la feuille f en deux 2-nœuds

contenant respectivement le plus petit et le plus grand élément de f. L ’élémen
médian 30 doit être ajouté au nœud père de f, il y a alors de la place pour 15
dans le même nœud que 13 qui devient alors un 3-noeud

M M
10 30 10 30
3 4 13 15 35 3 4 7 12 13 15 35 40

84
 Arbres 2.3.4
L ’ajout de 20 entraîne un éclatement de la feuille contenant 12, 13 et 15

M M
10 13 30 10 13 30
f
3 4 7 12 15 20 35 40 3 4 7 11 12 15 20 35 40
L ’adjonction de 6 provoque l ’éclatement de la feuille f, la remonté de 4 fait éclater à son tour la
racine de l ’arbre en 2-noeuds

M
13
=> les éclatements peuvent remonter en cascade sur toute la hauteur de l ’arbre.
4 10 30
3 6 7 11 12 15 20 35 40

85
 Arbres 2.3.4
• Pour éviter des éclatements de bas en haut, il suffit de travailler
sur des arbres qui ne contiennent jamais deux 4-nœuds qui se
suivent. Dans ce cas toute adjonction provoque au plus un
éclatement.
• Ceci peut être réalisé en éclatant les 4-nœuds à la descente : Lors
de la recherche de la place de l ’élément à ajouter, on parcourt un
chemin à partir de la racine jusqu ’à une feuille; seuls les 4-nœuds
de ce chemin risquent d ’éclater suite à l ’adjonction.
• On prévient ce risque en les faisant éclater, au fur et à mesure de
leur rencontre avant de réaliser l ’adjonction. (Ceci provoque
parfois des éclatements inutiles)

86
Une représentation des arbres 2.3.4 :
les arbres bicolores
• Définition : Un arbre bicolore est un arbre binaire de recherche dont
les nœuds portent une information supplémentaire (rouge et noir).
• Les 4-nœuds et 3-nœuds sont transformé en arbre binaire de
recherche. b
b
a b c a c a c
p0 p1 p2 p3 p0 p1 p2 p3 p0 p1 p2 p3
• Double trait si le lien appartient à un nœud de l ’arbre 2.3.4 (lie des
nœuds jumeaux)
• On peut aussi représenter par un double cercle les nœuds vers
lesquels « pointent » des doubles traits
b b
a c a c

p0 p1 p2 p3 p0 p1 p2 p3 87
Une représentation des arbres 2.3.4 :
les arbres bicolores
• Pour les 3-nœuds, il existe 2 transformations possibles

a a a
Penché à
a b b b
droite p0 b
p0
p0 p1 p2 p0 p1 p2
p1 p2 p1 p2
b b b
Penché à
a b a a
gauche p2 a p2
p0• Lesp1deuxp2représentationsppourront
0 p1 p2
exister à la suite de rotations
p0 p1 p p1
• La hauteur de l’arbre bicolore obtenu par ces transformations est au plus0 2*la hauteur
de l’arbre 2.3.4 initial, augmentée de 1.
• => Tout arbre bicolore associé à un arbre 2.3.4 contenant n éléments a une hauteur de
l’ordre O(log n)

88
 Arbres 2.3.4 /Arbres bicolores
12 45

8 20 25 40 50 60

3 5 10 15 22 24 30 35 38 43 48 55 59 63 65

Représentation en arbre bicolore ?

45
12 50

8 25 48 60

3 10 20 40 59 63

5 15 24 35 43 65
55
89
22 30 38
 Arbres 2.3.4 /Arbres bicolores
• On simule l ’adjonction avec éclatement à la descente dans un arbre
2.3.4
• Eclater un 4-nœud revient à inverser les couleurs des éléments de ce
nœud

b b
a c a c
• Ceci
p0 peut
p1 pcependant
p3 faire apparaître deux nœuds rouges consécutifs, ce
2 p0 p1 p2 p3
qui doit être évité si l ’on veut conserver la propriété de hauteur
logarithmique
=> utilisation de transformations locales : rotations

90
 Arbres 2.3.4 /Arbres bicolores
Plusieurs situations possibles
1) Le 4-nœud à éclater est attaché à un 2-nœud
=> une simple inversion de couleur suffit

a a a
a 

      

   

91
 Arbres 2.3.4 /Arbres bicolores
2) Le 4-nœud , E, à éclater est attaché à un 3-nœud :
3 cas lorsque le 3-nœud est penché à droite
3 cas lorsque le 3-nœud est penché à gauche
a) E est premier fils du 3-nœud
=> on inverse les couleurs des éléments du 4-noeud

a b a a  a b

 b b  
   

   
92
 Arbres 2.3.4 /Arbres bicolores
b) E est second fils du 3-nœud
=> une inversion de couleurs entraîne une mauvaise
disposition des éléments jumeaux a,  et b
=> rotation droite-gauche au niveau du nœud contenant a
RDG
a b a a 

b b a b
  
  


   

a  b

  93
 Arbres 2.3.4 /Arbres bicolores
c) E est troisième fils du 3-nœud

=> rotation gauche au niveau du nœud contenant a

a b a a RG b

b b a 
  
   

   
a b 

 
94
 Arbres 2.3.4 /Arbres bicolores
Algorithme d’adjonction :
• Descendre à partir de la racine à la recherche de la feuille où
insérer l’élément
• Sur le chemin, lorsqu’un nœud A a ses deux fils rouges on inverse
les couleurs de A et de ses fils : si de plus le père de A est lui
aussi rouge, on fait une rotation au niveau du grand-père de A
avant de poursuivre la descente.
• L’adjonction d ’un nouvel élément se fait toujours dans une
feuille qui devient un nœud rouge, puisque le nouvel élément est
ajouté en tant que jumeau; dans le cas où le père du nœud ajouté
est rouge, mais n ’a pas de frère rouge, il faut effectuer une
rotation comme en b)

95
 Arbres 2.3.4 /Arbres bicolores
Exercice :
Écrire l’algorithme d’adjonction en utilisant le type suivant :
typedef enum{blanc, rouge} couleur;
typedef struct bn{
couleur coul;
int val;
struct bn * fg, *fd;
} Bnoeud;
typedef Bnoeud * Bicolore;

96
 Recherche externe
• Grandes collections d ’éléments stockés sur
mémoire secondaire paginée.
• Le nombre d ’accès à la mémoire
secondaire est prépondérant
=> minimiser le nombre de transferts de pages
• B-Arbres :
– généralisation des arbres 2.3.4

97
 Recherche externe : B-arbres
Un B-arbre d ’ordre m est
• un arbre binaire de recherche formé de nœuds qui
peuvent chacun contenir jusqu’à 2m éléments;
• chaque nœud est dans une page différente du
support externe et
• la complexité des algos de recherche, adjonction et
suppression d ’un élément parmi n, compté en
nombre d ’accès à la mémoire secondaire, est en
O(logm n)

98
 B-arbres

Un B-arbre d ’ordre m est un arbre binaire de

recherche dont
– toutes les feuilles sont située au même niveau
– tous les nœuds, sauf la racine, sont des k-nœuds avec k
 [m+1..2m+1]

– la racine est un k-nœud avec k [2..2m+1]

99
 B-arbres
Exemple
25

6 10 20 30 40

1 2 3 4 7 8 13 14 15 18 22 24 26 27 28 32 35 38 41 42 44 46

Exemple de B-arbre d’ordre 2

100
 B-arbres
Dans la réalité m est choisi de manière à ce qu ’un nœud corresponde
au contenu d ’une page.
Exemple :
– m=250 => un arbre de hauteur 2 peut contenir plus de 125 millions
d ’éléments
• 500 éléments à la racine
• 500 *501 (environ 25*104) éléments dans les nœuds de profondeur 1
• 5012 *500 (environ 125*106) éléments dans les nœuds de profondeur 2
=> Dans les B-arbres, les niveaux les plus bas de l ’arbre contiennent la quasi-
totalité des éléments
Algorithmes de recherche, d ’adjonction et de suppression
=> généralisation des algorithmes pour les arbres 2.3.4

101
 Recherche externe : Hachage
dynamique
• Le tableau de hachage est remplacé par un index en mémoire centrale
• Cet index est un arbre binaire de recherche dont les feuilles
contiennent des adresses en mémoire secondaire
Exemple :
Adjonction successive par hachage dynamique des éléments E, X, T, F,
R, N, C, L, S, G, B
valeurs de hachage :
h(E)=00101, h(X)= 11000, h(T)= 10100, h(F)=00110,h(R)=10010,
h(N)=01110, h(C)=00011, h(L)=01100, h(S)=10011, h(G)=00111,
h(B)=00010
•
102
 Recherche externe : Hachage
• Exemple (suite) :
dynamique
En supposant que les pages en mémoire secondaire peuvent
contenir 4 éléments.
0 1
0 1
Index en R N,C
mémoire centrale
E
X E
Pages en X E
T F
X
T F T
mémoire secondaire F
R N
R
C

0 1 0 1 0 1
L S,G B
0 1 0 1 0 1
0 1
X X
X
T T
T E
E R N R
N R F N
F S L S
L C L E
C C
G F
B 103
G