import Ġjava . util . Array Deque Ċ Ċ class ĠMap < Key : ĠComparable < Key >, Value : ĠAny > Ġ{ ĊĠĠĠ Ġprivate Ġval ĠRED Ġ= Ġtrue ĊĠĠĠ Ġprivate Ġval ĠBLACK Ġ= Ġfalse ĊĠĠĠ Ġprivate Ġvar Ġroot Ġ: ĠNode < Key , ĠValue > Ġ?= Ġnull ĊĠĠĠ Ġdata Ġclass ĠNode < Key , ĠValue >( var Ġkey : ĠKey , Ġvar Ġvalue : ĠValue , Ġvar Ġcolor : ĠBoolean , Ġvar Ġsize : Int ){ ĊĠĠĠĠĠĠĠ Ġvar Ġleft : ĠNode < Key , ĠValue >? = null ĊĠĠĠĠĠĠĠ Ġvar Ġright : ĠNode < Key , ĠValue >? = null ĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ"${ this . key } Ġ-> Ġ${ this . value }: Ġ${ this . color }" ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġfun Ġsize (): ĠInt { ĊĠĠĠĠĠĠĠ Ġreturn Ġsize ( root ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġfun Ġdelete Min (){ ĊĠĠĠĠĠĠĠ Ġif Ġ(! is Red ( root ?. left ) Ġ&& Ġ! is Red ( root ?. right )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot !!. color Ġ= ĠRED ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġdelete Min ( root ) ĊĠĠĠĠĠĠĠ Ġif ( this . size ()!= 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot ?. color Ġ= ĠBLACK ĊĠĠĠ Ġ} ĊĠĠĠ Ġfun Ġdelete Max (){ ĊĠĠĠĠĠĠĠ Ġif Ġ(! is Red ( root ?. left ) Ġ&& Ġ! is Red ( root ?. right )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot !!. color Ġ= ĠRED ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġdelete Max ( root ) ĊĠĠĠĠĠĠĠ Ġif ( this . size ()!= 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot ?. color Ġ= ĠBLACK ĊĠĠĠ Ġ} ĊĠĠĠ Ġfun Ġdelete ( key : ĠKey ){ ĊĠĠĠĠĠĠĠ Ġif (! is Red ( root ?. left ) Ġ&& Ġ! is Red ( root ?. right )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot ?. color Ġ= ĠRED ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġdelete ( root !! , Ġkey ) ĊĠĠĠĠĠĠĠ Ġif ( this . size () Ġ== Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot ?. color Ġ= ĠBLACK ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġis Red ( x : ĠNode < Key , ĠValue > ?) Ġ= Ġx ?. let Ġ{ Ġit . color Ġ== ĠRED Ġ} ?: false ĊĠĠĠ Ġprivate Ġfun Ġrotate Left ( x : ĠNode < Key , ĠValue >): ĠNode < Key , ĠValue >{ ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= Ġx . right ĊĠĠĠĠĠĠĠ Ġx . right Ġ= Ġh ?. left ĊĠĠĠĠĠĠĠ Ġh ?. left Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġh !!. color Ġ= Ġx . color ĊĠĠĠĠĠĠĠ Ġx . color Ġ= ĠRED ĊĠĠĠĠĠĠĠ Ġh . size Ġ= Ġx . size ĊĠĠĠĠĠĠĠ Ġx . size Ġ= Ġsize ( x . left ) Ġ+ Ġsize ( x . right ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġh ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġrotate Right ( x : ĠNode < Key , ĠValue >): ĠNode < Key , ĠValue >{ ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= Ġx . left ĊĠĠĠĠĠĠĠ Ġx . left Ġ= Ġh ?. right ĊĠĠĠĠĠĠĠ Ġh ?. right Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġh !!. color Ġ= Ġx . color ĊĠĠĠĠĠĠĠ Ġx . color Ġ= ĠRED ĊĠĠĠĠĠĠĠ Ġh . size Ġ= Ġx . size ĊĠĠĠĠĠĠĠ Ġx . size Ġ= Ġsize ( x . left ) Ġ+ Ġsize ( x . right ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġh ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġflip Colors ( x : ĠNode < Key , ĠValue > ){ ĊĠĠĠĠĠĠĠ Ġx . color Ġ= Ġ! x . color ĊĠĠĠĠĠĠĠ Ġx . left ?. color Ġ= Ġ! x . left ?. color !! ĊĠĠĠĠĠĠĠ Ġx . right ?. color Ġ= Ġ! x . right ?. color !! ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġsize ( x : ĠNode < Key , ĠValue >? ): ĠInt { ĊĠĠĠĠĠĠĠ Ġreturn Ġx ?. size Ġ?: Ġ 0 ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġget ( x : ĠNode < Key , ĠValue > ?, Ġkey : Key ): ĠNode < Key , ĠValue >? { ĊĠĠĠĠĠĠĠ Ġif ( x Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġval Ġcmp Ġ= Ġkey . compareTo ( x . key ) ĊĠĠĠĠĠĠĠ Ġreturn Ġif ( cmp Ġ> Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget ( x . right , Ġkey ) ĊĠĠĠĠĠĠĠ Ġelse Ġif ( cmp Ġ< Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget ( x . left , Ġkey ) ĊĠĠĠĠĠĠĠ Ġelse { ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġset ( x : ĠNode < Key , ĠValue > ?, Ġkey : Key , Ġvalue : Value ): ĠNode < Key , ĠValue >{ ĊĠĠĠĠĠĠĠ Ġif ( x Ġ== Ġnull ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠNode ( key , Ġvalue , ĠRED , Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcmp Ġ= Ġkey . compareTo ( x . key ) ĊĠĠĠĠĠĠĠ Ġif ( cmp Ġ> Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx . right Ġ= Ġset ( x . right , Ġkey , Ġvalue ) ĊĠĠĠĠĠĠĠ Ġelse Ġif ( cmp Ġ< Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx . left Ġ= Ġset ( x . left , Ġkey , Ġvalue ) ĊĠĠĠĠĠĠĠ Ġelse { ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġbalance ( x ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġmove Red Left ( x : ĠNode < Key , ĠValue >? ): Node < Key , Value > Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġflip Colors ( x 1 !! ) ĊĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 . right ?. left )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 . right Ġ= Ġrotate Right ( x 1 . right !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġrotate Left ( x 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġflip Colors ( x 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġx 1 ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġdelete Min ( x : ĠNode < Key , ĠValue >? ): ĠNode < Key , ĠValue >? { ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= x ĊĠĠĠĠĠĠĠ Ġif ( x !!. left Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġif (! is Red ( x . left ) Ġ&& Ġ! is Red (( x . left )) ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġmove Red Left ( x ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġx 1 !!. left Ġ= Ġdelete Min ( x 1 . left ) ĊĠĠĠĠĠĠĠ Ġreturn Ġbalance ( x 1 ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġmin ( x : Node < Key , Value >): ĠNode < Key , ĠValue >{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif ( x . left Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx ĊĠĠĠĠĠĠĠ Ġelse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmin ( x . left !! ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġdelete Max ( x : ĠNode < Key , ĠValue >? ): ĠNode < Key , ĠValue >? { ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 ?. left )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġrotate Right ( x !! ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif ( x 1 !!. right Ġ== Ġnull ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif (! is Red ( x 1 . right ) Ġ&& Ġ! is Red (( x 1 . right ?. left )) ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġmove Red Right ( x 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġx 1 . right Ġ= Ġdelete Max ( x 1 . right ) ĊĠĠĠĠĠĠĠ Ġreturn Ġbalance ( x 1 ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġdelete ( x : ĠNode < Key , ĠValue > ?, Ġkey : Key ): ĠNode < Key , ĠValue >? { ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġif ( key Ġ< Ġx 1 !!. key ){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif (! is Red ( x 1 . left ) Ġ&& Ġ! is Red ( x 1 . left ?. left )){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġmove Red Left ( x 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 . left Ġ= Ġdelete ( x 1 . left , Ġkey ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġelse { ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 . left )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġrotate Right ( x 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( key Ġ== Ġx 1 . key Ġ&& Ġx 1 . right Ġ== Ġnull ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif (! is Red ( x 1 . right ) Ġ&& Ġ! is Red ( x 1 . right ?. left )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġmove Red Right ( x 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( key Ġ== Ġx 1 . key ){ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġh Ġ= Ġmin ( x 1 . right !! ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 . key Ġ= Ġh . key ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 . value Ġ= Ġh . value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 . right Ġ= Ġdelete Min ( x 1 . right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} else ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 . right Ġ= Ġdelete ( x 1 . right , Ġkey ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġbalance ( x 1 ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġprivate Ġfun Ġmove Red Right ( x : ĠNode < Key , ĠValue >): ĠNode < Key , ĠValue > Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 Ġ= Ġx ĊĠĠĠĠĠĠĠ Ġflip Colors ( x 1 ) ĊĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 . left ?. left )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġrotate Right ( x 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġflip Colors ( x 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġx 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġbalance ( x : ĠMap . Node < Key , ĠValue >): ĠNode < Key , ĠValue > Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx 1 = Ġx ĊĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 . right ) Ġ&& Ġ! is Red ( x 1 . left )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġrotate Left ( x 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 . left ) Ġ&& Ġis Red ( x 1 . left ?. left )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx 1 Ġ= Ġrotate Right ( x 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif ( is Red ( x 1 . right ) Ġ&& Ġis Red ( x 1 . left )){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġflip Colors ( x 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġx 1 . size Ġ= Ġsize ( x 1 . left ) Ġ+ Ġsize ( x 1 . right ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġx 1 ĊĠĠĠ Ġ} ĊĠĠĠ Ġoperator Ġfun Ġget ( key : Key ): ĠValue ? { ĊĠĠĠĠĠĠĠ Ġreturn Ġroot ?. let Ġ{ Ġget ( it , Ġkey )?. value Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġoperator Ġfun Ġset ( key : ĠKey , Ġvalue : ĠValue ){ ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġset ( root , Ġkey , Ġvalue ) ĊĠĠĠĠĠĠĠ Ġroot !!. color Ġ= ĠBLACK ĊĠĠĠ Ġ} ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġstr B Ġ= ĠStringBuilder () ĊĠĠĠĠĠĠĠ Ġif ( root Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ" Empty ĠB ST " ĊĠĠĠĠĠĠĠ Ġval Ġq Ġ= ĠArray Deque < Node < Key , ĠValue >>() ĊĠĠĠĠĠĠĠ Ġq . push ( root !! ) ĊĠĠĠĠĠĠĠ Ġwhile (! q . isEmpty ()){ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsize Ġ= Ġq . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( i Ġin Ġ 0 Ġuntil Ġsize ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnow Ġ= Ġq . first ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstr B . append ("$ now Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . pop () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( now . left Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . add Last ( now . left !! ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( now . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq . add Last ( now . right !! ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstr B . append ("\ n ") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġstr B . toString () ĊĠĠĠ Ġ} Ċ }