Voir la source de Arbre bouc-émissaire

{{À déjargoniser|date=décembre 2019}}
{{À désangliciser}}
Un '''arbre bouc-émissaire''', en [[informatique]], plus précisément en [[algorithmique]], est un [[arbre binaire de recherche]] auto-équilibrant. Ce type d'arbre a été inventé en 1989 par Arne Andersson<ref name=anderson1>{{lien conférence|titre=Improving partial rebuilding by using simple balance criteria |url=http://user.it.uu.se/~arnea/abs/partb.html |citeseerx=10.1.1.138.4859 |journal=Journal of Algorithms |prénom=Arne |nom=Andersson |conférence=Proc. Workshop on Algorithms and Data Structures |pages=393–402 |année=1989 |éditeur=Springer-Verlag |doi=10.1007/3-540-51542-9_33}}</ref>, puis réinventé en 1993 par Igal Galperin et [[Ronald L. Rivest]]<ref name=galperin_rivest>{{lien conférence|prénom1=Igal |nom1=Galperin  |prénom2=Ronald L. |nom2=Rivest |lien auteur2=Ronald L. Rivest |titre=Scapegoat trees |journal=Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms |pages=165–174 |année=1993 |url=http://people.csail.mit.edu/rivest/pubs/GR93.pdf |citeseerx=10.1.1.309.9376 |isbn=0-89871-313-7 |éditeur=[[Society for Industrial and Applied Mathematics]] |lieu=Philadelphia}}</ref>. Contrairement à la plupart des autres arbres auto-équilibrants, l'arbre bouc-émissaire se restructure plus rarement. Ainsi, la structure de l'arbre se [[Arbre équilibré|déséquilibre ]] peu à peu, jusqu'au moment où l'algorithme désigne un [[sommet (théorie des graphes)|nœud]] ''bouc-émissaire'', désigné comme responsable du déséquilibre. On y effectue alors un rééquilibrage pour que l'arbre retrouve une structure satisfaisante. 

== Intérêt ==
Le principal intérêt de l'arbre bouc-émissaire concerne sa complexité spatiale. Il s'agit du premier [[arbre (informatique)|arbre]] [[arbre binaire|binaire]] de recherche dont les opérations sont en O(log(n)) en moyenne où n est le nombre de nœuds, et qui ne prend pas plus de mémoire qu'un arbre binaire de recherche. En effet, contrairement aux arbres [[Arbre bicolore|bicolores]] et [[Arbre AVL|AVL]] qui stockent dans les nœuds des informations supplémentaires (telles que sa couleur ou sa hauteur), le bouc-émissaire ne garde en mémoire que l'étiquette du nœud et ses deux pointeurs vers ses enfants. Ainsi, cet arbre est plus économe en mémoire.

== Exemple ==

=== Insertion ===
Considérons l'arbre suivant, où le nœud 4.4 vient tout juste d'être inséré. Cet arbre est un arbre binaire de recherche : chaque nœud est plus grand que tous les nœuds de son sous-arbre gauche et plus petit que les nœuds dans son sous-arbre droit. Si un arbre possède 11 nœuds, on dira qu'il est de taille 11. [[Fichier:Arbre bouc-émissaire.png|vignette|Exemple d'un arbre devant être rééquilibré.|alt=|centré|498x498px]]

=== Recherche du nœud bouc-émissaire ===
On choisit une constante d'équilibrage, par exemple <math> \alpha=2/3 </math>. Le nœud (4.4) est à une profondeur 6. Comme <math> 6>\log_{3/2}(11) </math>, notre arbre n'est donc pas 2/3-équilibré. Un rééquilibrage est nécessaire. Pour cela, nous allons trouver le nœud responsable du déséquilibre : le nœud ''bouc-émissaire''. On définit la taille d'un nœud comme étant la taille du sous-arbre enraciné sur ce nœud. La condition de bouc-émissaire est <math> \text{taille}(\text{enfant}(u)) > \alpha \cdot \text{taille}(u) </math>.

