autotests/input/highlight.sml

0001 datatype Colour = R | B
0002
0003 datatype 'a RBtree = E | N of Colour * 'a * 'a RBtree * 'a RBtree
0004
0005 (* Dieses lookup funktioniert nur fuer Elemente vom Typ int *)
0006
0007 fun lookup (x,E) = false
0008   | lookup (x,N(_,y,l,r)) =
0009        if x < y then lookup(x,l)
0010        else if y < x then lookup(x,r)
0011        else true
0012
0013 fun balance (B,x,N(R,y,N(R,z,t1,t2),t3),t4) =
0014        N(R,y,N(B,z,t1,t2),N(B,x,t3,t4))
0015   | balance (B,x,N(R,y,t1,N(R,z,t2,t3)),t4) =
0016        N(R,z,N(B,y,t1,t2),N(B,x,t3,t4))
0017   | balance (B,x,t1,N(R,y,N(R,z,t2,t3),t4)) =
0018        N(R,z,N(B,x,t1,t2),N(B,y,t3,t4))
0019   | balance (B,x,t1,N(R,y,t2,N(R,z,t3,t4))) =
0020        N(R,y,N(B,x,t1,t2),N(B,z,t3,t4))
0021   | balance t = N t
0022
0023 fun insert(x,t) =
0024    let
0025       fun ins E = N(R,x,E,E)
0026         | ins (t as N(c,y,l,r)) =
0027              if x < y then balance (c,y,ins l,r)
0028              else if y < x then balance (c,y,l,ins r)
0029              else t
0030       val N(_,y,l,r) = ins t
0031    in N(B,y,l,r)
0032    end