@ file : Suppress (" Too Many Functions ") Ċ Ċ package Ġhome work 4 Ċ Ċ import Ġkotlin . math . max Ċ Ċ class ĠAv l Node < K Ġ: ĠComparable < K >, ĠV >( override Ġval Ġkey : ĠK , Ġprivate Ġvar Ġprivate Value : ĠV ) Ġ: ĠMap . Entry < K , ĠV > Ġ{ ĊĠĠĠ Ġprivate Ġvar Ġheight : ĠInt Ġ= Ġ 0 ĊĠĠĠ Ġoverride Ġval Ġvalue : ĠV ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġprivate Value ĊĠĠĠ Ġprivate Ġvar Ġleft Node : ĠAv l Node < K , ĠV >? Ġ= Ġnull ĊĠĠĠ Ġprivate Ġvar Ġright Node : ĠAv l Node < K , ĠV >? Ġ= Ġnull ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval Ġbalance Factor Value Ġ= Ġ 2 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġbalance (): ĠAv l Node < K , ĠV > Ġ{ ĊĠĠĠĠĠĠĠ Ġleft Node Ġ= Ġleft Node ?. balance () ĊĠĠĠĠĠĠĠ Ġright Node Ġ= Ġright Node ?. balance () ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( this . get Balance Factor ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbalance Factor Value Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . left Node ?. get Balance Factor () Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . big Left Rotate () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . right Rotate () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ- balance Factor Value Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . right Node ?. get Balance Factor () Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . big Right Rotate () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . left Rotate () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġthis ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Balance Factor (): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġupdate Height () ĊĠĠĠĠĠĠĠ Ġreturn Ġ( left Node ?. height Ġ?: Ġ 0 ) Ġ- Ġ( right Node ?. height Ġ?: Ġ 0 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġupdate Height () Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . left Node ?. update Height () ĊĠĠĠĠĠĠĠ Ġthis . right Node ?. update Height () ĊĠĠĠĠĠĠĠ Ġheight Ġ= Ġmax ( left Node ?. height Ġ?: Ġ 0 , Ġright Node ?. height Ġ?: Ġ 0 ) Ġ+ Ġ 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġleft Rotate (): ĠAv l Node < K , ĠV > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġpivot Ġ= Ġthis . right Node !! ĊĠĠĠĠĠĠĠ Ġthis . right Node Ġ= Ġpivot . left Node ĊĠĠĠĠĠĠĠ Ġpivot . left Node Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġthis . height Ġ= Ġmax ( this . left Node ?. height Ġ?: Ġ 0 , Ġthis . right Node ?. height Ġ?: Ġ 0 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġpivot . height Ġ= Ġmax ( pivot . left Node ?. height Ġ?: Ġ 0 , Ġpivot . right Node ?. height Ġ?: Ġ 0 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġpivot ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġbig Left Rotate (): ĠAv l Node < K , ĠV > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġleft Child Ġ= Ġthis . left Node Ġ?: Ġreturn Ġthis ĊĠĠĠĠĠĠĠ Ġthis . left Node Ġ= Ġleft Child . left Rotate () ĊĠĠĠĠĠĠĠ Ġreturn Ġthis . right Rotate () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġright Rotate (): ĠAv l Node < K , ĠV > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġpivot Ġ= Ġthis . left Node !! ĊĠĠĠĠĠĠĠ Ġthis . left Node Ġ= Ġpivot . right Node ĊĠĠĠĠĠĠĠ Ġpivot . right Node Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġthis . height Ġ= Ġmax ( this . left Node ?. height Ġ?: Ġ 0 , Ġthis . right Node ?. height Ġ?: Ġ 0 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġpivot . height Ġ= Ġmax ( pivot . left Node ?. height Ġ?: Ġ 0 , Ġpivot . right Node ?. height Ġ?: Ġ 0 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġpivot ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġbig Right Rotate (): ĠAv l Node < K , ĠV > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġright Child Ġ= Ġthis . right Node Ġ?: Ġreturn Ġthis ĊĠĠĠĠĠĠĠ Ġthis . right Node Ġ= Ġright Child . right Rotate () ĊĠĠĠĠĠĠĠ Ġreturn Ġthis . left Rotate () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd ( key : ĠK , ĠnewValue : ĠV ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ< Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Node Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Node Ġ= ĠAv l Node ( key , ĠnewValue ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Node ?. add ( key , ĠnewValue ) Ġ?: Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ> Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( right Node Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Node Ġ= ĠAv l Node ( key , ĠnewValue ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Node ?. add ( key , ĠnewValue ) Ġ?: Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Value Ġ= ĠnewValue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove ( key : ĠK , Ġparent Node : ĠAv l Node < K , ĠV >? ): ĠAv l Node < K , ĠV >? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ< Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . left Node Ġ= Ġthis . left Node ?. remove ( key , Ġthis ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ> Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . right Node Ġ= Ġthis . right Node ?. remove ( key , Ġthis ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġremove ByKey ( key , Ġparent Node ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġremove ByKey ( key : ĠK , Ġprevious Node : ĠAv l Node < K , ĠV >? ): ĠAv l Node < K , ĠV >? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Node Ġ== Ġnull Ġ-> Ġthis . right Node ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Node Ġ== Ġnull Ġ-> Ġthis . left Node ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġminimum Node Ġ= Ġthis . right Node ?. get Minimum Node () Ġ?: Ġthis ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( previous Node ?. left Node Ġ== Ġthis ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprevious Node . left Node Ġ= Ġminimum Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprevious Node ?. right Node Ġ= Ġminimum Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġminimum Node . left Node Ġ= Ġthis . left Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . right Node ?. key Ġ!= Ġminimum Node . key ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . right Node ?. remove Minimum Node ( key ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġminimum Node . right Node Ġ= Ġthis . right Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġminimum Node . right Node Ġ= Ġminimum Node . right Node ?. right Node ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġminimum Node . balance () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġget Minimum Node (): ĠAv l Node < K , ĠV > Ġ= Ġleft Node ?. get Minimum Node () Ġ?: Ġthis ĊĊĠĠĠ Ġprivate Ġfun Ġremove Minimum Node ( minimum Key : ĠK ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( left Node ?. key Ġ== Ġminimum Key ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Node Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Node ?. remove Minimum Node ( minimum Key ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġis ContainsKey ( key : ĠK ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ< Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . left Node ?. is ContainsKey ( key ) Ġ?: Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ> Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . right Node ?. is ContainsKey ( key ) Ġ?: Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġis Contains Value ( value : ĠV ): ĠBoolean Ġ= Ġthis . private Value Ġ== Ġvalue Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Node ?. is Contains Value ( value ) Ġ?: Ġfalse Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Node ?. is Contains Value ( value ) Ġ?: Ġfalse ĊĊĠĠĠ Ġfun ĠgetValue ByKey ( key : ĠK ): ĠV ? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ< Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . left Node ?. getValue ByKey ( key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġkey Ġ> Ġthis . key Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . right Node ?. getValue ByKey ( key ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġthis . private Value ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġget Entries ( entries : ĠMutable Set < Av l Node < K , ĠV >>) Ġ{ ĊĠĠĠĠĠĠĠ Ġentries . add ( this ) ĊĠĠĠĠĠĠĠ Ġthis . left Node ?. get Entries ( entries ) ĊĠĠĠĠĠĠĠ Ġthis . right Node ?. get Entries ( entries ) ĊĠĠĠ Ġ} Ċ } Ċ