datatype 'a RBtree = O | R of 'a * 'a RBtree * 'a RBtree | B of 'a * 'a RBtree * 'a RBtree ; fun balance ( B( z , R( y , R( x , t1 , t2 ) , t3 ) , t4 ) | B( z , R( x , t1 , R( y , t2 , t3 ) ) , t4 ) | B( x , t1 , R( y , t2 , R( z , t3 , t4 ) ) ) | B( x , t1 , R( z , R( y , t2 , t3 ) , t4) ) ) = R( y , B( x , t1 , t2 ) , B( z , t3 , t4 ) ) | balance t = t ; fun RBinsert x t = let fun ins( O ) = R( x , O , O ) | ins( R( y , l , r ) ) = if x <= y then R( y , ins l , r ) else R( y , l , ins r ) | ins( B( y , l , r ) ) = if x <= y then balance( B( y , ins l , r ) ) else balance( B( y , l , ins r ) ) ; in case ins t of R(x',l,r) => B(x',l,r) | t' => t' end ; foldl (fn(x,t) => RBinsert x t) O [9,4,6,1,2,3,8,5,7,0] ; foldl (fn(x,t) => RBinsert x t) O [0,1,2,3,4,5,6,7,8,9] ; RBinsert 10 it ;