1 Arbres Un arbre est une structure de données organisées de façon hiérarchique, à partir dun nœud distingué appelé racine. Très importante en informatique!

1

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

2

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

3

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.

niveau 0

niveau 1

niveau 2

niveau 3

racine

nœuds internes

feuilles

parentetfils

4

Arbres binaires

• Un Arbre Binaire est un arbre où chaque nœud admet au plus 2 fils.

5

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

15128

16

7 9 11 13

18

6

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]

7

Arbres Binaires: représentation par tableau

14

10

15128

16

7 9 11 13

18

1

2 3

4 5 6 7

8 9 10 11

1 2 3 4 5 6 7 8 9 10 11

14 10 16 8 12 15 18 7 9 11 13tab A:

8

Arbres Binaires: représentation par pointeurs

typedef struct n{

int clé;int clé;

struct n *fGauche, *fDroit;struct n *fGauche, *fDroit;

}nœud;

typedef nœud * Arbre;

9

Parcours : inOrdreInOrdre est décrit réursivement :

• Visiter le sous-arbre gauche en InOrdre• Visiter la racine• Visiter le sous-arbre droit en InOrdre

10

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

Parcours : préOrdre

11

PréOrdre itératif en utilisant une Pile. Pile Sempiler racine dans Srépéter jusqu’à S= v = dépiler S si v <> nil visiter v

empiler le fils droit de v dans Sempiler le fils gauche de v dans S

Parcours: non-récursif

12

PostOrdre est décrit réursivement :

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

Parcours: postOrdre

13

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

14

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

15

Arbre Binaire de Recherche: Exemples

C

A D

14

10

15118 18

16

14

10

15118

16

racine

racine

racine

16

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

17

ABR: InOrdre

14

10

15118 18

16

(8)(10)(11)(14)(15)(16)(18)

InOrdre visites :

Exemple:

18

ABR : Rechercher un élément

Soit un ABR :

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

G

P

D

19


rechercher(racine, x)

comparer x à la clé de racine:

- si x = clé return - si x < clé => chercher dans G - si x > clé => chercher dans D

chercher de la même manière dans G ou D

Exemple:

14

10

15118

16

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

20


bool searchABR(Arbre racine; typeCle clé){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 ?

21

ABR : Ajout d’un élément

Comment ajouter une clé?

La même procédure que searchABR s’applique: Déterminer la position d’insertion par searchABR. Ajouter la nouvelle clé si la recherche échoue.

Exemple:

10

8

5

3 4

2

9

ajout 4?

22

Construction d’un ABR

Exemple: ajouter C A B L M (dans l’ordre!)

1) Ajouter C

C

2) ajouter A

C

A

3) ajouter B C

A

B

4) Ajouter L C

A

B

L

5) Ajouter M C

A

B

L

M

23

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

C

A

B

L

M

A

B

C

L

M

Ajout de : A B C L M Ajout de : C A B L M

24

Trier avec un ABR

Soit un ABR, peut-on afficher les clés dans l’ordre?

Visiter l’ABR avec un parcours InOrdre: - visiter le sous-arbre gauche

- afficher racine - visiter le sous-arbre droit

Comment trouver le minimum? Comment trouver le maximum?

C

A

B

L

M

Example:

A B C L M

InOrdre affichage:

25

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

x

supprimer x On obtient un ABR

q

r

q

r

p p

26

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

L

x

q

r

suppr x L

q

r

On obtient un ABR

27

ABR : supprimer un élément

Cas C: x est un nœud interne avec 2 sous-arbres

W

x

q

r

suppr x

Z

t s

u

W

q

r

suppr x

s Z

u

propriété ABR est conservé

t

28

ABR : supprimer un élément

Cas C suite: … ou encore comme suit

W

q

r

Zs

u

t

q < x < u

q est inférieur au plus petit élément de Z r est supérieur au plus grand élément de W

D’autres façon ?

29

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 eten moyenne

30


niveau 0

niveau 1

niveau 2

niveau 3

• hauteur d’un ABR = niveau max• hauteur d’un noeud

h(x) = 0 si x est la racineh(x) = 1+ h(y), y = pere(x)

