DS 1 (MP option 2015-2016) — Partition et union d'ABR, arbres bicolores

Devoir surveillé · MP (option informatique) · 2015-2016

Cours : Arbres binaires de recherche · Arbres rouges et noirs

Sujet 1, niveau CCP/Centrale.

On rappelle qu'un arbre binaire étiqueté par des entiers est :

• soit vide, on le note alors \(Nil\) ;
• soit un nœud donné par un triplet \((x,g,d)\) où \(x \in \Z\), et \(g,d\) sont des arbres, on le note alors \(Noeud(x,g,d)\).

Soit \(A\) un tel arbre, on notera \(\mathrm{Etiq}(A)\) l'ensemble des étiquettes de l'arbre \(A\) défini récursivement par :

\[ \mathrm{Etiq}(Nil) = \emptyset \qquad \mathrm{Etiq}(Noeud(i,g,d)) = \{i\} \cup \mathrm{Etiq}(g) \cup \mathrm{Etiq}(d) \]

Un arbre binaire de recherche \(A\) (en abrégé ABR), étiqueté par des entiers distincts, est un arbre qui vérifie la propriété suivante : pour tout nœud \(Noeud(i,g,d)\) de \(A\), on a

\[ \max_{j \in \mathrm{Etiq}(g)} j \quad < i < \min_{k \in \mathrm{Etiq}(d)} k \]

I. Partition et union d'arbres binaires de recherche

On considère le type suivant :

type arbre = Nil | Noeud of int * arbre * arbre

On appelle coupure d'un ABR \(A\) selon une valeur \(c\) une partition de \(A\) en un couple de sous-arbres \((G_A,D_A)\) tels que :

• \(G_A\) et \(D_A\) sont deux ABR ;
• \(\mathrm{Etiq}(A) = \mathrm{Etiq}(G_A) \cup \mathrm{Etiq}(D_A)\) ;
• \(\displaystyle \max_{j \in \mathrm{Etiq}(G_A)} j \quad \le c < \min_{k \in \mathrm{Etiq}(D_A)} k\).

On remarque que \((Nil,Nil)\) est une coupure de \(Nil\) selon \(c\) (pour tout \(c\)).

Question 1

Soit \(Noeud(c,g,d)\) un ABR, montrer que \((Noeud(c,g,Nil),d)\) est une coupure de \(Noeud(c,g,d)\) selon \(c\).

Question 2

Soient \(i\) un entier, \(Noeud(i,A,B)\) un ABR et \(c\) un entier. Montrer que si \(c < i\) et si \((G_A,D_A)\) est une coupure de \(A\) selon \(c\), alors \((G_A, Noeud(i,D_A,B))\) est une coupure de \(Noeud(i,A,B)\) selon \(c\).

Question 3

Par symétrie, construire une coupure de l'ABR \(Noeud(i,A,B)\) selon \(c\), dans le cas où \(c > i\).

Question 4

Écrire une fonction récursive couper : int -> arbre -> arbre * arbre telle que couper c a renvoie une coupure de \(a\) selon \(c\).

Question 5

Si \(|a|\) désigne la hauteur de l'arbre \(a\), montrer que la complexité de la fonction couper c a, en nombre d'appels récursifs, est inférieure ou égale à \(|a|\).

Question 6

En utilisant la fonction couper, écrire une fonction non récursive inserer_racine : int -> arbre -> arbre telle que si \(b =\) inserer_racine i a alors \(\mathrm{Etiq}(b) = \mathrm{Etiq}(a) \cup \{i\}\) et \(b\) est un ABR dont la racine est étiquetée par \(i\). On supposera que les arguments \(i\) et \(a\) de la fonction sont tels que \(i \not\in \mathrm{Etiq}(a)\).

Question 7

Écrire une fonction récursive min_arbre : arbre -> int qui renvoie l'étiquette minimale d'un ABR différent de \(Nil\).

Question 8

En utilisant les fonctions min_arbre et couper, écrire une fonction non récursive union : arbre -> arbre -> arbre telle que si \(a\) et \(b\) sont deux ABR tels que les étiquettes de \(a\) sont toutes inférieures aux étiquettes de \(b\), alors si \(c =\) union a b, \(c\) est un ABR et \(\mathrm{Etiq}(c) = \mathrm{Etiq}(a) \cup \mathrm{Etiq}(b)\).

Question 9

Donner un majorant de la complexité de union a b dans le pire cas en fonction de \(|a|\) et \(|b|\), en comptant uniquement les appels récursifs de fonction.