Dans l'exemple précédent, on insère le nœud 4.4, et on remonte de parent en parent pour trouver le bouc-émissaire. 

* <math>\text{taille}(4.4)=1\leq \frac{4}{3} = \frac{2}{3} \text{taille}(4.2)</math> donc le nœud (4.2) n'est pas le bouc-émissaire.
* <math>\text{taille}(4.2)=2\leq 2 = \frac{2}{3} \text{taille}(4.5)</math> donc le nœud (4.5) n'est pas le bouc-émissaire.
* <math>\text{taille}(4.5)=3\leq 4 = \frac{2}{3} \text{taille}(4)</math> donc le nœud (4) n'est pas le bouc-émissaire.
* <math>\text{taille}(4)=6 > \frac{14}{3} =  \frac{2}{3} \text{taille}(6)</math> donc le nœud (6) est le bouc-émissaire.
La section théorique explique plus en détail ce processus.

=== Rééquilibrage ===
Une fois que le bouc-émissaire a été trouvé, on rééquilibre tout son sous-arbre. Ici, le nœud (6) a été choisi, donc les 7 éléments de son sous-arbre sont placés comme dans un arbre binaire de recherche. On observe que ceci réduit sa profondeur : l'arbre entier est mieux équilibré.[[Fichier:Arbre bouc-émissaire rééquilibré.png|vignette|Arbre bouc-émissaire rééquilibré|alt=|centré|483x483px]]

== Théorie ==
Dans toute cette partie, un arbre sera la donnée d'un nœud noté "e" et de ses enfants gauche "g" et droite "d". La taille d'un nœud e, notée taille(e) est le nombre de nœuds qu'il y a dans l'arbre enraciné en ce nœud.

=== Définitions ===
Un arbre binaire de recherche est dit ''équilibré'' s'il y a autant de nœuds à droite de la racine qu'à gauche. On relâche cette notion en introduisant deux définitions paramétrées. Un nœud e est un ''nœud α-équilibré en poids'' si 

<math display="block"> \text{taille}(g) <\alpha \cdot \text{taille}(e); </math><math display="block"> \text{taille}(d) <\alpha \cdot \text{taille}(e). </math> 

Un arbre α-équilibré en poids est alors un arbre n'ayant que des nœuds α-équilibrés en poids. De façon similaire, on dira qu'un arbre est α-équilibré en hauteur si :<math display="block"> \text{hauteur(arbre)} \leqslant \lfloor \log_{\frac{1}{\alpha}}(\text{taille(arbre)}) \rfloor</math>.

=== Propriétés ===

'''Propriété 1.''' Un arbre α-équilibré en poids est également α-équilibré en hauteur.

{{Boîte déroulante/début|titre = Démonstration}}
Par définition, nous avons pour chaque nœud e, de fils gauche g et de fils droit d :
<math> taille(e) \geqslant \frac{1}{\alpha}max(taille(g),taille(d)) </math>

Ainsi, par récurrence sur la taille de l'arbre, on constate que :
* Pour un arbre de taille 1, la propriété est vérifiée
* Pour un arbre de taille n+1, nous avons alors: <math> (n+1) \geqslant \frac{1}{\alpha}max(taille(d),taille(g)) </math>

Or, par hypothèse de récurrence, comme g et d sont de tailles strictement inférieure à n+1, <math> taille(g) \geqslant \frac{1}{\alpha}^{hauteur(g)} </math> et <math> taille(d) \geqslant \frac{1}{\alpha}^{hauteur(d)} </math>

Donc finalement: <math> (n+1) \geqslant \frac{1}{\alpha}max(\frac{1}{\alpha}^{hauteur(g)},\frac{1}{\alpha}^{hauteur(d)}) </math>

<math> (n+1) \geqslant \frac{1}{\alpha}(\frac{1}{\alpha}^{hauteur(e)-1}) </math>

