Arbre 2-3-4
Contenu du snippet
type 'a arbre = Nil
| D of 'a arbre * 'a * 'a arbre
| T of 'a arbre * 'a * 'a arbre * 'a * 'a arbre
| Q of 'a arbre * 'a * 'a arbre * 'a * 'a arbre * 'a * 'a arbre;;
let split4 = function
| Q(a1, k1, a2, k2, a3, k3, a4) -> (D(a1, k1, a2), k2, D(a3, k3, a4) )
| _ -> failwith("split 4") ;;
let i4 = function
| Q(a1, k1, a2, k2, a3, k3, a4) -> true
| _ -> false ;;
(* O(ln n) *)
let rec insert cmp v = function
| Nil -> failwith("insert")
| Q(a1, k1, a2, k2, a3, k3, a4) -> D(D(a1, k1, a2), k2, D(a3, k3, a4)) (*head*)
| D(Nil, k, Nil) -> if cmp v k = -1
then T(Nil, v, Nil, k, Nil)
else T(Nil, k, Nil, v, Nil)
| T(Nil, k1, Nil, k2, Nil) -> if cmp v k1 = -1
then Q(Nil, v, Nil, k1, Nil, k2, Nil)
else if cmp v k2 = 1
then Q(Nil, k1, Nil, k2, Nil, v, Nil)
else Q(Nil, k1, Nil, v, Nil, k2, Nil)
| D(a1, k1, a2) -> if cmp v k1 = -1
then if i4 a1
then let (a1', k1', a1'') = split4 a1
in insert cmp v (T (a1', k1', a1'', k1, a2))
else D (insert cmp v a1, k1, a2)
else if i4 a2
then let (a2', k2', a2'') = split4 a2
in insert cmp v (T (a1, k1, a2', k2', a2''))
else D (a1, k1, insert cmp v a2)
| T(a1, k1, a2, k2, a3) -> if cmp v k1 == -1
then if i4 a1
then let (a1', k1', a1'') = split4 a1 in if cmp v k1' = 1
then Q (a1', k1', insert cmp v a1'', k1, a2, k2, a3)
else Q (insert cmp v a1', k1', a1'', k1, a2, k2, a3)
else T(insert cmp v a1, k1, a2, k2, a3)
else if cmp v k2 = 1
then if i4 a3
then let (a3', k3', a3'') = split4 a3 in if cmp v k3' = 1
then Q (a1, k1, a2, k2, a3', k3', insert cmp v a3'')
else Q (a1, k1, a2, k2, insert cmp v a3', k3', a3'')
else T(a1, k1, a2, k2, insert cmp v a3)
else if i4 a2
then let (a2', k2', a2'') = split4 a2 in if cmp v k2' = 1
then Q (a1, k1, a2', k2', insert cmp v a2'', k2, a3)
else Q (a1, k1, insert cmp v a2', k2', a2'', k2, a3)
else T(a1, k1, insert cmp v a2, k2, a3);;
let insert cmp v tree = if tree = Nil then D(Nil, v, Nil) else insert cmp v tree;;
let cmp_i a b = if a < b then -1 else if a = b then 0 else 1;;
let insert_i = insert cmp_i;;
(* O(ln n) *)
let rec search cmp v = function
| Nil -> None
| D (a1, k1, a2) -> let c = cmp v k1 in
if c = 0 then Some k1 else search cmp v (if c = 1 then a2 else a1)
| T(a1, k1, a2, k2, a3) -> let c = cmp v k1 in
if c = 0 then Some k1 else if c = -1 then search cmp v a1
else search cmp v (D(a2, k2, a3))
| Q(a1, k1, a2, k2, a3, k3, a4) -> let c = cmp v k2 in
if c = 0 then Some k2 else if c = -1
then search cmp v (D(a1, k1, a2))
else search cmp v (D(a3, k3, a4));;
(* O(n) <=> O(2^p) *)
let arbre2li =
let rec i acc= function
| Nil -> acc
| D(a1, k1, a2) -> i (k1::(i acc a2)) a1
| T(a1, k1, a2, k2, a3) -> i (k1::(i acc (D(a2, k2, a3)) )) a1
| Q(a1, k1, a2, k2, a3, k3, a4) -> i (k1::(i acc (T(a2, k2, a3, k3, a4)))) a1
in i [];;
Compatibilité : Caml, CamlLight, ObjectiveCaml
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.