Arbre palindromique
# Arbre palindromique

Un arbre palindrome ou arbre palindromique, aussi appelé arbre eertree, est un graphe utilisé pour des algorithmes de combinatoire des mots.

## Description

L'arbre palindrome pour un mot $S$ de longueur $n$ est une structure de donnée sous forme d'un graphe proche d'un arbre et qui représentent tous les palindromes distincts qui sont facteurs de $S$ avec une place additionnelle en $O(n)$. Lorsque $S$ est de longueur $n$ sur un alphabet de taille $\sigma$ et est donnée on-line, l'arbre peut être construit en temps $O(n\log \sigma )$ et place $O(n)$.

Les sommets du graphe représentent des palindromes, les arcs décrivent le passage d'un palindrome au suivant ou à un précédent.

Il y a deux types d'arcs, des arcs directs — qui sont les arcs d'un arbre — et des liens suffixes qui permettent de revenir en arrière.

Les arcs directs sont étiquetés par des symboles de l'alphabet. Il y a un arc direct du sommet $u$ vers le sommet $v$ étiqueté par la lettre $a$ si $v=aua$ :

    $u\xrightarrow {a} v\iff v=aua$.

Ainsi, on a dans l'exemple, les arcs

    ${\mathsf {t}}\xrightarrow {\mathsf {r}} {\mathsf {rtr}}\xrightarrow {\mathsf {e}} {\mathsf {ertre}}\xrightarrow {\mathsf {e}} {\mathsf {eertree}}$.

Les liens suffixes sont des arcs qui vont d'un sommet $u$ au sommet $v$, où $v$ est le plus long suffixe palindrome propre de $u$. Dans l'exemple, les liens suffixes sont tracés en rouge. On a par exemple :

    ${\mathsf {eertree}}\ {\color {Red}\to }\ {\mathsf {ee}}\ {\color {Red}\to }\ {\mathsf {e}}\ {\color {Red}\to }\ 0$.

Deux sommets spéciaux sont ajoutés à la structure :

* le sommet $-1$ qui est la racine de l'arbre ; les arcs sortant de ce sommet et étiqueté $a$ ont pour extrémité le sommet $a$ ; on a donc, pour tout symbole figurant dans $S$, l'arc

       $-1\xrightarrow {a} a$.
* Le sommet $0$ qui représente le mot vide (qui est un palindrome) ; on a alors

       $0\xrightarrow {a} aa$
    si $aa$ est facteur de $S$. Le sommet $0$ est le lien suffixe du sommet $-1$ et de lui-même.

La notation curieuse pour ces sommets particuliers est une conséquence de la numérotation des sommets de l'arbre, qui va de 1 jusqu'à un entier qui est aussi le nombre de palindromes figurant dans le mot $S$.

## Complexité

On peut montrer que la construction de l'arbre palindromique peur se faire en temps $O(n\log \sigma )$ et place $O(n)$. Des variantes ont été données notamment par Mieno, Watanabe et al..

