fact: Definition balance rb t1 k t2 := match rb with | Red => Node Red t1 k t2 | _ => match t1 with | Node Red (Node Red a x b) y c => Node Red (Node Black a x b) y (Node Black c k t2) | Node Red a x (Node Red b y c) => Node Red (Node Black a x b) y (Node Black c k t2) | a => match t2 with | Node Red (Node Red b y c) z d => Node Red (Node Black t1 k b) y (Node Black c z d) | Node Red b y (Node Red c z d) => Node Red (Node Black t1 k b) y (Node Black c z d) | _ => Node Black t1 k t2 end end end.
imports: mathcomp(ssreflect ssrnat ssrbool eqtype)