TP 6 : Arbre de segments et ancêtre commun

Remarque : les arbres de segments ne doivent pas être confondus avec les arbres d'intervalles (la page Wikipedia sur les arbres de segments traite en fait des arbres d'intervalles).

Arbre de segments¶

Étant donné un tableau a et deux indices i et j, on souhaite pouvoir trouver efficacement le minimum de a.(i), a.(i + 1), ..., a.(j) (plus rapidement qu'en regardant chaque élément un par un, ce qui demanderait O($j - i$) opérations). Pour cela, on peut utiliser un arbre de segments :

Un arbre de segments est un arbre binaire dont les feuilles sont les éléments du tableau (ordonnés de gauche à droite) et chaque noeud $v$ possède une étiquette qui est un triplet (m, i, j) tel que le sous-arbre enraciné en v contienne les feuilles t.(i), ... , t.(j) et m est le minimum de ces valeurs.

Par exemple, voici un arbre de segments obtenu à partir du tableau [|5; 1; 2; 6; 3; 0|], où on a représenté seulement les minimums (premiers éléments de chaque triplet) :

On utilisera le fichier suivant qui définit un type tree et une fonction tree_to_tex pour dessiner un arbre (dans un nom de fichier donné en argument) :

In [30]:

#use "./draw_segment.ml"

#use "./draw_segment.ml"

type 'a tree = E | N of 'a * 'a tree * 'a tree
val tree_to_tex : string -> (int * 'a * 'b) tree -> unit = <fun>

Exercice

Écrire une fonction root pour renvoyer la racine d'un arbre. On renverra max_int si l'arbre est vide.

Exercice

Écrire une fonction build : int array -> (int * int * int) tree pour construire un arbre de segments récursivement à partir d'un tableau, en faisant en sorte qu'à chaque noeud N(r, g, d), le nombre de noeuds dans g et d diffère d'au plus $1$.

Exercice

Montrer que la hauteur de l'arbre construit précédemment est O($\log(n)$), si $n$ est le nombre d'éléments du tableau.

Exercice

Écrire une fonction update : int tree -> int -> int qui met à jour l'arbre de segments en ajoutant un nouvel élément.

Exercice

Écrire une fonction mini : int -> int -> int tree -> int telle que, si t est un arbre d'intervalles associé à un tableau a, mini i j t renvoie le minimum de a.(i), ..., a.(j). Pour cela, on remarquera qu'il y a $4$ cas possibles lorsqu'on est sur un noeud v = N((r, ri, rj), g, d) :

• Si ri > j || rj < i : alors le segment i, ..., j est disjoint du segment du noeud v, on peut renvoyer max_int (pas de minimum)
  Sinon, on pose m = (ri + rj) / 2.
• Si i > m alors il faut trouver le minimum dans d (appel récursif).
• Si j < m alors il faut trouver le minimum dans g (appel récursif).
• Sinon, il faut chercher le segment i, ..., m dans g, le segment (m+1), ..., j dans d, et prendre le minimum de ces $2$ valeurs.