II. Arbres bicolores

Représentation par pointeurs

On va maintenant considérer un autre type pour les arbres qui permettra de réaliser facilement des échanges de fils pour un nœud.

On considère le type mutuellement récursif suivant :

type noeud = {
  mutable etiquette : int;
  mutable gauche : arbre;
  mutable droit : arbre
}
and arbre = Nil | Noeud of noeud

On considère définies les fonctions suivantes :

let est_vide a = a = Nil
let noeud a = match a with
  | Noeud x -> x
  | Nil -> failwith "Arbre vide"

On peut alors effectuer un échange de fils pour un nœud ainsi :

let echange_fils a =
  match a with
  | Nil -> a
  | Noeud x ->
    let t = x.gauche in
    x.gauche <- x.droit;
    x.droit <- t;
    a

On remarque que cette fonction n'effectue l'échange que si c'est possible.

Rotations

Afin de pouvoir modifier la hauteur d'un arbre, on introduit, lorsqu'elles sont possibles, les opérations suivantes.

Rotation gauche

L'arbre obtenu en appliquant une rotation gauche à l'arbre \(Noeud(i_1,A_{g_1},Noeud(i_2,A_{g_2},A_{d_2}))\) est l'arbre \(Noeud(i_2,Noeud(i_1,A_{g_1},A_{g_2}),A_{d_2})\).

Soit graphiquement :

Rotation gauche.

Question 10

Écrire la fonction rotation_gauche : arbre -> arbre qui effectue une rotation gauche sur un arbre et le renvoie. Si la rotation gauche n'est pas possible, on renvoie l'arbre non modifié.

Question 11

Montrer que si \(A\) est un ABR, alors \(rotation\_gauche(A)\) est aussi un ABR.

Rotation droite

La rotation droite appliquée à un arbre binaire est l'opération inverse de la rotation gauche.

Question 12

Écrire la fonction rotation_droite, selon les mêmes principes que la fonction rotation_gauche. On fera un dessin au préalable.

Doubles rotations

Soit \(A = Noeud(i,A_g,A_d)\) un arbre binaire. La rotation gauche-droite de \(A\) est l'arbre

\[ rotation\_droite( Noeud(i, rotation\_gauche(A_g), A_d) ) \]

Question 13

Écrire la fonction rotation_gauche_droite. Là aussi, l'opération ne sera effectuée que si elle est possible.

Question 14

Dessiner le résultat obtenu après l'application de l'opération de rotation gauche-droite à l'arbre \(A_0\) suivant :

L'arbre \(A_0\).

La rotation droite-gauche de \(A = Noeud(i,A_g,A_d)\) est, s'il est défini, l'arbre :

\[ rotation\_gauche( Noeud(i, A_g, rotation\_droite(A_d)) ) \]

Question 15

Écrire la fonction rotation_droite_gauche.

Question 16

Dessiner le résultat obtenu après application de l'opération de rotation droite-gauche à l'arbre \(A_0\) défini à la question 14.

Arbres bicolores

Un arbre bicolore est un arbre binaire de recherche dont les nœuds sont colorés d'une couleur parmi deux selon des règles particulières énoncées ci-dessous. Si le rouge et noir sont classiquement utilisés, nous prendrons ici le blanc et noir.

On choisira d'autre part de ne pas étiqueter les feuilles.

Nouvelle représentation

On modifie la représentation des arbres afin d'ajouter l'information de coloriage.

On en profite pour ajouter dans un nœud un champ indiquant le père qui sera un arbre vide dans le cas de la racine. Les feuilles, non étiquetées, et qui ont une couleur fixe (voir ci-dessous) seront systématiquement représentées par des arbres vides. On supposera que les fonctions de rotation ont été corrigées pour tenir compte de cette nouvelle représentation.

Les types considérés seront donc :

type couleur = Blanc | Noir
type noeud = {
  mutable etiquette : int;
  mutable couleur : couleur;
  mutable gauche : arbre;
  mutable droit : arbre;
  mutable pere : arbre
}
and arbre = Nil | Noeud of noeud

Un arbre bicolore doit satisfaire aux contraintes suivantes (en plus d'être un ABR) :

a) Un nœud est soit blanc, soit noir.
b) Une feuille est noire.
c) La racine est noire.
d) Le père d'un nœud blanc est noir.
e) Tous les chemins partant d'un nœud donné et se terminant à une feuille contiennent le même nombre de nœuds noirs (sans prendre en compte le nœud de départ).

