Arbre binaire récursif

**BBouille** · 21/03/2022, 11h32

Bonjour les amis,
Ayant réalisé un programme qui me permet de charger les mots d'un dictionnaire dans un arbre binaire par récursivité je me pose une question.
Lorsqu'on introduit un nouveau mot dans l'arbre on recherche les lettres qui sont déjà dans certaines branches et on ajoute la lettre en cours.
En utilisant la récursivité il faut reparcourir toutes les branches qui contiennent les premières lettres du mot sauf erreur de ma part.
Comme on sait que le début du mot n'existait pas plutôt que de reparcourir les branches ne pourrait-on pas ajouter la dernière lettre en cours après le dernier noeud de cette branche?
J'espère que c'est assez clair.

**WhiteCrow** · 21/03/2022, 14h15

Bonjour,
que ton implémentation de l'ajout soit ou non récursive importe peu. Ce que tu devrais nous dire en premier est quelle structure tu utilises. Il y en a des dizaines de structures arborescentes pour implémenter un «dictionnaire», comme un trie, un hash tree, radix tree, dag ou dagad (même si ce ne sont plus des arbres mais juste des graphes acycliques) … ton arbre est-il binaire uniquement parce que tu utilises une représentation fils gauche/frère droit ?
Parle-nous de ta structure (du ce que tu utilises) avant de poser une question sur comment faire et virer en problème XY.

**BBouille** · 21/03/2022, 16h55

Désolé WhiteCrow,
Je ne suis pas un spécialiste mais dans mon esprit un arbre binaire était composé d'un noeud et d'un fils gauche et frère droit donc.

**WhiteCrow** · 21/03/2022, 21h41

Quelles données les nœuds contiennent-ils ?
Quel est le détail des structures de donnée que tu utilises ?
Quel algorithme as-tu implémenté ?

**tbc92** · 22/03/2022, 08h01

après le dernier noeud de cette branche?

Quand tu dis cette branche, tu penses à quelle branche ?
Si tu fais l'effort de répondre très précisément à cette question, tu vas t'apercevoir que tu vas proposer un algorithme, et que c'est justement l'algorithme que tu étais en train de critiquer.

**BBouille** · 22/03/2022, 12h29

Voici mon code (ai déjà peur du verdict

)

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
Procedure REMPLISSAGE_LISTE(VAR p_liste:ptr_dico;mot:T_mot;VAR nb_cells:integer;posit:integer);
  var
    p_inser:ptr_dico;                 // pointe vers l'élément à insérer dans l'arbre
  begin
   if posit<=length(mot) Then               // S'il reste des caractères à ajouter, alors                               
   begin
    if (p_liste=NIL) OR (p_liste^.car>mot[posit]) Then // S'il faut ajouter au début
    begin
      CREATION_CELL(p_inser,mot[posit]);  // Création & initialisation du noeud.
      nb_cells:=nb_cells+1;               // On incrémente le nombre de cellules d'une unité.
      p_inser^.droit:=p_liste;            // Chaînage
      p_liste:=p_inser;
      REMPLISSAGE_LISTE(p_liste^.suiv,mot,nb_cells,posit+1);  // Ajout dans le sous arbre du bas
    end
    else                                 // Si on n'ajoute pas au début
    begin
      if p_liste^.car=mot[posit] Then      // Si le caractère est déjà présent à ce niveau, alors
      begin
        REMPLISSAGE_LISTE(p_liste^.suiv,mot,nb_cells,posit+1); // ajouter dans le sous arbre du bas
      end
      else                               // Sinon, le caractère n'est pas présent à ce niveau
       begin                       
        REMPLISSAGE_LISTE(p_liste^.droit,mot,nb_cells,posit);  // Ajout dans le sous arbre droit
       end;
    end;
  end;
  end;

Un peu d'indulgence, j'ai déjà dû digérer la récursivité, le chaînage et le principe des arbres et le reste