• hauteur d’un ABR B : h(B) = max{h(x), x nœud de B}

(h =3)

31


Si tout les nœuds de l’arbre existent : ABR plein

Si tout les nœuds existent saufceux du dernier niveau :niveau-min ABR

32


Théorème: 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

2 - 1 noeuds

h+1

h+1

33


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

G Dh

h+1

Par hypothèse inductive le nouveau nombre de noeuds est

(2 - 1) + (2 -1) + 1 = 2 - 1 ……CQFD!

Ou encore : n = 1+2+…+2 = 2 - 1

h+1 h+1 h+2

h h+1

34


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 = log n car

2 <= n <= 2 - 1

2

h h+1

35

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 ………… ???


36


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 quelconqueest approximativement 39% plus chère que la recherche dans un ABR plein pour le même nombres de nœuds :

3log386.1)( 2 NNTavg

37

• Maintenant que nous connaissons la compléxité de searchABR que peut-on dire des autres opérations?

ABR : compléxité de rechercher

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)

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

Pourquoi?

38

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


39

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

40

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:

41

Arbres AVLPour 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 :

h(D) = h(G)

// : léger déséquilibre à gauche

\\ : léger déséquilibre à droite

-- : équilibré

\\\\ : déséquilibre droit

//// : déséquilibre gauche

h(D) = 1 + h(G)

h(G) = 1 + h(D)

h(G) > 1 + h(D)

h(D) > 1 + h(G)

42

Arbres AVLExemples :

//

\

\\

-

- -

/ -

/

-

-- - -

-

- /

Les clés ne sont pas montré. On suppose qu’elles satisfassent la propriété ABR

43

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érifierla propriété d’AVL!. Car l’arbre peut ne plus l’être!

/

-

-

-

-

h diffère de 2!

//

-

-

-

/

/

nouveaunoeuds

44

Arbres AVL

Après une insertion, si l’arbre est un AVL alors on ne fait rien.Comme sur l’exemple ci-dessous :

\

--

-

--

-

-

/

/

/

- ----

--

-

-- -

\ \ \

/

/

/

45

Arbres AVL

-

-

-

--

-

/ \

/

--

- -

-

--

\

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

46

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é

47

-

-

-

--

-

/ \

/

--

- -

-

--

\

Arbres AVL: Insertion

U

B B

BBBBU

U U

UU UU

U UUU

48


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 propriété AVL est violée nouveau noeud

49


h h

h

T1 2

3T

T

/

-

A

B

Supposons que le sous-arbre le plus haut est celui de gaucheet 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

Dans l’arbre AVL, avantl’insertion, T1, T2 et T3 ont une hauteur h

Le même raisonnement peut être utilisé si l ’arbre le plus haut est celui de droite

50


Cas I: un nouveau nœud est inséré dans T1

Rééquilibrer par rotation droite:P < B < q < A < r =>=> propriété ABR maintenue!

A

h3T

-

-B

h2T

Th+1

1 rqp

h+2 h+1

A

h h

h

12

3T

T

//

/B

p q

r

T

Arbre Original

51


Cas I: rotation Droite ou rotation Gauche

void RD(Arbre *a){

Arbre aux= (*a)->fg;

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

aux->fd= *a;

*a= aux;

}

void RG(Arbre *a){

Arbre aux= (*a)->fd;

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

aux->fg= *a;

*a= aux;

}

52


Cas II: nouveau noeud inséré dans T2

A

h13h T

/

-B

h-1 2bT

p

q

s

T

h-12aTs

-C

On a 3 cas a considérer : 1- nouveau nœud en C 2- nouveau nœud ajouté à T2a

3- nouveau nœud ajouté à T2b

Les 3 cas sont similaires. On considérera le cas 2.

53


A

h13h T

//

\B

h-1 2bT

p

q

s

T

h-12aTr

/C

Cas II - T2a :Rééquilibrage de l’arbre AVL avec une double rotation (gauche sur B et ensuite droite sur A)

Cas II - T2b :

Insertion en T2b => rotation droite sur B et ensuite gauche sur A

54


A

1

3h T

//

