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 :
Puis il y'a cet algorithme :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.
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.
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
Vous pouviez m'éclaircir s'i vous plait ?
Partager