J'espère que c'est suffisant sans déclaration des variables, etc.
J'avais commencé un programme qui traitait notamment ce dictionnaire en Delphi et là ça marchait super bien, très rapide.
J'ai voulu le retranscrire en RealBasic et là je me suis rendu compte que le chargement du dictionnaire était super lent, peut-être à cause du logiciel et aussi parce que je dois passer par des variables intermédiaires (moins souple que Delphi).
Alors j'ai approfondi le raisonnement et me suis rendu compte qu'on passait peut-être inutilement par tous les noeuds avant d'insérer.
Donc ma question était de savoir s'il était possible d'insérer directement une nouvelle lettre à la suite de l'arbre sans reparcourir toutes le(s) branche(s)?

**tbc92** · 22/03/2022, 15h12

Il y a un truc qui n'est pas clair dans cette histoire.

Ayant réalisé un programme qui me permet de charger les mots d'un dictionnaire dans un arbre binaire par récursivité je me pose une question.
Lorsqu'on introduit un nouveau mot dans l'arbre on recherche les lettres qui sont déjà dans certaines branches et on ajoute la lettre en cours.

Imaginons les 3 problèmes suivants :
J'ai un arbre binaire, qui contient par exemple une centaine de mots. Il ne contient qu'un mot commençant par W , le mot Wagon, et il ne contient aucun mot commençant par X. Par contre il contient des mots commençants par Y ou Z, les mots YEN et ZOO.

Problème n°1, je dois ajouter le mot WATT
Problème n°2, je dois ajouter le mot XENOPHOBE
Problème n°3, je dois ajouter le mot WAGONNET

Dans un cas, WATT commence avec les lettres WA, comme WAGON, alors que dans l'autre, XENOPHOBE commence par X, et aucun autre mot ne commence par X. et dans le cas de WAGONNET, c'est encore autre chose, c'est le même mot que WAGON, avec 3 lettres en plus.

Dans tes explications, et dans le code que tu proposes, ça crée une différence. Tu parles de length(mot) dans ton code.

Pour moi, ces 3 cas sont strictement identiques. Dans les 3 cas, on doit ajouter un mot qui se trouvera à la fin 'entre' WAGON et YEN. Point final.

A aucun moment, tu n'as besoin de découper ton mot lettre à lettre. Ni de comparer telle lettre avec telle autre lettre. Tu as besoin de traiter des mots. Tu n'as pas du tout besoin de traiter des lettres.

Code :

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

1
2
3
4
5
Si mot_a_insérer < mot_lu alors  
   ... 
sinon 
   ... 
fin

Ou alors, c'est que je n'ai rien compris au besoin.

**BBouille** · 22/03/2022, 15h31

Oui mais si j'ai bien compris l'avantage d'un arbre binaire c'est que tu diminues le nombre d'entrées.
Par exemple WATT commence par WA et WAGON aussi donc tu auras:

W
|
A--
|  |
G  T
|  |
O  T
|
N--S
|     
N
|
E
|
T

Ou j'ai rien compris non plus.

**WhiteCrow** · 22/03/2022, 16h16

Donc ce que tu cherches à faire est un trie (enfin plus ou moins) sauf qu'au lieu d'avoir une représentation par un arbre n-aire tu en as une avec un arbre binaire.

La réponse à ta question est … oui (enfin je suppose). Si lors de l'insertion d'un mot tu remarques qu'une lettre n'existe pas dans la liste des frères (que tu auras intérêt conserver triée) alors tu peux directement insérer la lettre manquante et créer le sous arbre gauche avec la liste de toutes les lettres qui suivent dans le mot.

Ta structure pourra sans doute être compactée →https://en.wikipedia.org/wiki/Determ...tate_automaton .

**tbc92** · 22/03/2022, 17h16

Dans un arbre, (un vrai arbre,dans la forêt), il y a un tronc, puis ce tronc se sépare en plusieurs branches. Puis chaque branche se sépare en plusieurs branchettes etc etc.
Dans un arbre binaire, à chaque séparation, on a une branche qui se sépare en 2. Binaire, ça veut dire 2.

