UTBM theorie de la programmation tda et structures de donnees 2004 gi

UTBM 21 juin 2004 Final – LO42 Les documents de cours, TD et TP sont autorisés. Le barème est indicatif. Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal interprétée). L’élégance de la solution sera jugée. Sauf indication contraire, dans le cas d’algorithmes les réponses doivent être rédigées en pseudo code. Une question subsidiaire ne peut être traitée qu’une fois les autres questions traitées « correctement ». 1 Les arbres rouge et noir Un arbre rouge et noir est un arbre binaire de recherche dont chaque nœud contient une information supplémentaire, sa couleur, qui peut valoir soit rouge soit noir. En contrôlant la manière dont les nœuds sont colorés sur n’importe quel chemin allant de la racine à une feuille, les arbres rouge et noir garantissent qu’aucun de ces chemins n’est plus de deux fois plus long que n’importe quel autre, ce qui rend l’arbre approximativement équilibré. Nous représenterons les arbres rouge et noir grâce aux types suivants : Type couleur = (Rouge, Noir) ; Btree = ^Bnoeud ; Bnoeud = Structure Début val : Ninfo ; col : couleur ; pere, fg, fd : Btree ; Fin ; Un objet de type Btree représente un arbre binaire dont les nœuds sont colorés en rouge ou en noir et portent des étiquettes de type Ninfo. On supposera que l’on dispose d’une relation d’ordre sur ces éléments. Un tel arbre est dit de recherche si et seulement si pour tout nœud étiqueté par ...