Rotation dans les ABR

Sommaire

1- introduction

1-1 définition et utilité d'un ABR

2- Description de problème

2-1 Notion d' ABR équilibré

2-2 le problème des ABR

3- Pistes des développements

3-1 alogorithme de transformation d'un ABR en peigne droit

3-2 la hauteur d'un arbre équilibré

3-3 le nombre de rotations maximal pour équilibrer un arbre

4-Exercice
5-QCM
6-Bibliographie

introduction :

un arbre de recherche binaire (ABR) est une structure de donnée qui permet de représenter un ensemble de valeurs ,si l'on dispose une relation d'ordre sur ces valeurs .ABR est utilisé surtout dans certain algorithmes de tri car il permet de faire  des opérations rapides pour rechercher une valeur , insérer ou supprimer une valeur .

c'est un arbre  dans lequel chaque nœud possède une valeur qui est de type entier , chaqu'un contient au plus un sous-arbre gauche dont toutes les valeurs sont plus petites que celles de la racine, et un sous-arbre droit, sont toutes les valeurs sont plus grandes que la racine.

Description du problème:

Pour mieux éclaircir notre problème on commence d'abord par définir c'est quoi un arbre équilibré

un ABR équilibré est un arbre binaire de recherche tel  que les hauteurs des deux sous arbres de tout nœud de l’arbre différent de 1 au plus :     |h(Ag)-h(Ad)| ≤1 .

un arbre équilibré
arbre désequilibré

Notre problème c'est que les opérations : insertion et suppression sont couteuses dans un ABR déséquilibré surtout quand le sommet se situe loin dans l’arbre par exemple dans l’exemple précédent si on veut supprimer le nœud qui contient la valeur « 1 » , on est obligé de passer par tout les nœuds  de l’arbre et c’est pareil aussi pour l’insertion .

Pour pallier à ce problème il faut transformer l’arbre déséquilibré en un arbre équilibré, pour se faire il existe une manipulation sur ABR qui s’appelle « rotation » et il existe deux types de rotations : rotations gauche et rotation droite .

Pistes de développement

 Une rotation droite autour du sommet x d'un arbre binaire de recherche consiste à faire remonter le sommet x  et à faire descendre son pére qui deveindra son fils droit , et son ancien fils droit devient fils gauche de pére ,  sans invalider l'ordre des éléments. L'opération inverse s'appelle rotation gauche autour du sommet  y

rotation gauche et droite

1- Est-ce que tout ABR peut être transformer en un peigne droit à l’aide de rotation ?

 Oui , Soit T un ABR ,  on  peut le transformer en peigne droit en faisant des rotations  droite à la racine , au fur  et à mesure on met à jour la racine  et on s’arrête quand  le fils gauche de la racine égal à  Nill , ce qui montre les deux algorithmes  ci-dessous :

Rotation_droite (T,x) /*T un  ABR et x le nœud sur lequel on va effectuer la rotation 
Y<- gauche [x]
 Gauche[x]<- droite [x]
Si (droite[x] != Nill)  alors     
  P[droite[y]] <-x /*on met à jour le père de y qui sera égal a x */
p[y]<-p[x]
si p[x]=NILL alors Root[T]<-y
Sinon Si x=droite [p[x]] alors droite[p[x]] <-y           
 Sinon gauche [p[x]]<-y
droite [y]<-x
p[x]<-y  
Transformation_peigne_droit  (T)
Tantque (droite [Root[T]] != Nill ) faire  
Rotation_droite (T,Root[T])    

2- la hauteur d’un arbre équilibré : Soit n le nombre de sommets dans l’arbre et h la hauteur :

                      log2 (1+n) ≤ 1+ h ≤ 3 /2 log2(n + 1)

preuve :

Montrons que :  log2(1+n) ≤ 1+ h , elle est vérifié pout tout arbre binaire (même si n’est pas équilibré ) 

