Arbres binaires de recherche

On considère le type suivant :

type 'a abr = 
    | Noeud of 'a abr * 'a * 'a abr
    | Nil

On reprend la définition du cours : un arbre binaire est un arbre binaire de recherche (abr) s'il est vide ou si ses deux sous-arbres sont des abr et si l'étiquette \(x\) de sa racine vérifie \(\max_{y \in g} y \le x \le \min_{y \in d} y\), où \(g\) et \(d\) sont les sous-arbres gauche et droit (on autorise donc les doublons).

Question 1. Écrire une fonction etendue qui à tout arbre a non vide renvoie le couple (min_v, max_v) constitué des valeurs minimale et maximale de ses étiquettes.

Corrigé

let rec etendue a =
    match a with
    | Nil -> failwith "Arbre vide"
    | Noeud(Nil,x,Nil) -> (x,x)
    | Noeud(a',x,Nil) | Noeud(Nil,x,a') -> 
        let min_a', max_a' = etendue a' in
        (min min_a' x, max max_a' x)
    | Noeud(g,x,d) ->
        let min_g, max_g = etendue g in
        let min_d, max_d = etendue d in
        (min (min min_g min_d) x,
         max (max max_g max_d) x)

Question 2. En déduire une fonction est_abr1 qui renvoie un booléen indiquant si un arbre binaire est un abr.

Corrigé

let rec est_abr1 a =
    match a with
    | Nil | Noeud(Nil,_,Nil) -> true
    | Noeud(g,x,Nil) ->
        let _, max_g = etendue g in
        est_abr1 g && max_g <= x
    | Noeud(Nil,x,d) ->
        let min_d, _ = etendue d in
        est_abr1 d && x <= min_d
    | Noeud(g, x, d) ->
        let _, max_g = etendue g in
        let min_d, _ = etendue d in
        est_abr1 g && est_abr1 d && max_g <= x && x <= min_d

Question 3. Expliquer pourquoi cette fonction n'est pas efficace et en déduire une version est_abr linéaire dans le nombre de nœuds de l'arbre binaire.

Corrigé

est_abr1 appelle etendue sur chaque sous-arbre, ce qui parcourt à nouveau tout ce sous-arbre : chaque nœud est visité autant de fois qu'il a d'ancêtres, d'où une complexité quadratique dans le pire cas (pour un peigne). On renvoie plutôt, en un seul parcours, le booléen et l'étendue.

let rec est_abr_aux a =
    match a with
    | Nil -> failwith "Arbre vide"
    | Noeud(Nil,x,Nil) -> (true, x, x)
    | Noeud(g,x,Nil) ->
        let abr_g, min_g, max_g = est_abr_aux g in
        (abr_g && max_g <= x, min_g, x)
    | Noeud(Nil,x,d) ->
        let abr_d, min_d, max_d = est_abr_aux d in
        (abr_d && x <= min_d, x, max_d)
    | Noeud(g, x, d) ->
        let abr_g, min_g, max_g = est_abr_aux g in
        let abr_d, min_d, max_d = est_abr_aux d in
        (abr_g && abr_d && max_g <= x && x <= min_d,
            min_g, max_d)

let est_abr a =
    match a with
    | Nil -> true
    | _ -> let b, _, _ = est_abr_aux a in b

Question 4. Écrire une fonction contient qui teste si une valeur est présente dans un abr.

Corrigé

Deux versions possibles, puis une version à éviter :

let rec contient x a =
    match a with
    | Nil -> false
    | Noeud(_,y,_) when x = y -> true
    | Noeud(g,y,_) when x < y -> contient x g
    | Noeud(_,y,d) -> contient x d

let rec contient x a =
    match a with
    | Nil -> false
    | Noeud(g,y,d) -> 
            x = y || (if x < y then contient x g else contient x d)

(* à éviter : *)
let rec contient x a =
    match a with
    | Nil -> false
    | Noeud(g,y,d) -> 
        if x = y
        then true (* perdu *)
        else if x < y 
             then contient x g
             else if x > y 
                  then contient x d
                  else false (* impossible a atteindre *)

Question 5. Écrire une fonction insere qui rajoute un élément dans un abr et renvoie le nouvel abr.

Corrigé

let rec insere x a =
    match a with
    | Nil -> Noeud(Nil, x, Nil)
    | Noeud(g,y,d) -> 
        if x <= y
        then Noeud(insere x g, y, d)
        else Noeud(g, y, insere x d)

Question 6. Écrire une fonction supprime qui supprime un élément d'un abr et renvoie le nouvel abr. Si jamais l'élément n'est pas dedans, cette fonction se comporte comme l'identité.

On pourra définir une fonction plus_a_droite qui renvoie le nœud le plus à droite d'un abr.

Corrigé

