fact: Fixpoint append (l:tree) : tree -> tree := match l with | Leaf => fun r => r | Node lc ll lx lr => fix append_l (r:tree) : tree := match r with | Leaf => l | Node rc rl rx rr => match lc, rc with | Red, Red => let lrl := append lr rl in match lrl with | Rd lr' x rl' => Rd (Rd ll lx lr') x (Rd rl' rx rr) | _ => Rd ll lx (Rd lrl rx rr) end | Black, Black => let lrl := append lr rl in match lrl with | Rd lr' x rl' => Rd (Bk ll lx lr') x (Bk rl' rx rr) | _ => lbalS ll lx (Bk lrl rx rr) end | Black, Red => Rd (append_l rl) rx rr | Red, Black => Rd ll lx (append lr r) end end end.
imports: Bool List BinPos Pnat Setoid SetoidList PeanoNat