X ENS Option Informatique MP MPI 2024Sujet, corrigé et rapport du jury

ECOLE POLYTECHNIQUE ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2024

Arbres équilibrés et géométrie algorithmique

Partie I. Préliminaires

Arbres binaires. Un arbre binaire est défini récursivement de la manière suivante : soit comme l'arbre vide, noté ⟩, qui ne contient aucun nœud; soit comme un nœud, noté ⟨ℓ, x, r⟩ avec un sous-arbre gauche ℓ, un élément x ∈ U à la racine et un sous-arbre droit r. On dessine un arbre tel que ⟨⟨⟩, w, ⟨⟨⟩, x, ⟨⟩⟩⟩, y, ⟨⟨⟩, z, ⟨⟩⟩⟩ de la manière suivante

avec la racine (ici y ) en haut, reliée aux sous-arbres gauche et droit dessinés en-dessous. Les sous-arbres vides ne sont pas dessinés, mais les liaisons vers les sous-arbres vides le sont.

• le parcours infixe de l'arbre vide ⟩ est la séquence vide;
• le parcours infixe d'un arbre ⟨ℓ, x, r⟩ est la concaténation, dans cet ordre, du parcours infixe de l'arbre ℓ, de l'élément x et du parcours infixe de l'arbre r.
  Ainsi, le parcours infixe de l'arbre précédent est la séquence w, x, y, z.
  Un arbre binaire t est un arbre binaire de recherche si la séquence de ses éléments donnée par un parcours infixe est triée par ordre strictement croissant. En particulier, un élément n'apparaît qu'au plus une fois dans cette séquence. Tous les arbres binaires manipulés dans ce sujet seront toujours des arbres binaires de recherche.

De tels arbres sont dits AVL (du nom de leurs auteurs, Adelson-Velsky et Landis). Ainsi, dans les deux arbres ci-dessous,

celui de gauche est un AVL mais celui de droite n'en est pas un (en supposant w < x < y < z par ailleurs).

val eq: elt -> elt -> bool
val lt: elt -> elt -> bool

type tree = E | N of int * tree * elt * tree

let height t = match t with E -> 0 | N(h, _, _, _) -> h

let node l x r = N(1 + max (height l) (height r), l, x, r)

Partie II. Construire des arbres AVL

• soit un arbre de hauteur h;
• soit un arbre de hauteur h + 1 avec un sous-arbre gauche de hauteur h − 1 et un sous-arbre droit de hauteur h.
  Indication : pour chaque cas qu'on choisit de distinguer dans la preuve, on pourra se contenter d'un schéma donnant la forme de l'arbre renvoyé annoté avec les hauteurs pertinentes.

let rotate_left $\mathrm{t}=$ match t with
    $\mid N\left(C_{-}, a, x, N\left(C_{-} b, y, c\right)\right) \rightarrow$ node (node $\left.a x b\right) y c$
    | _ -> assert false
let rotate_right $t=$ match $t$ with
    $\mid \mathrm{N}\left(\_, \mathrm{N}\left(\_, \mathrm{a}, \mathrm{x}, \mathrm{b}\right), \mathrm{y}, \mathrm{c}\right) \rightarrow$ node $\mathrm{a} \mathrm{x}($ node b y c$)$
    | _ -> assert false

    let rec join_right (l: tree) (x: elt) (r: tree) : tree =
    match 1 with
    | N(_, ll, lx, lr) ->
        if height $\operatorname{lr}<=$ height $\mathrm{r}+1$ then
            let $t=$ node $\operatorname{lr} x \mathrm{r}$ in
            if height $\mathrm{t}<=$ height $11+1$ then node 11 lx t
            else rotate_left (node 11 lx (rotate_right t))
        else
            let $t=$ join_right $\operatorname{lr} \times r$ in
            let $t^{\prime}=$ node $l l \operatorname{lx} t$ in
            if height $\mathrm{t}<=$ height $l l+1$ then t ' else rotate_left t '
    | E -> assert false
let rec join_left (l: tree) (x: elt) (r: tree) : tree =
let join (l: tree) (x: elt) (r: tree) : tree =
    if height $l>$ height $r+1$ then join_right $l \times r$
    else if height $r>$ height $l+1$ then join_left $l \times r$
    else node $1 \times \mathrm{r}$

let rec split (t: tree) (y: elt) : tree * bool * tree =
    match t with
    | E -> E, false, E
    | N(_, l, x, r) ->
        if eq y x then l, true, r
        else if lt y x then let ll, b, lr = split l y in ll, b, join lr x r
        else let rl, b, rr = split r y in join l x rl, b, rr
let insert (x: elt) (t: tree) : tree =
    let l, _, r = split t x in
    join l x r

let a = Array.make n E
let () = for i = 1 to n - 1 do a.(i) <- insert (i-1) a.(i-1) done

Partie III. Application : localisation d'un point dans le plan

On considère une subdivision du plan définie par un ensemble fini de polygones. Ces polygones peuvent partager des sommets et des arêtes. Les arêtes ne se croisent pas. Voici un exemple avec 7 points et trois polygones:

Approche. Notre approche consiste à diviser le plan en N + 1 tranches verticales, délimitées par les abscisses des N points. Sur notre exemple, on a donc 8 tranches :

type point = float * float
type edge = point * point (* avec x1 < x2 *)

let xmin ((x, _), _) = x
let xmax (_, (x, _)) = x

type elt = edge

type slab = { xleft: float; xright: float; tree: tree }

-\infty = slabs.(0).xleft < slabs.(0).xright = x(p0) = slabs.(1).xleft
    < slabs.(1).xright = x(p1)= slabs.(2).xleft
    < ...
    < slabs.(N).xright = +\infty

• L'arbre de la tranche 0 est vide.
• Pour construire l'arbre de la tranche i, pour 1 ≤ i ≤ N,
• on retire les arêtes qui se terminent au point p_(i − 1);
• on ajoute les arêtes qui démarrent au point p_(i − 1).

Localisation d'un point. Enfin, on peut utiliser le tableau slabs pour localiser un point p donné. On fait l'hypothèse que ce point n'est sur aucune arête, et est donc en particulier différent des N points p_i. Si on prend l'exemple suivant

alors le point p est d'abord localisé dans la tranche 4 puis, dans cette tranche, localisé entre les arêtes (p_2, p_4) et (p_2, p_5).

type answer = Outside | Between of edge * edge

* *
*