Théorie de la programmation - TDA et structures de données 2004 Génie Informatique Université de Technologie de Belfort Montbéliard

Crenaud

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Théorie de la programmation - TDA et structures de données 2004. Retrouvez le corrigé Théorie de la programmation - TDA et structures de données 2004 sur Bankexam.fr.

Sujets

• 2004

Informations

• Publié par: bankexam
• Publié le: 27 janvier 2008
• Nombre de lectures: 33
• Langue: Français

Extrait

UTBM 21 juin 2004
lo42 - Final P2004 - page1/1
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 l’élément x, tous les éléments présents dans le
sous-arbre gauche sont inférieurs à x et tous ceux du sous-arbre droit sont supérieurs à x. Un arbre binaire de
recherche est un arbre rouge et noir s’il satisfait les deux propriétés suivantes :
(1) Si un nœud est rouge alors ses fils sont noirs.
(2) Chaque chemin simple issu d’un nœud à un descendant "vide" contient le même nombre de nœuds
noirs.
Voici un exemple d’arbre rouge et noir :







(Les nœuds rouges sont représentés grisés).


Question 1 (2) Ecrivez une fonction arbre_successeur qui retourne le nœud possédant la plus petite étiquette
supérieure à celle du nœud reçu en paramètre, ou nul. 7 est le successeur de 5, 13 est le successeur de 7.
On suppose que nous disposons de la fonction "arbre_min(r :Btree) : Btree".

fonction arbre_successeur (r : Btree) : Btree ;

Nous allons maintenant écrire quelques fonctions permettant de vérifier qu’un objet de type Btree vérifie bien les
propriétés d’un arbre rouge et noir.

Question 2 (2) Ecrivez une fonction controle qui vérifie qu’un objet de type Btree vérifie la propriété (1), i.e.
que tout fils d’un nœud rouge est noir.

fonction controle(r : Btree) : booléen ;


La hauteur noire hn(t) d’un arbre rouge et noir t est le nombre de nœuds noirs, présents dans un chemin
quelconque descendant de sa racine à n’importe quelle feuille
13
17 5
14 19 7 3
4 1 UTBM 21 juin 2004
lo42 - Final P2004 - page2/2
t2 t3

Question 3 (2) Ecrivez une fonction hauteur_noir qui calcule la hauteur noire d’un objet de type Btree . Dans
le cas où cette hauteur ne serait pas définie (parce que l’arbre de vérifie pas la propriété (2)), vous
retournerez -1.
Modifiez votre fonction pour générer une exception. On supposera que celle-ci peut être provoquée par
appel à erreur() ;

fonction hauteur_noir (r : Btree) : entier ;

Question 4 (1) Déduisez-en une fonction controle2 qui vérifie qu’un objet de type Btree vérifie bien la
propriété (2), i.e. que tout chemin simple reliant un nœud à un descendant vide contient le même nombre
de nœuds noirs.

fonction controle2(r : Btree) : booléen ;

2 Les arbres rouge et noir et les arbres 2-3-4

Voici un arbre 2-3-4,







Question 5 (2) Donnez une séquence simple minimale d’insertions et suppressions dans un arbre vide
permettant d’obtenir cet arbre. Puis établissez l’arbre rouge et noir correspondant.

Question 6 (2) On supprime 13. En vous rappelant les propriétés de l’arbre, donnez l’arbre 2-3-4 après
cette suppression. Donnez l’arbre rouge et noir correspondant.

3 Insertion d’un élément
Le principe de l’insertion d’un élément x dans un arbre rouge et noir est le suivant. On effectue tout d’abord une
insertion en procédant comme pour un arbre binaire de recherche simple. Un nœud est donc créé à la place
d’une feuille, à une position choisie de manière à respecter l’ordre entre éléments. On colorie ce nouveau nœud
en rouge, ce qui permet de préserver la propriété (2). Ainsi, après cette première étape, seule la propriété (1)
peut être violée : il se peut en effet que le père du nœud introduit soit lui aussi rouge ! L’idée est alors de
remonter la structure de l’arbre en réarrangeant astucieusement les nœuds et leurs couleurs de manière à
remonter ce conflit et à le faire disparaître tout en maintenant la propriété (2).

Question 7 (2) Ecrivez une première fonction simple_insert qui insère un élément dans un arbre en vous
limitant à la première étape décrite ci-dessus, c’est à dire sans vous préoccuper du respect de la propriété
(1).

fonction simple_insert (x: Ninfo ; r : Btree) : Btree ;

3.1 Conflits rouges
Un conflit rouge est un arbre binaire de recherche d’une des quatre formes suivantes :














t3
x3
t4 x2
t3 x1
t2 t1
t2
x1
x2 t1
x3
t4
t3 t2
x3
t4 x1
x2 t1
x1
x3 t1
x2 t4
10 | 15 | 20
7 13 18 25 UTBM 21 juin 2004
lo42 - Final P2004 - page3/3


(Où les sous-arbres t1, t2, t3 et t4 sont des arbres rouge et noir de même hauteur noire). Il est possible
de < résoudre > n’importe lequel de ces conflits en réécrivant l’arbre sous la forme suivante :







Question 8 (5) Ecrivez une fonction conflit qui prend pour argument un objet de type Btree. S’il s’agit
d’un conflit, votre fonction réarrangera l’arbre comme indiqué ci-dessus. Dans tous les autres cas, elle
rendra l’arbre inchangé.

fonction conflit (r : Btree) : Btree ;


3.2 Insertion avec résolution des conflits

Si la racine d’un arbre rouge et noir est rouge, l’arbre obtenu en colorant cette racine en noir est également un
arbre rouge et noir. On peut donc toujours se ramener au cas où l’arbre considéré, a une racine noire. On
supposera ainsi que les arbres manipulés ont une racine noire.

Question 9 (1) Ecrivez une fonction racine_noire qui colore en noir la racine d’un arbre.

fonction racine_noire (r : Btree) : Btree ;

Question 10 (2) Adaptez votre fonction simple insert de manière à résoudre les conflits lors de la remontée
à l’aide de la fonction conflit. Vous pourrez supposer que l’arbre initial a une racine noire et veillerez que
l’arbre obtenu ait également une racine noire.

fonction insert (x : Ninfo ; r : Btree) : Btree ;

Le coût de l’insertion d’un élément dans un arbre rouge et noir est le même que pour un arbre binaire de
recherche : elle est proportionnelle à la hauteur de l’arbre. En effet, les manipulations effectuées pour résoudre
les éventuels conflits, sont locales et limitées au chemin menant de la racine de l’arbre au nœud ajouté. Elle
n’affecte donc la complexité théorique de la fonction que d’un facteur constant.
x2
x3
x1
t3 t4 t2 t1