(* On va chercher le noeud le plus à droite y et on le court-circuite en
   renvoyant le couple (y, a') où a' est a privé de y *)
let rec plus_a_droite a =
    match a with
    | Nil -> failwith "Vide"
    | Noeud(g,y,Nil) -> (y, g)
    | Noeud(g,y,d) ->
        let z, d' = plus_a_droite d in
        (z, Noeud(g,y,d'))

let rec supprime x a =
    match a with
    | Noeud(Nil, y, Nil) when x = y -> Nil
    | Noeud(g, y, Nil) when x = y -> g
    | Noeud(Nil, y, d) when x = y -> d
    | Noeud(g, y, d) when x = y ->
        let z, g' = plus_a_droite g in
        Noeud(g', z, d)
    | Noeud(g, y, d) ->
        if x < y then Noeud(supprime x g, y, d)
                 else Noeud(g, y, supprime x d)
    | _ -> a

Arbres 2-3 et 2-3-4

On définit les deux types suivants :

type 'a a23 =
    | Bin23 of 'a a23 * 'a * 'a a23
    | Ter23 of 'a a23 * 'a * 'a a23 * 'a * 'a a23
    | Nil23

type 'a a234 =
    | Bin234 of 'a a234 * 'a * 'a a234
    | Ter234 of 'a a234 * 'a * 'a a234 * 'a * 'a a234
    | Quat234 of 'a a234 * 'a * 'a a234 
        * 'a * 'a a234 * 'a * 'a a234
    | Nil234

Question 7. Écrire une fonction insere23 qui insère un élément dans un arbre 2-3 en utilisant un arbre 2-3-4 de manière transitoire.

Corrigé

On commence par des fonctions de conversion :

let rec vers234 a =
    match a with
    | Nil23 -> Nil234
    | Bin23(g,x,d) -> Bin234(vers234 g, x, vers234 d)
    | Ter23(g,x,m,y,d) -> Ter234(vers234 g, x, vers234 m, y, vers234 d)

let rec vers23 a =
    match a with
    | Nil234 -> Nil23
    | Bin234(g,x,d) -> Bin23(vers23 g, x, vers23 d)
    | Ter234(g,x,m,y,d) -> Ter23(vers23 g, x, vers23 m, y, vers23 d)
    | _ -> failwith "Quaternaire"

On insère alors dans une feuille, ce qui peut créer un nœud quaternaire, que l'on fait remonter en l'éclatant en deux nœuds binaires et en insérant sa clé médiane dans le père (repare234). Si la racine devient quaternaire, on l'éclate et la hauteur augmente de 1.

let elim_racine_quat a =
    match a with
    | Quat234(g,x,m,y,n,z,d) -> Bin234( Bin234(g,x,m), y, Bin234(n,z,d) )
    | _ -> a

let rec repare234 a =
    match a with
    | Bin234(Quat234(g,x,m,y,n,z,d),t,d') ->
            Ter234(Bin234(g,x,m), y, Bin234(n,z,d), t, d')
    | Bin234(g',t, Quat234(g,x,m,y,n,z,d)) ->
            Ter234(g', t, Bin234(g,x,m), y, Bin234(n, z,d))
    | Ter234(Quat234(g,x,m,y,n,z,d),x',m',y',d') ->
        Quat234(Bin234(g,x,m),y,Bin234(n,z,d),x',m',y',d')
    | Ter234(g',x',Quat234(g,x,m,y,n,z,d),y',d') ->
        Quat234(g',x',Bin234(g,x,m),y,Bin234(n,z,d),y',d')
    | Ter234(g',x',m',y',Quat234(g,x,m,y,n,z,d)) ->
        Quat234(g',x',m',y',Bin234(g,x,m),y,Bin234(n,z,d))
    | _ -> a

let rec insere23_aux x a =
    match a with
    | Nil23 -> Bin234(Nil234, x, Nil234)
    | Bin23(Nil23,y,Nil23) -> 
        if x <= y
        then Ter234(Nil234,x,Nil234,y,Nil234)
        else Ter234(Nil234,y,Nil234,x,Nil234)
    | Bin23(g, y, d) -> repare234
        (if x <= y then Bin234(insere23_aux x g, y, vers234 d)
                  else Bin234(vers234 g, y, insere23_aux x d))
    | Ter23(Nil23,y,Nil23,z,Nil23) -> 
        if x <= y
        then Quat234(Nil234, x, Nil234, y, Nil234, z, Nil234)
        else if x <= z
            then Quat234(Nil234, y, Nil234, x, Nil234, z, Nil234)
            else Quat234(Nil234, y, Nil234, z, Nil234, x, Nil234)
    | Ter23(g,y,m,z,d) -> repare234
        (if x <= y
        then Ter234(insere23_aux x g, y, vers234 m, z, vers234 d)
        else if x <= z
            then Ter234(vers234 g, y, insere23_aux x m, z, vers234 d)
            else Ter234(vers234 g, y, vers234 m, z, insere23_aux x d))


let insere23 a x = vers23 (elim_racine_quat (insere23_aux x a))