Ton organisation, elle ressemble à quelque chose, pas de problème. On peut dire que ça ressemble à un arbre, ok. Mais explique moi en quoi ton arbre serait binaire ! Pour la première lettre d'un mot, tu as 26 possibilités, et pas seulement 2.

Tu as peut-être des bonnes raisons de faire comme ça (lettre par lettre), et ça peut fonctionner, pourquoi pas. Mais en terme de performance, ça ne me paraît pas performant du tout, bien au contraire, et en terme de vocabulaire, je ne vois vraiment pas ce qui te permet d'appeler cela un arbre binaire.

Je reste vraiment sur l'idée de traiter mot par mot et pas lettre par lettre. En terme de stockage mémoire, tu économises des choses, parce que WA est stocké une seule fois pour WAGON et pour WATT, mais tu dois stocker plein de liens inutiles W suivi de A suivi de T suivi de T : tout ça pour WATT. Le peu que tu gagnes parce que les débuts de mots sont mis en commun, tu perds 10 fois plus ou 100 fois plus, parce que tu dois stocker plein de liens en plus.

**WhiteCrow** · 22/03/2022, 21h18

Si si … c'est intéressant. On part d'un trie qui serait un arbre 27-aire (une lien possible par lettre si on se restreint à A-Z plus un marqueur de fin de mot). Cette arbre 27-aire peut ensuite être représenté par un arbre binaire (un classique fils gauche, frère droit).
On peut pousser le bouchon plus loin en transformant cet arbre binaire en graphe acyclique où l'on partage également les fin de mots (un dawg, directed acyclic word graph).
Cela permet d'avoir une représentation très compacte d'un lexique.
On peut même adapter cette sdd pour qu'elle soit plus flexible en permettant de parcourir les mots dans deux sens (utile pour un jeu comme le scrabble où on cherche à accrocher un mot à partir d'une ancre en l'allongeant dans deux directions opposées).

Il y a pas mal de littérature sur le sujet.

**BBouille** · 23/03/2022, 09h33

Justement WhiteCrow mon intention finale était de réaliser un DAWG mais pour ça je voulais être sûr de l'arbre initial.
En effet au départ j'avais fait un arbre n-aire mais je voulais essayer de le comparer à un binaire pour voir lequel était le plus performant.
tbc92 merci de me préciser que bi ça veut dire 2.
Je dis que c'est un arbre binaire parce chacun de mes noeuds n'a que 2 fils.
Si tu regardes mon code je vais soit à gauche soit à droite ou j'ajoute un noeud.
J'avais trouvé ça qui dit bien que c'est un arbre binaire :https://www.enseignement.polytechniq...1/TD/td_6.html
ou ceci : https://munier.perso.univ-pau.fr/temp/IC2/dico.pdf
Je ne vois vraiment pas comment traiter les mots en entier ou alors je garde mon fichier texte ou je mets tous les mots dans un stream et je cherche les mots dans cette variable.
Les principaux programmes du célèbre jeu de mots utilisent un DAWG et qui est bien un enchevêtrement de lettres et de chemins.

**tbc92** · 23/03/2022, 10h43

Je n'avais pas vu que l'idée était de bâtir un dictionnaire type 'Scrabble'.

Et effectivement, ça change tout.

**WhiteCrow** · 23/03/2022, 13h09

ça va aussi beaucoup dépendre de quel jeu tu veux implémenter …
Si c'est un «mot le plus long» pas la peine d'un dawg il sera plus efficace d'avoir une hashmap avec comme clé la liste des lettres du mot ordonnées alphabétiquement (bon on peut toujours utiliser un dawg). Utiliser une db comme sqlite3 sera également performant.
Si c'est un «wordle/motus» ou un «mots mêlés» un dawg simple devrait faire l'affaire.
Si c'est un «scrabble/wordox» (où il y a un plateau et où on accroche des mots à d'autres) un gaddag est le plus performant.

**BBouille** · 23/03/2022, 15h13

