(* Exercice 1 *) (* 1.1 *) type color = int * int * int (* 1.2 *) type qtree = Color of color | Node of qtree * qtree * qtree * qtree (* 1.3 *) let rec color_count t (c:color) = match t with | Color(r,g,b) -> if c=(r,g,b) then 1 else 0 | Node(nw,ne,se,sw) -> color_count nw c + color_count ne c + color_count se c + color_count sw c (* 1.4 *) let rec clockwise t = match t with | Node (nw, ne, se, sw) -> Node (clockwise sw, clockwise nw, clockwise ne, clockwise se) | _ as x -> x (* 1.5 *) let rec lr_sym t = match t with | Node (nw, ne, se, sw) -> Node (lr_sym ne, lr_sym nw, lr_sym sw, lr_sym se) | _ as x -> x (* Exercice 2 *) type 'a btree = Leaf of 'a | Node of 'a btree * 'a * 'a btree (* 2.1 *) let t1 = Node ( Node ( Node (Leaf 0, 0, Leaf 0), 0, Leaf 0), 0, Leaf 0) type 'a htree = HLeaf of 'a | HNode of 'a htree * 'a * int * 'a htree (* 2.2 *) let height ht = match ht with HLeaf _ -> 0 | HNode(_,_,x,_) -> x (* 2.3 *) let make_htree l x r = HNode(l,x,1+max (height l) (height r), r) (* 2.4 *) let rec enrich t = match t with Leaf x -> HLeaf x | Node(l,x,r) -> let tl = enrich l in let tr = enrich r in make_htree tl x tr (* 2.5 *) let is_k_avl k t = let rec aux ht = match ht with HLeaf _ -> true | HNode (l, _, _, r) -> abs ((height l)- (height r)) <= k && aux l && aux r in aux (enrich t) (* 2.6 *) let is_perfect t = is_k_avl 0 t (* 2.7 *) (* (a) Les seuls arbres de hauteur 0 sont de la forme Leaf(x), contenant un noeud. On a donc m(0) = 1. (b) Soit t un 1-AVL de hauteur h. Si les deux sous-arbres de la racine ont la même hauteur h-1, on peut supprimer des noeuds à l'un des sous-arbres pour le rendre de hauteur h-2: la propriété d'être un 1-AVL est conservée lors de cette suppression. Autrement dit, on obtient un 1-AVL de hauteur h avec un nombre minimal de noeuds en formant un 1-AVL avec 2 sous-arbres de la racine, de hauteurs respectives h-1 et h-2, et chacun avec un nombre minimal de noeuds. On en déduit la relation m(h) = 1+ m(h-1) + m(h-2). (c) Comme on a clairement m(h-1) > m(h-2), on obtient m(h) > 1+ 2m(h-2). Donc m(h)+1 > 2(m(h-2)+1) (d) En itérant cette relation h/2 fois, on obtient m(h)+1 > 2^{h/2}(m(0)+1) > 2^{h/2} donc m(h)>=2^{h/2}. (e) On en déduit que log2 (m(h)) >= h/2, autrement dit, la hauteur est toujours inférieure à 2 log2(n+1). (f) Idem. *) (* 2.7 *)