ARBRES EQUILIBRES

MIGO ET COMPLEXITE 1

ARBRES EQUILIBRES

Définition :

On dit qu’un arbre binaire est H équilibré si en tout nœud de l’arbre, les hauteurs des sous-arbres gauche et droit diffèrent au plus de 1.

Exemple :


Fonction DESEQUILIBRE sur les arbres binaires

Déséquilibre (Ø)= 0

Déséquilibre (<O,G,D>)= hauteur (G) – hauteur (D)

Remarque :

Un arbre T est H-équilibré si pour tout sous-arbre S de T on a :

Déséquilibre (s)Є -1,0,1


Proposition

Tout arbre H-équilibré ayant n nœuds a une hauteur h vérifiant :

log 2 (n+1) ≤ h + 1 <1,44 log 2 (n+2)

Preuve

a) Arbre H-équilibré de hauteur h contenant le plus de nœuds ?

Celui dont tous les niveaux sont complètement remplis

Déséquilibre o en chaque nœud

Nmax (h) : nombre de nœuds d’un tel arbre

Nmax (h) = 1+2Nmax (h-1)

Nmax (o) = 1


Nmax (h) = 2h+1 – 1

Donc pour tout arbre H-équilibré ayant n nœuds et de hauteur h :

n ≤ 2h+1 – 1

n+1 ≤ 2h+1

Log2 (n+1) ≤ h+1

b) Arbres H-équilibrés de hauteur h contenant le moins de nœuds ?

▪ si déséquilibre = -1 ou +1

dans tous les noeuds

Nmin (h) : nombre de nœuds d’un tel arbre

Nmin (o)=1, Nmin (1) = 2

Nmin (h) = 1+Nmin (h-1) + Nmin (h-2)


Soit F(h) = Nmin (h) + 1

On a :

F(h) = F(h-1) + F (h-2)

F(o)є = 2 ; F(1) = 3

Equation de récurrence de Fibonacci

F (h) = rh

F (h-1) = rh-1 ; F(h-2) = r h-2

rh = rh-1 + rh-2

rh-2 (-r2 + r + 1) = 0

≠ 0

r2-r-1=0

∆ = 1 + 4 = 5

r1 = 1+√5 = Ø, r2 = 1- √5 = Ø

2 2


La solution est de la forme

F(h) = λ1 Øh + λ 2 (Ø)h

F(o) = 2

2 = λ1 + λ2 (1)

F (1) = 3

3 = λ1 Ø + 2ג Ø

3 = λ1 (1+√5) + λ2 (1-√5)

2 2

6 = λ1 (1+√5) + λ2 (1-√5)

6 = λ1 + 5√ + 2ג (λ1 - 2ג )

6 = 2 + √5 ( 2ג - 1ג )

(2) 2ג - 1ג = 4

(1) + (2) :

1ג 2 = 4 + 2

√5

λ1 = 1 + 2 = √5 + 2

√5 √5


Ø = 1 + √5 2 Ø-1 = √5

2

λ1 = 2Ø-1+2 = 2Ø+1

2Ø-1 2Ø-1

λ2 = 2- 1ג

= 2-(√5 + 2) Øh + (√5 – 2)

√5 √5

F(h)= 1 (√5 + 2) Øh + (√5 – 2) Øh

√5


F (h) = 1 (Øh+3 – Øh+3)

√5

Nmin (h)+1 = 1 (Øh+3 – Øh+3)

√5

Donc pour tout arbre H-équilibré à n noeuds et de hauteur h

N+1 >1 (Øh+3 – Øh+3)

√5

Or :

-1 <Øh+3 = (1- √5 )h+3 <1

2

n+1>1 (Øh+3 – 1)

√5

1+ √5(n+1) ≥ Øh+3

Log Ø 1+√5(n+1) ≥ h+3

Log Ø √5(n+2) ≥ h+3


Log Ø (x) = (log2 (Ø))-1 log2 (Ø)

h+3 < logØ ( √5) + logØ (n+2)

< 2 + 1 log2 (n+2)

log2(Ø)

Remarque :

√5 < Ø2 = (1+√5)2

2

logØ (√5) < logØ (Ø2)

< 2

1 ~1,44

Log2 Ø

h+1 < 1,44 log2 (n+2)


Arbres AVL

Adelson – Velskii – Landis

Définition

Un AVL est un arbre binaire de recherche H-équilibré

Equilibrage ?

Rotations

Rotation droite, rotation gauche

A = q

p

p

q

u

w

v

u

v w

rd (A)

rz (A)

A, u, v, w : arbres binaires de recherche


Rotation gauche-droite

A = r

p q

rT

q p

T w

rgd (A)

A, T, u, v, w : arbres binaires de recherche

u v

w

u y

Remarque :

rotation gauche-droite = la composée d’une rotation gauche sur le sous-arbre gauche de A suivie d’une rotation droite sur A


Function RD (A : ARBRE) : ARBRE ;

Var Aux : ARBRE ;

Begin Aux : = A .g ; A .g : = Aux .d ;

Aux .d = A ; RD : = Aux

end RD ;