//B

h-1

p

s

T 2aT2bTq

h

r-

C

h-1

A

1

\

-

B

h-1

p

3h T

s

T 2aTq

h

r-

C

h-12bT

Rotation gauchesur B

Rotation droitesur A

La propriété ABR est maintenue!

Cas II - T2a :

55


void RGD(Arbre *a){

RG( &((*a)->fg) );

RD(a);

}

void RDG(Arbre *a){

RD( &((*a)->fd) );

RG(a);

}

Cas II: nouveau noeud inséré dans T2

Cas II - T2a : Cas II - T2b :

56

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


57

Arbre AVL: Insertion (Algorithme)

• Propriété : Toute adjonction dans un AVL nécessite au plus une rotation pour le rééquilibrer.

• 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• De par la nature des rotations, la hauteur de A n ’est

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

déséquilibre qu ’ils avaient avant l ’adjonction de x, il

n ’y a donc jamais besoin d ’effectuer de rotation « au-

dessus » de A, ni de mise à jour du déséquilibre.

A

T

1

Y

58

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.

59

Arbre AVL: Insertion (Algorithme)Void ajouterAVL (AVL *t, int x){

AVL y, a, p, aa, pp;

/* création du nœud à ajouter *//* 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;

1 2

60

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 ...*/}

1 2

61

Arbre AVL: Insertion (Algorithme)

If(aa=NULL)

*t=a;

else if (a->val<=aa->val)

aa->fg=a;

else aa->fd=a;

}

}

1 2

62

Arbre AVL: suppression• La réorganisation de l ’arbre peut nécessiter plusieurs

rotations successives.

0

1

1

1

-1

26

16

2210

40

50

0

-123

24

20

AB

E

CD

-1

1

TOn veut supprimer 26, on le remplace par 24, cette suppr diminue la hauteur du sous-arbre de racine 22 et le sous-arbre de racine 16 est alors trop déséquilibré.

On le réorganise par une rotation droite, mais cela accentue le déséquilibre du niveau immédiatement supérieur et il faut faire une rotation droite gauche en 24. Les rotations peuvent ainsi remonter en cascade jusqu ’à la racine de l ’arbre.

=> 1.5 log2 n rotations.

=> la suppression est en O(log2 n)

63

Arbre AVL: suppression• L ’arbre n ’est plus un AVL

0

2

1

1

-1

24

16

2210

40

50

02320

AB

E

CD

0

1

T

On distingue différents cas…

64

Arbre AVL: suppression• Cas I: Cas II:

+1

A

T

B

• Rien à faire, car la hauteur de l’arbre n’a pas été modifié

• Avec -1 même situation

0

A

T

B

• Ici la hauteur du sous-arbre va évoluer(-1) localement : aucun déséquilibre n ’est apparu, au contraire, le sous arbre devient équilibré. Des déséquilibre peuvent apparaître plus haut!

65

Arbre AVL: suppression• Cas III:

+2

A

T

B

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 :

66

Arbre AVL: suppression• Cas III.1:

+2

q

A

T

C

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)

B

p

RD(T)

+1

q

A

T

CB

p-1

0

67


+2

q

A

T

C

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 appliqué en considérant I,II et les différents cas de III.

B

p

RD(T)

0

q

A

T

CB

p0

-1

68


+2

r

A

T

D

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

=> remonté de l ’information comme en III.2

C

p

RD(T)

-1

B

q-1,0,+1

0

q

A

T

DC

p1,0

B

r-1,0

69

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

70

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)

71


/

/

/-/

/

/ /

---

-

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.

72

• 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 tailles respectives

73


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

74

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

75

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

sqrt

F

i

i2

51

5

1

5

76


N

Nh

N

h

h

h

2

2

3

log44.1

log44.1

2

51

5

1

Toutes les opérations AVL sont en O(log2 N)

h

77

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

78

Arbres 2.3.4

30 404 10 13

15

14 50 4035

1 315

1 3 7 8 11 12 20 28

4 10 13

2-noeud 4-noeud3-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

79

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

80

Arbres 2.3.4Proprié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 : 20+ 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) : 2h(n)+1-1 <= n <= 4h(n)+1-1