On nomme hauteur noire d'un nœud \(n\) appartenant à un arbre bicolore (on la note \(hn(n)\)) le nombre de nœuds noirs sur les chemins partant de ce nœud et aboutissant à une feuille (sans prendre en compte \(n\)). Cette fonction est bien définie grâce à la condition e).

On nomme hauteur noire d'un arbre bicolore la hauteur noire de sa racine.

Hauteur d'un arbre bicolore

Question 17

Montrer qu'un sous-arbre de racine \(n\) d'un arbre bicolore contient au moins \(2^{hn(n)} - 1\) nœuds internes.

Question 18

Montrer qu'un arbre bicolore comportant \(l\) nœuds internes a une hauteur au plus égale à \(2 \log_2(l+1)\).

Question 19

Que peut-on dire de l'ordre de grandeur de la complexité de la recherche d'un élément dans un arbre bicolore ?

Insertion dans un arbre bicolore

Pour insérer un nouveau nœud \(n\) dans un arbre bicolore, on commence par l'insérer selon l'algorithme d'insertion dans un ABR (on parlera d'insertion initiale), en lui affectant la couleur blanc. L'arbre obtenu ainsi n'est plus forcément bicolore, et il faut le modifier pour lui redonner cette propriété. L'algorithme utilisé est itératif, donc si au départ, le nœud courant \(n\) a deux fils qui sont des arbres vides, cette propriété n'est plus obligatoirement respectée aux itérations suivantes.

Question 20

Dans le cas où l'arbre initial est vide, quelle modification faut-il apporter pour que l'arbre résultat soit de nouveau bicolore ?

Question 21

Dans le cas d'un arbre non vide, que peut-on dire de l'arbre résultat si le père de \(n\) après insertion initiale est noir ?

On se place maintenant dans le cas où le père de \(n\) après insertion initiale (ou après itération) est blanc. Le père de \(n\) n'est donc pas la racine, et a lui-même un père qui est noir.

Les différents cas possibles sont donc (on note \(f_d\) et \(f_g\) les deux fils de \(n\), \(p\) son père, \(q\) son grand-père, \(f\) son frère et \(o\) son oncle) :

Les quatre cas (nœuds noirs pleins, nœuds blancs évidés, sous-arbres en triangles).

On suppose qu'au départ, tous les nœuds respectent la propriété e) des arbres bicolores et que seuls \(n\) et \(p\) violent la condition d).

Question 22

Que peut-on dire de la couleur du frère \(f\) de \(n\) ?

On va modifier l'arbre afin de retrouver un arbre bicolore. Deux familles de modifications sont possibles, selon la couleur de \(o\). On suppose tout d'abord que l'oncle \(o\) de \(n\) est blanc. Dans le cas 1, on effectue la transformation suivante :

Cas 1, oncle blanc.

Question 23

À quelle condition simple l'arbre global obtenu est-il bicolore ?

Question 24

Que faut-il faire si la condition n'est pas vérifiée afin de retrouver un arbre bicolore ?

Question 25

Quelle transformation faut-il effectuer dans les cas 2, 3 et 4 afin de retrouver un arbre bicolore, toujours en supposant que \(o\) est blanc ?

On suppose maintenant que l'oncle \(o\) de \(n\) est noir. Dans le cas 1, on effectue la transformation suivante :

Cas 1, oncle noir.

Question 26

Quelle est cette transformation ?

Question 27

Montrer que l'arbre global obtenu est bicolore.

Question 28

Montrer que dans le cas 2, si on effectue la même transformation, on ne peut pas trouver une coloration des nœuds \(p\), \(q\) et \(n\) telle que les contraintes d) et e) soient vérifiées.

Question 29

Dessiner et nommer la transformation à effectuer dans le cas 2 qui permette de conserver la hauteur noire vue du père du sous-arbre.

Question 30

Dessiner et nommer une transformation à effectuer dans le cas 3.

Question 31

Dessiner et nommer la transformation à effectuer dans le cas 4.

On suppose écrite la fonction d'insertion dans un ABR. Cette fonction retourne l'arbre binaire dont la racine est colorée en blanc et est étiquetée par l'élément qui vient d'être inséré.

On considère que cette fonction a le type suivant : inserer_arbre_binaire : arbre -> int -> arbre

Question 32

Écrire une fonction inserer_arbre_bicolore ayant le même type mais réalisant l'insertion dans un arbre bicolore.