Utilisatrice:P141592653/Arbre radix
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En informatique, un arbre radix ou arbre PATRICIA (pour Practical Algorithm To Retrieve Information Coded In Alphanumeric en anglais) est une structure de données compacte permettant de représenter un ensemble de mots adaptée pour la recherche. Il est obtenu à partir d'un arbre préfixe en fusionnant chaque nœud n'ayant qu'un seul enfant avec celui-ci. On peut alors étiqueter indifféremment chaque arrête par un mot ou bien par une unique lettre.
Applications[modifier | modifier le code]
Les arbres Patricia peuvent être utilisés dans la construction de tableaux associatifs.
Pimitives[modifier | modifier le code]
- Insertion : Ajout d'un mot à l'arbre.
- Suppression : Suppression d'un mot de l'arbre..
- Recherche : Détermine si un mot est ou non dans l'arbre. On peut également ajouter une fonction qui renvoie la liste des mots commençant par un certain préfixe.
Recherche[modifier | modifier le code]
Version 1:
La recherche d'un mot consiste en un simple parcours récursif de l'arbre : on part de la racine et on regarde si l'une des arrêtes est un préfixe du mot. Si on n'en trouve pas, le mot ne se trouve pas dans l'arbre. Sinon, on réitère le processus sur le nœud correspondant, jusqu'à ce qu'on tombe sur une feuille. Si le mot est vide, alors le mot est bien dans l'arbre. Dans le cas contraire, il ne s'y trouve pas.
Version 2:
Rechercher un mot dans un arbre consiste à parcourir l'arbre de manière à ce que les arrêtes parcourues mises bout à bout forment le mot recherché.
Plus précisément, on part de la racine et on regarde si l'une des arrêtes est un préfixe du mot. Si on n'en trouve pas, le mot ne se trouve pas dans l'arbre. Sinon, on réitère le processus sur le nœud correspondant, jusqu'à ce que l'on tombe sur une feuille. Lorsqu'on arrive à une feuille, deux cas se présentent : soit le mot correspond aux arrêtes parcourues mises bout à bout, soit le mot est en fait plus long et ne fait que commencer par le mot lu sur l'arbre. Dans ce cas, le mot n'est pas contenu dans l'arbre.
(version bis) Si le mot est vide, c'est-à-dire si l'on a parcouru le mot en entier alors le mot est bien dans l'arbre. Dans le cas contraire, on n'a pas fini de lire le mot et le mot n'est par conséquent pas dans l'arbre.
Cet algorithme est illustré par le pseudo-code suivant :
Fonction rechercher(arbre,mot) :
Si est_feuille(arbre) et est_vide(mot) alors
Renvoyer Vrai
Sinon si est_vide(mot) ou est_feuille(arbre) alors
Renvoyer Faux
Sinon
Pour arête dans arêtes(arbre) faire
Si est_un_préfixe(arête,mot) alors
Renvoyer rechercher(sous_arbre(arbre,arête) , suffixe(mot,taille(arête)) )
Renvoyer Faux
Suppression[modifier | modifier le code]
Cette opération se fait à l'identique de la recherche d'un mot. Lorsqu'on a trouvé le mot à supprimer, il suffit ensuite de supprimer la feuille correspondante à l'identique d'une suppression sur un arbre.
Insertion[modifier | modifier le code]
L'insertion d'un mot commence par le parcours de l'arbre de manière identique à la recherche d'un mot jusqu'à ce qu'aucune des arrêtes ne coïncident avec la fin du mot à insérer. Si l'on arrive à une feuille, c'est que le mot est déjà dans l'arbre. Sinon on cherche une arête ayant un préfixe commun avec la suite du mot.
- Si aucune des arêtes n'a de préfixe commun, on ajoute un fils au nœud sur lequel on se trouve. L'arête les reliant est la fin du mot à insérer.
- Sinon, on choisit l'un des préfixes en commun, on supprime l'arête correspondante. On crée ensuite une arête ayant pour étiquette ce préfixe et on lui ajoute deux fils avec pour étiquettes l'une le suffixe de l'arête que l'on a supprimé, l'autre la fin du mot à insérer privée du préfixe commun.
Histoire[modifier | modifier le code]
Le premier à parler d'"arbre de PATRICIA" est Donald R. Morrison [1]. À peu près au même moment, Gernot Gwehenberger invente indépendamment la même structure[2]. Les arbres PATRICIA sont des arbres radix dont la base est égale à 2 c'est à dire que chqaque noeud a au plus deux fils, ce qui correspond à un ensemble de mots dans un alphabet binaire (l'alphabet composé de deux lettres : 0 et 1).
- Morrison, Donald R. Practical Algorithm to Retrieve Information Coded in Alphanumeric
- G. Gwehenberger, Anwendung einer binären Verweiskettenmethode beim Aufbau von Listen. Elektronische Rechenanlagen 10 (1968), pp. 223–226