D'où finalement: <math> (n+1) \geqslant \frac{1}{\alpha}^{hauteur(e)} </math>

Le principe de récurrence conclut.
{{Boîte déroulante/fin}}

Ainsi, par [[Contraposition|contraposée]], un arbre bouc-émissaire étant le plus petit arbre non α-équilibré en poids, il ne peut être un arbre α-équilibré en hauteur (c'est d'ailleurs un premier critère discriminatoire dans la recherche de notre bouc-émissaire). Cependant, on dispose de la propriété suivante.

'''Propriété 2.''' Un arbre bouc-émissaire est presque <math> \alpha</math>-équilibré en hauteur : hauteur(arbre) <math> \leqslant \lfloor log_{\frac{1}{\alpha}}(taille(arbre)) \rfloor + 1 </math>.

{{Boîte déroulante/début|titre = Démonstration}}
La démonstration repose sur le fait que notre arbre bouc émissaire est celui de plus petite hauteur violant la propriété α-équilibré en poids.

De fait, en notant h la hauteur de cet arbre, et en supposant - sans perdre de généralité - que son fils de plus grande taille est le droit, on a :

h-1 <math> \leqslant \lfloor log_{\frac{1}{\alpha}}(taille(d)) \rfloor </math>

(En effet, dans le cas contraire, on aurait le fils droit qui briserait également la propriété α-équilibré en poids tout en étant de hauteur strictement inférieure à celle de notre bouc-émissaire: absurde !)

D'où finalement, par croissance du logarithme (taille(arbre) > taille(d)):

h <math> \leqslant \lfloor log_{\frac{1}{\alpha}}(taille(arbre)) \rfloor </math> + 1
{{Boîte déroulante/fin}}

Ceci constitue donc un premier critère discriminatoire dans la recherche de notre arbre bouc-émissaire.

De plus, cette propriété montre que la hauteur d'un arbre bouc-émissaire est majorée, à l'instar des arbres rouge-noir. La principale différence provient du moment où s'effectue le rééquilibrage: l'arbre bouc-émissaire le fait à la première rencontre avec un nœud non <math> \alpha</math>-équilibré en poids.

