Arbre splay

Un arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue. Cette structure de données a été inventée par Daniel Sleator et Robert Tarjan en 1985.

Toutes les opérations courantes sur les structures de données sont suivies d'une opération basique nommée évasement (splaying en anglais). Évaser un arbre autour d'un certain élément consiste à réarranger l'arbre afin que cet élément soit placé à la racine tout en conservant la structure ordonnée de l'arbre. Une manière d'obtenir cela est d'effectuer une recherche ordinaire sur un arbre binaire en mémorisant le chemin suivi, puis d'effectuer une série de rotations d'arbre afin d'amener l'élément à la racine. D'autres implémentations permettent d'effectuer ces deux opérations en une seule passe.

Avantages

Les performances des arbres évasés reposent sur le fait qu'ils s'auto-optimisent, c'est-à-dire que les nœuds fréquemment utilisés vont se rapprocher de la racine où ils pourront être accédés de manière rapide. Dans le pire cas toutefois, la plupart des opérations pourraient avoir une complexité linéaire ; en pratique la plupart ont une complexité moyenne logarithmique.

Rapprocher les nœuds fréquemment utilisés de la racine est avantageux dans la plupart des situations pratiques (une propriété appelé le principe de localité) et en particulier pour implémenter des algorithmes de cache ou de ramasse-miettes.

Finalement, l'absence de données secondaires (telles la hauteur des sous-arbres dans les arbres AVL) permet un stockage de donnée relativement compact.

Désavantages

Le désavantage le plus évident des arbres évasés est qu'ils peuvent dans certains cas terminer avec une hauteur linéaire dans leur taille ce qui peut affecter significativement les performances de toutes les opérations. Une variante randomisée permet cependant de tempérer ce défaut.

Plus subtilement, le fait qu'une simple lecture de l'arbre modifie sa structure peut poser de sérieuses difficultés dans le cas où la base de données représentée doit être accédée par plusieurs clients simultanément. Des implémentations concurrentes de l'accession sont alors parfois nécessaires.

Opérations

Insertion

Pour insérer un nouveau nœud dans un arbre évasé :

• On commence par insérer ce nœud comme pour un arbre binaire de recherche.
• On évase ensuite l'arbre sur le nœud inséré afin de le placer à la racine.

Suppression

Pour supprimer un nœud, on procède de façon similaire au cas d'un arbre binaire de recherche. Si le nœud a deux enfants, on échange la valeur de ce dernier avec son successeur direct dans ses sous-arbres et on cherche à supprimer le nœud dont on vient d'échanger la valeur. Dans tous les cas, on va ensuite évaser l'arbre sur le parent du nœud supprimé.

Évasement

Pour réaliser un évasement sur le nœud $X$, on effectue une série d'étapes d'évasement, chacune rapprochant $X$ de la racine. Afin de déterminer quelle étape doit être réalisée, trois facteurs doivent être pris en compte :

• $X$ est-il l'enfant à droite ou à gauche de son parent $P$,
• $P$ est-il la racine,
• $P$ est il l'enfant à droite ou à gauche de son parent, le grand-parent $G$.

Après chaque étape, $X$ aura pris la place de $G$ (jusqu'à finir à la racine).

Deux opérations, zig et zag permettent alors de former toutes les combinaisons devant être réalisées : zig, zig-zig, zig-zag, zag, zag-zag et zag-zig. Les trois dernières étant les symétriques des trois premières nous nous concentrerons sur celles-là.

Zig

Une étape Zig sur un arbre évasé.

Dans le cas où $P$ est la racine, l'arbre est pivoté sur le lien entre $X$ et $P$. Cette étape n'existe que pour gérer les problèmes de parité et ne sera effectuée qu'en dernière opération (donc après une série de zig-zig et autres).

Zig-zig

Une étape Zig-zig sur un arbre évasé dans le cas ou les deux nœuds X et P sont des enfants à gauche.

Lorsque $X$ et $P$ sont tous les deux enfants à droite (resp. gauche), l'arbre est alors pivoté deux fois : d'abord sur le lien entre $P$ et $G$, puis à nouveau sur le lien entre $X$ et $P$.

Zig-zag

Une étape Zig-zag sur un arbre évasé, X étanbt initialement l'enfant à droite de P, lui même l'enfant à gauche de G.

Lorsque $X$ et $P$ sont deux enfants différents (droite et gauche, ou vice-versa), on effectue d'abord une rotation sur le lien entre $X$ et $P$ puis une deuxième sur le lien entre $P$ et $G$.

Bibliographie

• (en) Daniel D. Sleator et Robert E. Tarjan, « Self-Adjusting Binary Search Trees », Journal of the ACM, vol. 32, n^o 3,‎ 1985, p. 652-686 (DOI 10.1145/3828.3835, lire en ligne)