Arbre 2-3-4

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 377 fois - Téléchargée 8 fois

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

Disponible dans d'autres langages :

A voir également

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.