Dans la suite, nous considérons α <math> \in </math>]1/2,1[fixé. Nous appellerons "nœud profond" tout nœud de profondeur supérieure à <math> \lfloor log_{\frac{1}{\alpha}}(taille(arbre)) \rfloor </math>. C'est la détection de ces derniers qui enclenche le processus de rééquilibrage.

== Opérations==
Dans cette section, nous détaillons les opérations de recherche, d'insertion et de suppression dans un arbre bouc-émissaire<ref name="operations">{{ouvrage|lire en ligne=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf|titre=On Consulting a Set of Experts and Searching |chapter=Chapter 3 - Scapegoat Trees |url=http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf |prénom=Igor |nom=Galperin|lien auteur= Igor Galperin |consulté le=2019-12-19}}</ref>. On note n = taille(A), où A désigne l'arbre bouc-émissaire sur lequel on effectue les opérations. La valeur de n est stockée. Au cours de l'insertion et la suppression, on met à jour la valeur de n. 

=== Recherche ===
L'algorithme de recherche est le même que pour un [[Arbre binaire de recherche#Recherche|arbre binaire de recherche]] classique. Ainsi, la complexité dans le pire des cas est en <math> O(\log(n)) </math>.

=== Insertion ===
Le principe de l'insertion repose sur la mémorisation de la profondeur à laquelle le nouveau nœud est inséré. On commence par insérer aux feuilles l'élément x. On regarde récursivement si l'élément doit être ajouté à gauche ou à droite du nœud et on incrémente à chaque étape la valeur de la profondeur d d'insertion. On vérifie si l'arbre ainsi construit est α-équilibré en taille en testant que d <math> \leqslant \lfloor log_{\frac{1}{\alpha}}(n) \rfloor </math>). Si ce n'est pas le cas, un rééquilibrage est nécessaire.

On cherche alors le sous-arbre ''bouc émissaire'' dont la racine va subir le rééquilibrage. Celle-ci est un ancêtre du nœud inséré et n'est pas α-équilibré en poids (il y aura toujours un tel nœud).

{{Boîte déroulante/début|titre = Démonstration qu'un nœud profond a nécessairement un ancêtre α-déséquilibré en poids|contenu=}}
En effet, par l'absurde, si x est un nœud profond n'ayant que des parents α-équilibrés en poids, on a pour son parent y :

taille(x) <math> \leqslant </math> α*taille(y)

Et donc, par récurrence sur le chemin entre x et la racine, on a :

taille(x) <math> \leqslant \alpha^{profondeur(x)}*taille(arbre) </math>

Nécessairement, la profondeur de x est au plus de <math> log(\frac{1}{\alpha})(taille(arbre)) </math> (car <math> \alpha^{log_{\frac{1}{\alpha}}(n)}*n = 1 </math>, donc une plus grande profondeur induirait que x est de taille nulle), ce qui est contradictoire avec le fait que x soit un nœud profond.
{{Boîte déroulante/fin}}

Ce nœud peut être trouvé en remontant de parent en parent à partir du nœud inséré. Le rééquilibrage d'un tel sous-arbre assure la propriété d'α-équilibré en taille dans tout l'arbre.

{{Boîte déroulante/début|titre = Démonstration|contenu=}}
Si un arbre binaire contient un nœud profond <math> x_0 </math>, alors l'ancêtre de <math> x_0 </math> le plus profond <math> x_i </math>  qui n'est pas α-équilibré en hauteur n'est pas non plus
α-équilibré en poids.

En effet, un tel nœud xi vérifie :

hauteur(<math> x_i) = i > log(\frac{1}{\alpha})(taille(x_i)) </math>

hauteur(<math> x_{i-1}) = i-1 \leqslant log(\frac{1}{\alpha})(taille(x_{i-1})) </math>

Ainsi, en soustrayant les deux inégalités :

1 > <math> log_{\frac{1}{\alpha}}(taille(x_i)) - log_{\frac{1}{\alpha}}(taille(x_{i-1}))
  = log_{\frac{1}{\alpha}}(taille(x_i)/taille(x_{i-1}) </math>

D'où, en élevant à la puissance <math> \frac{1}{\alpha} </math> :

<math> \frac{1}{\alpha} > taille(x_i)/taille(x_{i-1}) </math>

<math> taille(x_{i-1}) > alpha*taille(x_{i}) </math>

D'où le résultat.
{{Boîte déroulante/fin}}

L'intérêt de remonter ainsi dans l'arbre pour trouver le nœud bouc-émissaire ne vérifiant pas les conditions

* taille(enfant gauche) < α*taille(nœud)
* taille(enfant droite) < α*taille(nœud)

est que nous disposons déjà des tailles d'un des enfants et du nœud.

Il y a dès lors moins de calcul à effectuer. On sait que le cas de base (la hauteur du nœud inséré qui est une feuille) est égal à 1. Il suffit alors de remonter l'arbre comme décrit précédemment, en calculant la taille de chaque nouveau nœud <math> x_{i+1} </math> comme suit:

taille(<math>x_{i+1}</math>) = taille(<math>x_{i}</math>) + taille(frère de <math>x_{i}</math>) + 1

où seule la taille du frère de <math> x_i </math> reste à déterminer.

Une fois le nœud bouc-émissaire localisé, on rééquilibre l'arbre dont il est racine (en le remplaçant par un autre arbre contenant les mêmes noeuds mais parfaitement <math> \alpha </math>-balancé). Une manière de faire est de parcourir les noeuds de l'arbre en les triant par valeur, puis choisir récursivement la valeur [[Médiane (statistiques)|médiane]] comme racine du nouvel arbre. Ceci s'effectue en O(taille(<math>x_i</math>)) en temps.

=== Suppression ===
Contrairement à la plupart des autres types d'arbre, la suppression est plus simple que l'insertion. Pour ce faire, il faut garder en mémoire une valeur en plus de la structure d'arbre, que nous appellerons MaxNoeudsComptés. Il s'agit du plus grand nombre de noeuds que l'arbre a pu compter depuis le dernier rééquilibrage complet de l'arbre.

Ainsi, lorsqu'il y a un rééquilibrage, MaxNoeudsComptés est réinitialisé à la taille de l'arbre. À chaque insertion, MaxNoeudsComptés = max(MaxNoeudsComptés,n+1).

Ensuite, pour supprimer le nœud, on fait comme dans [[Arbre binaire de recherche#Suppression|n'importe quel arbre binaire]], puis on regarde si:

n <math> \leqslant \alpha </math>*MaxNoeudsComptés

Si c'est le cas, alors on rééquilibre entièrement l'arbre, en réinitialisant MaxNoeudsComptés.

== Complexité ==
En ignorant les opérations de rééquilibrage et de recherche d'un arbre bouc-émissaire, les complexités de l'insertion, suppression et recherche sont proportionnelles à la hauteur de l'arbre. Elles sont en <math> O(\log(n)) </math>. 

Étudions la part de complexité qui n'est pas encore prise en compte. 

'''Lemme.''' lors de l'insertion d'un élément, le coût pour trouver le nœud bouc-émissaire w et le reconstruire est O(taille(w)).

{{Boîte déroulante/début|titre = Démonstration|contenu=}}
Le coût de reconstruction du sous arbre de racine w est <math>O(\operatorname{taille}(w))</math>. Lorsque l'on cherche le nœud bouc-émissaire, on remonte de père en père depuis le nœud ajouté <math>x_{0}</math> et on appelle successivement taille(<math>x_{i}</math>) jusqu'à avoir <math>x_{i}=w</math>. Comme w est le premier nœud de cette séquence qui ne soit pas alpha-équilibré en poids, on a pour tout i compris entre 0 et k-2 taille(<math>x_{i}</math>) < <math> \alpha*taille(x_{i+1})</math>.

Ainsi le coût total des appels à taille(<math>x_{i}</math>) est:

<math>O(\sum_{i=0}^k taille(x_{k-i})=O(taille(x_k)+\sum_{i=0}^{k-1} taille(x_{k-i-1})</math>
<math>=O(taille(x_k)+\sum_{i=0}^{k-1} \alpha^i*taille(x_k)=O(taille(x_k)(1+\sum_{i=0}^{k-1} \alpha^i))</math>
<math>=O(taille(x_k))=O(taille(w))</math>

{{Boîte déroulante/fin}}

'''Théorème.''' En partant d'un arbre vide, une séquence de m opération d'insertion ou suppression a une complexité amortie de <math> O(n\cdot\log(n)) </math>. 

{{Boîte déroulante/début|titre = Démonstration|contenu=}}
On va prouver cette complexité amortie avec un système de crédit. On image que chaque nœud va conserver des crédits qui correspondent à un certain temps constant c. Ce crédit de temps pourra être utilisés pour les opérations de reconstruction et de recherche de bouc émissaire.

Lors d'une insertion ou d'une suppression, on ajoute un crédit à chaque nœud parcouru sur le chemin emprunté et un crédit supplémentaire est mis "de côté"  à chaque suppression. 
On "paye" ainsi O(<math>m\log(m)</math>). Il reste à vérifier que ce crédit est suffisant pour compenser les opérations non prises en compte (à savoir les rééquilibrages).

Lorsqu'on doit reconstruire le bouc émissaire s=(w,g,d) où w racine, g sous arbre de gauche et d sous arbre de droite.  On a (sans perte de généralité) <math> taille(g) > alpha*taille(s) </math> . Or <math> taille(s) = 1+taille(g)+taille(d) </math>. 

On a donc <math> taille(g) > \frac{\alpha*taille(d)}{1-\alpha} </math> . Enfin  <math> (2\alpha-1)taille(s) \leq (taille(g)-taille(s)) </math>.
La dernière fois qu'un sous arbre contenant s a été reconstruit, on avais <math> taille(g)-taille(s) \leq 1 </math>. On a donc fait entre-temps <math> (2\alpha-1)taille(s) -1 </math> opérations affectant cet arbre et on a donc autant de crédit pour payer O(taille(w)) et reconstruire s.

Si on reconstruit l'arbre lors du suppression, on a 
n <math> \leqslant \alpha </math>*MaxNoeudsComptés. On a alors mis de côté MaxNoeudsComptés-n <math> \leqslant (\alpha-1)n </math> crédits qui permettent de payer la reconstruction en O(n).
{{Boîte déroulante/fin}}

== Étymologie ==
Le nom d'arbre bouc-émissaire est {{citation|basé sur la sagesse populaire selon laquelle, dès que quelque chose ne va pas, la première chose que les gens auront tendance à faire est de trouver quelqu'un à blâmer pour cela (le [[bouc-émissaire]]). Une fois ce blâme clairement établi, on peut laisser au bouc-émissaire le soin de résoudre le problème}}<ref name="opendatastructures">{{ouvrage|lire en ligne=http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html|titre=Open Data Structures (in pseudocode) |chapter=Chapter 8 - Scapegoat Trees |url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html |edition=0.1G β |prénom=Pat |nom=Morin|lien auteur= Pat Morin |consulté le=2017-09-16}}</ref>.

== Voir également ==
* [[Arbre splay]]
* [[Arbre enraciné]]
* [[Rotation d'un arbre binaire de recherche]]
* [[Arbre AVL]]
* [[B Arbre]]

== Notes et références ==
{{Références}}

== Liens externes ==
*[http://people.ksp.sk/~kuko/bak/index.html Applet Arbre bouc-émissaire] par Kubo Kovac
* Galperin, Igal; Rivest, Ronald L. (1993). [http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-700.pdf Scapegoat trees (PDF)]. Proceedings of the fourth annual ACM-SIAM [[Symposium on Discrete Algorithms|Symposium on Discrete algorithms]]. Philadelphia: Society for Industrial and Applied Mathematics. {{p.|165–174}}. [[CiteSeerX]] 10.1.1.309.9376. {{ISBN|0-89871-313-7}}.
*{{ouvrage|lire en ligne==http://opendatastructures.org/versions/edition-0.1g/ods-python/8_Scapegoat_Trees.html |titre=Open Data Structures (in pseudocode) |chapter=Chapter 8 - Scapegoat Trees |url=http://opendatastructures.org/versions/edition-0.1g/ods-python/ods-python-html.html |edition=0.1G β |prénom=Pat |nom=Morin |consulté le=2017-09-16}}
<!--*{{cite techreport |url=http://people.scs.carleton.ca/~maheshwa/Honor-Project/scapegoat.pdf |title=A Study and and Implementation of Scapegoat Trees |first=Phuong |last=Dao |date=15 avril 2006 |type=honour project report |publisher=Carleton University}}-->
*[http://www.domiciaherring.com/scapegoat-trees Les arbres bouc-émissaire] par Domicia Herring
*[https://www.geeksforgeeks.org/scapegoat-tree-set-1-introduction-insertion/ Exemple d'insertion] par Rahul Aggarwal and Sahil Chhabra
* [http://cg.scs.carleton.ca/~morin/teaching/5408/refs/gr93.pdf Publication de Galperin et Rivest décrivant les arbres bouc-émissaires]

{{Palette|Arbres informatiques}}

{{Portail|informatique}}

[[Catégorie:Arbre (structure de données)]]