Houlàà WhiteCrow tu m'as appris plusieurs mots là.
J'ai essayé avec une base de données mais comme j'utilise SQLite quand il faut rechercher tous les mots formables à partir d'un tirage c'est trop lent.
Avec l'arbre binaire la recherche est très rapide mais mon problème c'est le chargement, le "remplissage" de l'arbre là c'est très long (plusieurs secondes) c'est pourquoi je reviens à ma question initiale comment par récursivité éviter de reparcourir la branche où on ajoute lettre après lettre le mot qui est nouveau donc on sait que ça doit se passer dans la branche en cours.
Je vais essayer sans récursivité mais pour une fois que j'avais pu l'utiliser en comprenant comment ça fonctionne plus ou moins ben là je suis coincé.
Je n'ai pas encore essayé comme ça me paraissait moins élégant mais charger tous les mots dans un binarystream et rechercher les mots formables un après l'autre devrait être instantané et là au moins je suis sûr que le chargement du fichier vers le binarystream est quasi immédiat.

**WhiteCrow** · 23/03/2022, 22h09

Sqlite3 trop lent dans le cadre ?
J'avais, il y a quelques temps, fait un test à partir de l'ODS et les temps de réponses étaient tout à fait corrects.
Pour faire simple, j'ai créé une db avec une table à deux champs. Le premier champ est le mot, le second la chaîne obtenue en triant les lettres du mot.
Pour un tirage donné, je le trie puis je génère tous les sous multi-ensembles que je checke dans la db … ce qui me permet d'avoir la liste de tous les mots du lexique formables à partir du tirage.

Ensuite, si tu optes pour une représentation en dawg, ou des mots ou des clés (=le mot avec les lettres triées), il ne faut pas le reconstruire à chaque fois. Le plus simple est de le faire une seule fois puis de le sérialiser. Ce n'est pas parce que tu as une «structure d'arbre» que tu es obligé d'avoir des pointeurs mémoire entre les nœuds, un simple indice dans un tableau fait très bien l'affaire.

Ensuite je ne comprends pas ta question, car si pendant la recherche tu es sur le chemin SOL (par exemple) et qu'aucune autre lettre ne te permet de continuer alors par backtracking tu zappes directement tout le reste …

Mais à nouveau, une solution efficiente dépendra surtout du type de recherche que tu as besoin de faire (ou tous les mots formables avec un tirage (le mot le plus long), ou idem mais en plus posables sur un plateau (scrabble), ou les mots formables en parcourant différentes possibilités pour les lettres (boggle) … )

**BBouille** · 24/03/2022, 08h36

Pour le SQL je forme une requête en faisant une boucle sur les lettres du tirage du genre :

Code :

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

Groupe = Groupe + "' AND Mot LIKE '%"+Mot_Array(i)+"%"

Ceci pour trouver les anagrammes.
J'avais essayé d'utiliser ta méthode mais je ne m'y retrouvais pas dans toutes les combinaisons possibles.
Selon le tirage et les mots déjà placés sur la grille ça fait donc pas mal d'appels à la BD.
J'ai fait une comparaison entre les méthodes que j'ai pour le moment.
Le fichier texte à charger comprend 402325 mots (4724 Ko).
Pour un arbre n-aire le temps du remplissage de l'arbre est de 6,7 secondes (toujours en RealBasic).
Pour un arbre binaire là je passe à 144 secondes.
Et enfin en chargeant le fichier texte dans un binarystream là ça prend 0,015 seconde, j'y ai fait une recherche aléatoire de 25000 mots et ça prend 0,67 secondes.
Je reste persuadé que le temps perdu pour l'arbre binaire est de devoir reparcourir la branche où on doit ajouter une lettre mais avec la récursivité je ne vois pas comment y échapper.
Pour pouvoir continuer le reste je vais travailler avec un binarystream puis je reviendrai à ces arbres.

**WhiteCrow** · 24/03/2022, 09h18

