Questions / réponses

Bst search rec terminale

Bst search rec terminale

av Alexis Perignon -
Antall svar: 4

Bonjour ,
  j'ai essayé de faire BST_search en version récursive terminale , j'ai crée deux versions différentes et j'ai un doute sur chacune d'elle étant terminale , pourriez vous m'aider ?

La première je ne suis vraiment pas sur , vu que je renvoie multiplicity si la clé est trouvée , et que je renvoie 0 si la clé n'a pas été trouvée , j'ai un gros doute mais 0 et multiplicity sont stockées dans la pile non ? La seconde me semble mieux , mais parcours tout l'arbre même en ayant trouvé la valeur au début de l'arbre ..

   
let bst_search tree value =
  let rec aux l =
    match l with
    |[]-> 0
    |Empty::next -> aux next 
    |Bin((key,multiplicity),left,right)::next when key=value-> multiplicity
    |Bin(_,left,right)::next -> aux (left::right::next) 
  in aux [tree]


let bst_search tree value =
  let rec aux l to_return =
    match l with
    |[]-> to_return
    |Empty::next -> aux next to_return
    |Bin((key,multiplicity),left,right)::next-> aux (left::right::next) (if key=value then multiplicity else to_return)
                              in aux [tree] 0
Merci ,
A.P
Som svar til Alexis Perignon

Re: Bst search rec terminale

av Marc Zeitoun -

Les deux versions me semblent correctes, et sont effectivement récursives terminales (ce qui n'est pas simple à obtenir sur les arbres, parce que les algorithmes combinent souvent deux appels récursifs pour calculer la valeur de retour).

Il faut bien retourner 0 lorsque la liste est vide dans la version 1: l'arbre a été découpé en sous-arbres et complètement inspecté, et la clé n'a jamais été trouvée. La version 2 est en fait moins efficace que la version 1: 

- dans la version 1, lorsque la clé est trouvée, elle est renvoyée immédiatement.

- dans la version 2, même si la clé est trouvée dès le départ (à la racine de l'arbre), on va inspecter tout l'arbre, en maintenant dans to_return la multiplicité qu'on vient de découvrir et qu'on retournera à la fin (autrement dit, dans la version 2, soit to_return reste à 0 lors de tous les appels, soit il change une seule seule fois).

En tout cas c'est très bien...

Som svar til Alexis Perignon

Re: Bst search rec terminale

av Philippe Duchon -

Bonjour,

La recherche dans un ABR est l'une des rares opérations classiques qui, dans leur version la plus naturelle, se code en récursivité terminale: dès que l'arbre n'est pas vide, on a trois cas à traiter, et dans les deux cas où on est naturellement à appliquer la récursivité, d'une part on n'a qu'un appel à faire, d'autre part le résultat de l'appel récursif est directement le résultat cherché.

Votre première fonction est en fait une recherche (récursive terminale) dans un arbre binaire quelconque (qui peut ne pas être un ABR): si on suppose simplement que les contenus des noeuds sont des couples (cle,multiplicite) avec uniquement la condition que les cles sont toutes distinctes, vous retournez la multiplicite de la cle cherchee (et 0 si la clé n'est pas présente). Mais vous n'exploitez pas du tout la structure d'ABR.

La deuxième est aussi une recherche dans un arbre binaire quelconque (de nouveau, vous n'utilisez pas le fait que l'arbre soit censé être un ABR), mais si vous trouvez la valeur cherchée vous ne retournez pas directement la multiplicité, vous la conservez et donc, au final, si la même clé est présente plusieurs fois dans l'arbre avec des multiplicités distinctes vous allez retourner celle du dernier noeud (dans l'ordre préfixe) qui contient la clé cherchée. L'ordre est préfixe parce que vous parcourez l'arbre dans l'ordre préfixe: d'abord le noeud racine, puis les sous-arbres gauche et droit qui sont placés dans la liste d'arbres à traiter dans cet ordre.


Au final, sur des arbres binaires qui peuvent contenir plusieurs noeuds de même clé, vos deux fonctions ne calculent pas la même chose: la première retourne la multiplicité trouvée dans le premier noeud (en ordre préfixe) qui contient la clé cherchée; la seconde, celle trouvée dans le dernier noeud (toujours en ordre préfixe) qui contient la clé cherchée. Les deux sont correctes sur les ABR, mais peu efficaces bien que récursives terminales.

Bref, vous avez fait beaucoup d'efforts pour obtenir de la récursivité terminale (et vous l'appliquez correctement), mais comme application aux ABR, ce n'est pas très pertinent smiler

Som svar til Philippe Duchon

Re: Bst search rec terminale

av Marc Zeitoun -

Effectivement... j'avais lu le code comme celui d'un algorithme de recherche dans un arbre quelconque.

Pour reformuler la réponse de Philippe, la plupart des algorithmes sur les arbres nécessitent deux appels récursifs (par exemple la recherche dans un arbre binaire qui n'est pas forcément un ABR), mais la recherche dans un ABR en nécessite un seul (car on sait si on doit continuer la recherche dans le sous-arbre gauche ou dans celui de droite). Autrement dit, si on sait que l'arbre est un ABR, l'algorithme naïf est naturellement récursif terminal.


Som svar til Marc Zeitoun

Re: Bst search rec terminale

av Alexis Perignon -

Merci de vos réponses en tout cas ! Il est vrai que sur des ABR ce n'est pas très pertinent mais au moins cela m'a aidé sur la manière de le faire pour des arbres binaires aussi, je n'avais pas réalisé sur le moment que la version "naïve " était récursive terminale aussi !

Cordialement , A.P