DIGITAL SEARCH TREES WITH KEYS OF VARIABLE LENGTH

摘要

In this paper we consider Digital Search Trees (DST's) with keys of variable length, where a key might be a prefix of any other. Since the traditional insertion algorithm for DST's does not work in this case, a modification which can deal with prefixes is presented. Afterwards an average case analysis of the new algorithm is performed.%Dans cet article, nous considérons des arbres de recherche digitaux où les clés sont de longueur variable, une clé pouvant être un préfixe d'une autre. Comme l'algorithme d'insertion traditionnel ne s'applique plus dans ce cas, nous présentons une modification qui prend en compte les préfixes. Nous effectuons l'analyse en moyenne de ce nouvel algorithme.