Là je te dirais que la gestion de la mémoire n'est pas des plus optimales avec realbasic, car je suppose que tu alloues de la mémoire à tour de main.
Si tu utilises un binarystream, je suppose que tu utilises quelque chose proposé par le langage qui est mieux optimisé en interne.

J'avais développé mes petits jeux en C, puis en Rust. Il n'y a jamais eu de goulet d'étranglement de ce type.

De ce que je comprends, tu veux une structure de type lexique pour jouer à jeu similaire au scrabble ?
Je ne comprends toujours pas la structure que tu utilises ? est-ce un trie ou pas ?
Mais surtout, il ne faut pas reconstruire l'arbre à chaque fois, il faut le sérialiser.

**BBouille** · 24/03/2022, 13h54

Oui le but final est bien un jeu de Scrabble avec plusieurs options, conjugaisons, anagrammes, définitions, entraînement, 7 ou 8 lettres, parties joker etc.
J'étais pas mal avancé en Delphi où je n'ai pas ce problème de performance mais le programme devenait tellement important et comme je suis bordélique je perdais plus de temps à retrouver mes procédures qu'à programmer.
J'utilise Delphi 7, ça a sûrement changé maintenant mais mon problème est qu'il y a autant de fichiers que d'unités ça me semble donc moins pratique mais je me trompe sûrement.
Alors j'ai tout retranscrit en RealBasic qui permet de mieux ranger les procédures et d'y accéder directement.
On passe plus facilement d'une fenêtre à l'autre aussi.
Il n'y a qu'un seul fichier qui est le programme lui-même.
Tu as raison Delphi gère beaucoup mieux la mémoire.
N'étant pas informaticien je dirais que le binarystream permet de charger en une fois un fichier texte par exemple dans une variable String plutôt que de lire séquentiellement dans un fichier texte.
L'accès aux mots dans ce cas-là est instantané. Je ne sais pas qu'elle est la limite de la taille de la variable mais 10 Mega passent sans problème.
Les autres logiciels de programmation ont sûrement leur équivalent.
Pour ma structure telle que décrite dans le code plus haut est celle d'un arbre binaire.
Pour la sérialisation, tu veux dire sauvegarder l'arbre plutôt que de le créer à chaque lancement du programme?
Je voulais m'y pencher après avoir maîtrisé ce fichu arbre mais je ne suis pas sorti du bois.

**WhiteCrow** · 24/03/2022, 14h17

ok … une structure d'arbre binaire n'est que le squelette rien d'autre. Un BST (binary search tree), un arbre de Huffmann ou un Heaptree on tous la même structure d'arbre mais ne représentent pas la même chose ni n'ont les même fonctions pour y accéder/les modifier/etc. Un arbre binaire n'est qu'un graphe acyclique connexe de degré maximum 3 …

Tu as un nœud qui contient une lettre et deux pointeurs, un pour le fils gauche et un pour le fils droit. Si dans ton arbre tu es sur un nœud après avoir traversé des nœuds contenant 'S' puis 'A' tu commences à construire un mot commençant par "SA". Si tu cherches la lettres 'L' (pour le préfixe "SAL") tu cherches à partir du fils droit de 'A'. Si celui-ci contient 'C' alors tu passes au fils droit de 'C' et ainsi de suite jusqu'à trouver un nœud contenant 'L'. Si tu ne le trouve pas alors par backtracking tu retombes sur le nœud 'A' avec le préfixe "S" et tu passes au fils droit suivant … Si tu le trouve tu continues …

La récursivité par défaut te permet de t'abstenir de maintenir par toi-même une pile d'appel …
Après les soucis sont sans doute dûs à la gestion de la mémoire dynamique faite par ton langage.

Attention toutefois de ne pas vouloir une seule structure pour tout faire …
Une recherche d'anagramme est plus simple avec un hashmap, une recherche avec joker sera sans doute plus efficiente avec un dawg et si tu as besoin de placer un mot sur plateau avec contrainte alors un daggad serait le plus adapté.

Arbre binaire récursif

Algorithmes et structures de données

Discussions similaires

Partager

Partager