Function RGD (A : ARBRE) : ARBRE ;

Begin

A .g : = RG (A .g) ;

RGD : = RD (A)

end RGD ;


Adjonction dans un AVL et rééquilibrages

12

Exemple : 12, 3, 2, 5, 4, 7, 9, 11, 14, 10

E1 : E2 :

12

3

E3 :

12

3

2

rd

12 2

3

E4 : 12 2

3

5

E5 :

3

12 2

5

4

20

1

0

3

5 2

4 12

rd


E6 :

5 2

12

7

-2 3

4

12 3

5

7

rg

4 2

E7 :

12 3

5

7 4 2

9

2 9 3

5

7 4 2 12

rgd

9 3

5

7 4

E8 et E9 :

12 2

1411


9 3

5

7 4

rgd

2 12

14 11

10

11 3

5

9 4 12

14 7

2

10

-2

Principe général

Soit T= <r, G, D> un AVL

Supposons que l’adjonction de l’élément x ait lieu sur une feuille de G et qu’elle fasse augmenter de 1 la hauteur de G et que G reste un AVL

1) Si le déséquilibrage de T valait 0 avant l’adjonction, il vaut 1 après.

T reste un AVL et sa hauteur a augmenté de 1


2) Si le déséquilibrage de T valait -1 avant l’adjonction, il vaut 0 après.

T reste un AVL et sa hauteur n’est pas modifiée

3) Si le déséquilibre de T valait +1 avant l’adjonction, il vaut +2 après.

T n’est plus H-équilibré il faut le restructurer en AVL

adj dans sous-arbre

2 cas possibles gauche de G

adj dans sous-arbre

droit de G


b

a

..

..

rd

a

...

..

b

..

...

a

... ..

b

.....

c

. . .

. . .

rgd..

a c

b


ALGORITHME D’ADJONCTION DANS UN AVL

Ajoutavl : Arbre x Valeur Arbre

ajoutavl (Ø,x) = x

x ≤ r ajoutavl (<r, G, D>, x) =

rééquilibrage (<r, ajoutavl (G, x), D>)

x>r ajoutavl (<r, G, D>, x) =

rééquilibrage (<r, G, ajoutavl (D, x)>)

Rééquilibrage : Arbre Arbre

Déséquilibre : Arbre {-2,-1,0,1,2}


Déséquilibre (T)=0 (ou 1 ou -1) rééquilibrage (T) = T

Déséquilibre (T)=+2 et Déséquilibre (g (T))=+1

rééquilibrage (T) = rd (T)

Déséquilibre (T)=-2 et Déséquilibre (d (T))=-1

rééquilibrage (T)=rg (T)

Déséquilibre (T)=+2 et Déséquilibre (g(T))=-1

rééquilibrage (T)=rgd (T)

Déséquilibre (T)=-2 et Déséquilibre (d(T))=+1

rééquilibrage (T)= rdg (T)

Implémentation

type AVL = NŒUD ;

NŒUD = record deseq : -2..+2 ;

val : VALEUR ;

g, d : AVL

end ;


Procédure AJOUTAVL (var T : AVL ; x : VALEUR) ;

Var Y, A, AA, PP : AVL ; { AA est le père de A ; PP père de P }

begin { création du noeud à ajouter }

new (Y) : Y .val : = x ; Y .deseq :=0 ; y .g=nil ; y .d : = nil ; if T = nil then T:=Y

Else

Begin { descente à la recherche de la feuille, en mémorisant le dernier noeud pointé par A dont le déséquilibre est + 1 }

A : = T ; AA : = nil ; P : =T ; PP:= nil;

while P <> nil do begin

if P . deseq <> 0 then begin A : = P ; AA : = PP : P ;

If x ≤P .val then P : = P .g else P:z P .d

PP; end

{ adjonction }

If x ≤ PP .val then PP .g : = Y else PP .d : = Y ;

{modification du déséquilibre sur le chemin de A à Y}


P = A;

while P <> Y do if x ≤ P .val then begin

P .deseq : = P .deseq + 1 ; P : = P .g end else begin

P .deseq : = P .deseq - 1 ; P : = P .d end ;

{ rééquilibrage }

Case A .deseq of

O, +1,-1 : return ;

+2:

Case A .g deseq of

+1:begin A:=RD(A) ; A deseq :=0 ; A .d .deseq:=0 ;

End ;

-1:begin A:=RDG (A);

Case A .deseq oF

+1:begin A .g .deseq :=O ; A .d .deseq :=-1 end ;

-1:begin A .g .deseq :=-1 ; A .d .deseq :=0 end ;

0:begin A .g .deseq :=O ; A .d .deseq :=0 end ;

End ;

A .deseq :=0;

End ;

End ;


-2:{ cas symétrique du cas +2 }...

End { fin du cas }

If AA = mil then T:=A

Else if A .val ≤AA .val then AA .g : = A else

AA .d:=A

End ;

+2:

Case A .g deseq of

+1:begin A:=RD(A) ; A deseq :=0 ; A .d .deseq:=0 ;

End ; { descente }

End AJOUT VAL ;

Documents

ARBRES EQUILIBRES