Arbre bouc-émissaire

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, puis réinventé en 1993 par Igal Galperin et Ronald L. Rivest. Contrairement à la plupart des autres arbres auto-équilibrants, l'arbre bouc-émissaire se restructure plus rarement. Ainsi, la structure de l'arbre se déséquilibre peu à peu, jusqu'au moment où l'algorithme désigne un 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 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 bicolores et 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.

Exemple d'un arbre devant être rééquilibré.

Recherche du nœud bouc-émissaire

On choisit une constante d'équilibrage, par exemple $\alpha =2/3$. Le nœud (4.4) est à une profondeur 6. Comme $6>\log _{3/2}(11)$, 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 ${\text{taille}}({\text{enfant}}(u))>\alpha \cdot {\text{taille}}(u)$.

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.

• ${\text{taille}}(4.4)=1\leq {\frac {4}{3}}={\frac {2}{3}}{\text{taille}}(4.2)$ donc le nœud (4.2) n'est pas le bouc-émissaire.
• ${\text{taille}}(4.2)=2\leq 2={\frac {2}{3}}{\text{taille}}(4.5)$ donc le nœud (4.5) n'est pas le bouc-émissaire.
• ${\text{taille}}(4.5)=3\leq 12={\frac {2}{3}}{\text{taille}}(4)$ donc le nœud (4) n'est pas le bouc-émissaire.
• ${\text{taille}}(4)=6>{\frac {14}{3}}={\frac {2}{3}}{\text{taille}}(6)$ 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é.

Arbre bouc-émissaire rééquilibré

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

$${\text{taille}}(g)<\alpha \cdot {\text{taille}}(e);$$

$${\text{taille}}(d)<\alpha \cdot {\text{taille}}(e).$$

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 :

$${\text{hauteur(arbre)}}\leqslant \lfloor \log _{\frac {1}{\alpha }}({\text{taille(arbre)}})\rfloor$$

.

Propriétés

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

Démonstration

Par définition, nous avons pour chaque nœud e, de fils gauche g et de fils droit d : $taille(e)\geqslant {\frac {1}{\alpha }}max(taille(g),taille(d))$

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: $(n+1)\geqslant {\frac {1}{\alpha }}max(taille(d),taille(g))$

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

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

$(n+1)\geqslant {\frac {1}{\alpha }}({\frac {1}{\alpha }}^{hauteur(e)-1})$

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

Le principe de récurrence conclut.

 

Ainsi, par 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 $\alpha$-équilibré en hauteur : hauteur(arbre) $\leqslant \lfloor log_{\frac {1}{\alpha }}(taille(arbre))\rfloor +1$.

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 $\leqslant \lfloor log_{\frac {1}{\alpha }}(taille(d))\rfloor$

(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 $\leqslant \lfloor log_{\frac {1}{\alpha }}(taille(arbre))\rfloor$ + 1

 

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 $\alpha$-équilibré en poids.

Dans la suite, nous considérons α $\in$]1/2,1[fixé. Nous appellerons "nœud profond" tout nœud de profondeur supérieure à $\lfloor log_{\frac {1}{\alpha }}(taille(arbre))\rfloor$. 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. 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 classique. Ainsi, la complexité dans le pire des cas est en $O(\log(n))$.

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 $\leqslant \lfloor log_{\frac {1}{\alpha }}(n)\rfloor$). 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).

Démonstration qu'un nœud profond a nécessairement un ancêtre α-déséquilibré en poids

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) $\leqslant$ α*taille(y)

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

taille(x) $\leqslant \alpha ^{profondeur(x)}*taille(arbre)$

Nécessairement, la profondeur de x est au plus de $log({\frac {1}{\alpha }})(taille(arbre))$ (car $\alpha ^{log_{\frac {1}{\alpha }}(n)}*n=1$, 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.

 

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.

Démonstration

Si un arbre binaire contient un nœud profond $x_{0}$, alors l'ancêtre de $x_{0}$ le plus profond $x_{i}$ 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($x_{i})=i>log({\frac {1}{\alpha }})(taille(x_{i}))$

hauteur($x_{i-1})=i-1\leqslant log({\frac {1}{\alpha }})(taille(x_{i-1}))$

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

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

D'où, en élevant à la puissance ${\frac {1}{\alpha }}$ :

${\frac {1}{\alpha }}>taille(x_{i})/taille(x_{i-1})$

$taille(x_{i-1})>alpha*taille(x_{i})$

D'où le résultat.

 

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 $x_{i+1}$ comme suit:

taille($x_{i+1}$) = taille($x_{i}$) + taille(frère de $x_{i}$) + 1

où seule la taille du frère de $x_{i}$ 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 $\alpha$-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 comme racine du nouvel arbre. Ceci s'effectue en O(taille($x_{i}$)) 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 n'importe quel arbre binaire, puis on regarde si:

n $\leqslant \alpha$*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 $O(\log(n))$.

É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)).

Démonstration

Le coût de reconstruction du sous arbre de racine w est $O(\operatorname {taille} (w))$. Lorsque l'on cherche le nœud bouc-émissaire, on remonte de père en père depuis le nœud ajouté $x_{0}$ et on appelle successivement taille($x_{i}$) jusqu'à avoir $x_{i}=w$. 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($x_{i}$) < $\alpha *taille(x_{i+1})$.

Ainsi le coût total des appels à taille($x_{i}$) est:

$O(\sum _{i=0}^{k}taille(x_{k-i})=O(taille(x_{k})+\sum _{i=0}^{k-1}taille(x_{k-i-1})$ $=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}))$ $=O(taille(x_{k}))=O(taille(w))$

 

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 $O(n\cdot \log(n))$.

Démonstration

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($m\log(m)$). 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é) $taille(g)>alpha*taille(s)$ . Or $taille(s)=1+taille(g)+taille(d)$.

On a donc $taille(g)>{\frac {\alpha *taille(d)}{1-\alpha }}$ . Enfin $(2\alpha -1)taille(s)\leq (taille(g)-taille(s))$. La dernière fois qu'un sous arbre contenant s a été reconstruit, on avais $taille(g)-taille(s)\leq 1$. On a donc fait entre-temps $(2\alpha -1)taille(s)-1$ 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 $\leqslant \alpha$*MaxNoeudsComptés. On a alors mis de côté MaxNoeudsComptés-n $\leqslant (\alpha -1)n$ crédits qui permettent de payer la reconstruction en O(n).

 

Étymologie

Le nom d'arbre bouc-émissaire est « 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 ».

Voir également

• Arbre splay
• Arbre enraciné
• Rotation d'un arbre binaire de recherche
• Arbre AVL
• B Arbre

Liens externes

• Applet Arbre bouc-émissaire par Kubo Kovac
• Galperin, Igal; Rivest, Ronald L. (1993). Scapegoat trees (PDF). Proceedings of the fourth annual ACM-SIAM 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).
• Pat Morin, Open Data Structures (in pseudocode), 0.1G β (lire en ligne), « Chapter 8 - Scapegoat Trees »
• Les arbres bouc-émissaire par Domicia Herring
• Exemple d'insertion par Rahul Aggarwal and Sahil Chhabra
• Publication de Galperin et Rivest décrivant les arbres bouc-émissaires