Discussion :

[mimicha2000]

Bonsoir,
En essayant de réaliser un TP d'arbres de Patricia( ou tries ou arbres pour faire l'ordre lexicographique),j'ai trouvé quelques soucis.
Tout d'abord,je trouve qu'il y'a toujours un sommet vide mais je ne comprends pas comment symboliser en informatique cette case (structure contenant un tableau d'une case et pointeur ou quoi au juste).
Sinon en voulant insérer un mot dans l'arbre,j'ai trouvé un algorithme sur internet,mais je ne comprends pas quelques points :

Nous ne présentons que l'algorithme qui réalise l'insertion d'un mot dans l'arbre lexicographique binaire, l'algorithme de recherche en est une simple adaptation. Pour plus de lisibilité, nous avons externalisé la création d'un nœud de l'arbre dans l'algorithme Créer-Nœud. L'algorithme Insérer-Lexico est récursif et traite chaque symbole ui du mot u = u1, u2,… un ∈ Σ* l'un après l'autre à chaque appel récursif. La base récurrente est atteinte quand le mot à traiter est le mot vide ε. Dans le cas contraire, le traitement du mot u ne dépend que de son premier symbole u1 et de sa longueur |u| :

Le nœud A est vide. Dans ce cas, on crée un nœud racine dans lequel on range le premier symbole de u. Son attribut booléen est initialisé à VRAI si |u| = 1 ce qui signifie qu'on insère en fait le dernier symbole du mot, et à FAUX dans le cas contraire. On insère alors son suffixe u' dans le sous-arbre “cadet”.
Le nœud A n'est pas vide. On peut donc comparer (avec l'ordre alphabétique) le premier symbole de u avec le symbole s contenu dans l'arbre. On distingue alors trois sous-cas :
u1  >   s, il faut insérer u à droite dans le sous-arbre “frère”.
u1  =   s, il faut insérer u plus bas dans le sous-arbre “cadet” et modifier l'attribut booléen du nœud s'il s'agit du dernier symbole à insérer.
u1  <   s, dans ce cas il faut insérer un nouveau nœud avant dans lequel on range le premier symbole de u et on insère son suffixe dans le sous-arbre “cadet”.
Pour alléger les écritures, la notation u' désignera le suffixe u2, u3,… un de u.

Puis il y'a cet algorithme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
ALGORITHME CREER-NOEUD(s,b,C,F): arbre binaire;
INSTANCE
   s: symbole de Σ;
   b: booléen;
   C, F: arbres binaires;
VARIABLES
   aux: arbre binaire;
DEBUT
   aux ← NOUVEAU();
   aux→symbole ← s;
   aux→estmot ← b;
   aux→cadet ← C;
   aux→frere ← F;
   RETOURNER aux;
FIN
 ALGORITHME INSERER-LEXICO(u,@A)
INSTANCE
   u: mot de Σ*;
   A: arbre binaire;
VARIABLES
   aux: arbre binaire;
DEBUT
   SI (u ≠ ε) ALORS
      SI (A = ∅) ALORS
         A ← CREER-NOEUD(u[1],|u|=1,∅,∅);
         INSERER-LEXICO(u', A→cadet);
      SINON
         SI (u[1] > A.symbole) ALORS
            INSERER-LEXICO(u, A→frere);
         SINON 
            SI (u[1] = A.symbole) ALORS	       
               A.estmot ← A.estmot  OU (|u| = 1);
               INSERER-LEXICO(u', A→cadet);
            SINON 
               aux ← CREER-NOEUD(u[1],|u|=1,∅,A);
               aux→frere ← A;
               A ← aux;
               INSERER-LEXICO(u',A→cadet);
            FSI
         FSI      
      FSI   
   FSI   
FIN

J'ai tout compris sauf le |u|=1 ; est ce que çà veut dire la fin du mot? (je ne pense pas car sinon la ligne verte introduire qu'une lettre et s'arrêtera).Aussi, je n'ai pas compris la ligne en rouge.
Vous pouviez m'éclaircir s'i vous plait ?

[Invité]

Bonjour,

|u|, c'est la longueur d'un mot. Et |u| = 1, apparemment, vu la syntaxe, c'est un test d'égalité, entre |u| et 1.