Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Arbre radix
Résumé
En informatique, un arbre radix ou arbre PATRICIA (pour Practical Algorithm To Retrieve Information Coded In Alphanumeric en anglais et signifiant algorithme commode pour extraire de l'information codée en alphanumérique) 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 fils avec celui-ci. On peut alors étiqueter indifféremment chaque arête par un mot ou bien par une unique lettre.
Le premier à parler d’« arbre de PATRICIA » est Donald R. Morrison. À peu près au même moment, Gernot Gwehenberger invente indépendamment la même structure.
Les arbres Patricia peuvent être utilisés dans la construction de tableaux associatifs.
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 d'autres primitives selon les usages :
Recherche des mots avec un préfixe commun : Détermine la liste des mots commençant par un certain préfixe.
Recherche du mot précédent : Recherche du plus grand mot parmi ceux plus petits qu'un certain mot. Les comparaisons utilisent l'ordre lexicographique.
Recherche du mot suivant : Recherche du plus petit mot parmi ceux plus grands qu'un certain mot.
Rechercher un mot dans un arbre consiste à parcourir l'arbre de manière que les arê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 arê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 arê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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.