package Ġl td . rust _ lang . utils . tree Ċ Ċ class ĠRB Tree < E >( comparator : ĠComparator < E >? Ġ= Ġnull ) Ġ: ĠB ST Ext < E >( comparator ) Ġ{ ĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠRED Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠBLACK Ġ= Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcreate Node ( e : ĠE , Ġparent : ĠNode < E >? ): ĠNode < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠRB Node ( e , Ġparent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġset Color ( color : ĠBoolean , Ġnode : ĠNode < E >? ): ĠNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( node Ġas ĠRB Node < E >). color Ġ= Ġcolor ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġset Red ( node : ĠNode < E >? ): ĠNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġset Color ( RED , Ġnode ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġset Black ( node : ĠNode < E >? ): ĠNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġset Color ( BLACK , Ġnode ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcolor Of ( node : ĠNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ( node Ġas ĠRB Node < E > ?) ?. color Ġ?: ĠBLACK ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġis Black ( node : ĠNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġcolor Of ( node ) Ġ== ĠBLACK ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġis Red ( node : ĠNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġcolor Of ( node ) Ġ== ĠRED ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġinner Ġclass ĠRB Node < E >( e : ĠE , Ġparent : ĠNode < E > ?) Ġ: ĠNode < E >( e , Ġparent ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcolor : ĠBoolean Ġ= ĠRED ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġstr Ġ= Ġ"" ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( color Ġ== ĠRED ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstr Ġ= Ġ" R _" ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġstr Ġ+ Ġelement . toString () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġafter Add ( tmp : ĠNode < E > ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġparent Ġ= Ġtmp ?. parent ĊĠĠĠĠĠĠĠ Ġif Ġ( parent Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( tmp ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( is Black ( parent )) Ġreturn ĊĊĠĠĠĠĠĠĠ Ġval Ġun cle Ġ= Ġparent . sibling () ĊĠĠĠĠĠĠĠ Ġval Ġgrand pa Ġ= Ġset Red ( parent . parent ) ĊĠĠĠĠĠĠĠ Ġif Ġ( is Red ( unc le )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( unc le ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġafter Add ( grand pa ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhen Ġ( Pair ( parent . is Left Child (), Ġtmp . is Left Child ())) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( first Ġ= Ġtrue , Ġsecond Ġ= Ġtrue ) Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠLL ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( grand pa ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( first Ġ= Ġtrue , Ġsecond Ġ= Ġfalse ) Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠLR ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( tmp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( grand pa ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( first Ġ= Ġfalse , Ġsecond Ġ= Ġtrue ) Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRL ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( tmp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( grand pa ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠPair ( first Ġ= Ġfalse , Ġsecond Ġ= Ġfalse ) Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRR ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( grand pa ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġafter Remove ( tmp : ĠNode < E > ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( is Red ( tmp )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( tmp ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġparent Ġ= Ġtmp !!. parent Ġ?: Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġis Left Ġ= Ġparent . left Ġ== Ġnull Ġ|| Ġtmp . is Left Child () ĊĠĠĠĠĠĠĠ Ġvar Ġsibling Ġ= Ġif Ġ( is Left ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . right ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . left ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( is Left ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Red ( sibling )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( sibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Red ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsibling Ġ= Ġparent . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Black ( sibling !!. left ) Ġ&& Ġis Black ( sibling . right )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġis Parent Black Ġ= Ġis Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Red ( sibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Parent Black ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġafter Remove ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Black ( sibling . right )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( sibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsibling Ġ= Ġparent . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Color ( color Of ( parent ), Ġsibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( sibling !!. right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Red ( sibling )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( sibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Red ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsibling Ġ= Ġparent . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Black ( sibling !!. left ) Ġ&& Ġis Black ( sibling . right )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġis Parent Black Ġ= Ġis Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Red ( sibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Parent Black ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġafter Remove ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Black ( sibling . left )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( sibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsibling Ġ= Ġparent . left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Color ( color Of ( parent ), Ġsibling ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( sibling !!. left ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġset Black ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( parent ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