d’où l’on tire l ’encadrement de la hauteur

81

Arbres 2.3.4Algorithme de recherche (principe)Soit M un arbre 2.3.4, Soit x un élément à rechercher dans M.• x est comparé avec le(s) éléments x1,.., 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 MExercice 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

82

Arbres 2.3.4 : Recherchetypedef struct n {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;elsereturn 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;}

83

Arbres 2.3.4Adjonction 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

Ce nœud ne peut plus contenir de nouveau éléments.On remarque que du point de vue recherche, M est équivalent à l ’arbre binaire :

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

13, puis 3, puis 30

4M

4 35M

4 10 35M

10M

4 35

84

Arbres 2.3.4

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ément 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

10

13 354

10

13 353 4

10

13 30 353 4 f

M M M

10 30

13 153 4

M

35

10 30

3 4 7 12 13 15

M

35 40

85

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

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

=> les éclatements peuvent remonter en cascade sur toute la hauteur de l ’arbre.

10 13 30

3 4 7 15 20

M

35 4012

10 13 30

3 4 7 15 20

M

35 4011 12f

30

15 20

M

35 40

4 10

13

11 123 6 7

86

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)

87

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.

• 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

a b c

p0 p1 p2 p3

ba c

p0 p1 p2 p3

b

p0 p1 p2 p3

a c

b

p0 p1 p2 p3

a c

b

p0 p1 p2 p3

a c

88

Une représentation des arbres 2.3.4 : les arbres bicolores

• Pour les 3-nœuds, il existe 2 transformations possibles

• Les deux représentations pourront exister à la suite de rotations• La hauteur de l’arbre bicolore obtenu par ces transformations est au plus 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)

a b

p0 p1 p2

ab

p0 p1 p2

a

p0

p1 p2

ba

p0

p1 p2

bPenché à droite

a b

p0 p1 p2

ab

p0 p1 p2

b

p2

p0 p1

a

b

p2

p0 p1

aPenché à gauche

89

Arbres 2.3.4 /Arbres bicolores

50 6020 25 40

12 45

43 63 654815 22 24 30 35 38 55 593 5 10

8

Représentation en arbre bicolore ?45

12 50

8 25

3

5

10 20 40

15 24 35 43

6048

59 63

6555

22 30 38

90

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

• Ceci peut cependant faire apparaître deux nœuds rouges consécutifs, ce qui doit être évité si l ’on veut conserver la propriété de hauteur logarithmique

=> utilisation de transformations locales : rotations

b

p0 p1 p2 p3

a cb

p0 p1 p2 p3

a c

91


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

92


2) Le 4-nœud , E, à éclater est attaché à un 3-nœud :3 cas lorsque le 3-nœud est penché à droite3 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

a

a b

a b

bb

93

Arbres 2.3.4 /Arbres bicoloresb) 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

a

a

a b

a b

bb

a

b

RDG

94

Arbres 2.3.4 /Arbres bicoloresc) E est troisième fils du 3-nœud

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

a

b

a

a b

a b

b

RGa

b

95

Arbres 2.3.4 /Arbres bicoloresAlgorithme 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)

96

Arbres 2.3.4 /Arbres bicoloresExercice :

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

97

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

98

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)

99

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]

100

B-arbres

Exemple

30 406 10 20

25

41 42 44 467 8 13 14 15 18 32 35 3822 241 2 3 4 26 27 28

Exemple de B-arbre d’ordre 2

101

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

102

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

•

103

Recherche externe : Hachage dynamique

• Exemple (suite) : En supposant que les pages en mémoire secondaire peuvent contenir 4 éléments.

1

EXTF

0

Index en mémoire centrale

Pages en mémoire secondaire

EF

XTR

R

EFNC

XTR

N,C10

EFC

XTR

L 10

NL

0 1

EFCG

XTRS

S,G 10

NL

0 1

CB

XTRS

B 10

NL

0 1

EFG

0 1

Documents

1 Arbres Un arbre est une structure de données organisées de façon hiérarchique, à partir dun nœud distingué appelé racine. Très importante en informatique!