log2(1+n) ≤ 1+ h   => n ≤ 21+h  -1

 on sait que le nombre maximum de sommets dans un arbre binaire dans le niveau i est 2i  donc le nombre maximum de tous l’arbre de hauteur h est

  • qui est une suite géométrique donc la somme égal à  2h+1   -1
  • n ≤ 21+h  -1  => log2 (1+n) ≤ 1+ h

Montrons que : 1+ h ≤ 3 /2 log2(n + 1)  (c’est ce cas la qui assure que  l’arbre soit  équilibré )

  Soit uh  le nombre minimal de nœuds d’un arbre de hauteur h > 0.

On a u0 = 1, u1 = 2, et :

 ∀h ∈ N, uh+2 = uh + uh+1 + 1.

Soit, après résolution : uh = Aαh + Bβh − 1, avec :

A = (5 + 2√ 5)/ 5 ≈ 1, 89,  B = (5 − 2 √ 5 )/5 ≈ 0, 11,  α = (1 + √ 5)/ 2 ≈ 1, 62,

β = (1 − √ 5)/ 2 ≈ −0, 62.

 On a donc : n > uh > Aαh − 2,  n + 2 > Aαh ,

h < logα(n + 1) + logα ( (1/ A )·( n + 2/ n + 1)) =>

h < logα(n + 1) = (ln 2/ ln α )log2(n + 1)=>

 h < 3 /2 log2(n + 1).

inégalité est vraie pour h = −1

3- Le nombre maximale de rotations  pour équilibrer un arbre T :

On commence d’abord par définir c’est quoi triangulation :

Trianguler un ensemble de points du plan, c’est relier ces points par des segments de façon à former des triangles. Les points seront appelés les sommets. Il faut néanmoins respecter quelques règles :

 (a) Les seuls polygones autorisés sont des triangles.

 (b) Tous les sommets doivent faire partie d’au moins un triangle.

(c) La triangulation est convexe.

Si deux arbres T ,T’ ont la même  taille ( nombre de sommets ) , on peut toujours transformer T à T’ en utilisant plusieurs rotations . La distance de rotation dist (T, T ') est le nombre minimal de rotations nécessaires dans la transformation, et d (n) désignera le maximum de dist (T,T ′) pour T, T ′ de taille n.Il existe une correspondance univoque entre les arbres de taille n et les triangulations d'un (n + 2) angles . Sous cette correspondance, une rotation dans un arbre se traduit par un retournement de la triangulation associée, c’est-à-dire l’opération d’échange de diagonales dans le quadrilatère formé par deux triangles adjacents. Donc d (n) est aussi le retournement maximal distance entre deux triangulations d'un (n + 2) angles .

  En utilisant un argument de comptage simple, D. Sleator, R. Tarjan et W. Thurston ont  prouvé  l'inégalité d (n) ≤2n − 6 pour n≥ 11 et, Un argument de force brute donne d (n) = 2n - 6 pour 11≤n ≤19.

Exercice :

a travers cet article on a trouvé le nombre maximale de rotations pour équilibrer un arbre , maintenant en partant d'un peigne gauche combien de rotations qu'on va faire pour équilibrer le peigne le plus tôt possible, autrement quel est nombre minimale d'étapes pour l'équilibrer ?

pour le moment on a pas la valeur exacte mais nous établissons une limite inférieure qui est n-1

QCM :

pour tester votre compréhension je vous recommande vivement de passer le Quiz qui se trouve dans la page gérer les quiz qui a l'identifiant 6 "mtouchquiz id=6" .

Animation :

voici une animation d'un arbre équilibré obtenu d'un peigne droit a 4 sommets

Bibliographie :

https://fr.wikipedia.org/wiki/Rotation_d%27un_arbre_binaire_de_recherche

https://users.cs.duke.edu/~reif/courses/alglectures/skiena.lectures/lecture10. pdf

https://info-llg.fr/option-mp/pdf/01.slide.pdf

0 Cliquer pour recommander cet article