Bonjour,
j'aimerais savoir les algorithmes qui sont éligibles au ds de vendredi.
Cordialement,
DUBAN Mathieu
Le programme est celui que j'ai indiqué en cours: ce qui a été fait en CM, CI+TD, et TD machine jusqu'à cette semaine. Côté algorithmique, cela inclut en particulier :
- les algorithmes simples récursifs (calcul d'une quantité, comme le nombre de nœuds ayant une certaine propriété),
- les parcours d'arbres (en profondeur et en largeur),
- les algorithmes concernant les arbres binaires de recherche, les AVL et les arbres rouges et noirs : il faut avoir compris comment se font les recherches, les insertions et les suppressions, sauf la suppression dans les arbres rouges et noirs qui n'est pas au programme du DS.
- les algorithmes réalisant les correspondances vues entre arbres binaires, arbres planaires et mots de Dyck.
Vous devez aussi pouvoir concevoir un algorithme répondant à un problème simple décrit dans l'énoncé, même si on ne l'a pas vu en cours. Enfin, on peut vous demander une preuve simple (par exemple une démonstration par récurrence).
Bonjour,
j'ai essayé d'écrire la fonction d'insertion dans un AVL, mais je n'y arrive pas, (je dirais à cause du rééquilibrage, je ne sais pas comment en langage ocml détecter dans quel cas on se trouve 1a,1b,..)
J'aimerais savoir si le fait de comprendre la fonction (utilité + étapes +différents rééquilibrages ) est suffisante pour le DSI, ou s'il faut connaitre l'algorithme en language ocml ?
Idem pour la suppression dans un arbre AVL et pour l'insertion dans un arbre rouge/noir
Merci
IA
Bonsoir,
Il est un peu tard pour répondre de manière précise à votre question - le sujet est fait, soit il nécessite de savoir ré-écrire la fonction, soit il ne le nécessite pas... (la probabilité est de 1 ou de 0, mais je n'ai pas le droit de vous dire laquelle des deux est la bonne)
Quant à savoir dans quel cas on se trouve (je suppose que vous parlez du rééquilibrage d'un arbre AVL après l'insertion), tout peut se faire avec un match (qui peut être un peu complexe) et éventuellement des tests (ou un when dans le match); en sachant que, d'après ce que vous avez vu en TD, la particularité des arbres AVL est qu'une fois qu'on a fait un rééquilibrage dans le noeud critique, il n'y a pas besoin de continuer à remonter pour rééquilibrer.
Concrètement, pour écrire la fonction d'insertion-rééquilibrage, il peut être utile d'inclure dans la valeur de retour (d'une fonction auxiliaire, donc), un booléen qui dit si on a déjà fait un rééquilibrage ou pas.