KheyENSAE4
2022-12-09 20:07:45
Le 09 décembre 2022 à 20:06:13 :
jane street? ok implémente moi un RB tree en ocaml
type color = Red | Black
type 'a rbtree =
| Leaf
| Node of color * 'a * 'a rbtree * 'a rbtree
(* insert x into the tree t, and balance the tree if necessary *)
let insert x t =
let rec ins = function
| Leaf -> Node (Red, x, Leaf, Leaf)
| Node (c, y, l, r) as t ->
if x < y then balance c y (ins l) r
else if x > y then balance c y l (ins r)
else t
in
match ins t with
| Leaf -> failwith "unexpected leaf"
| Node (_, x, l, r) -> Node (Black, x, l, r)
(* balance a tree according to the red-black tree rules *)
and balance = function
| Black, z, Node (Red, y, Node (Red, x, a, b), c), d ->
Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
| Black, z, Node (Red, x, a, Node (Red, y, b, c)), d ->
Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
| Black, x, a, Node (Red, z, Node (Red, y, b, c), d) ->
Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
| Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
| c, x, l, r -> Node (c, x, l, r)