package Ġcom . cr az yle g end . data structures and algorithms . trees . av l Ċ Ċ import Ġkotlin . math . max Ċ Ċ class ĠA VL Tree < T Ġ: ĠComparable < T >> Ġ{ ĊĊĠĠĠ Ġvar Ġroot : ĠA VL Node < T >? Ġ= Ġnull ĊĊĠĠĠ Ġfun Ġinsert ( value : ĠT ) Ġ{ ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġinsert ( root , Ġvalue ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġremove ( value : ĠT ) Ġ{ ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġremove ( root , Ġvalue ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġremove ( node : ĠA VL Node < T > ?, Ġvalue : ĠT ): ĠA VL Node < T >? Ġ{ ĊĠĠĠĠĠĠĠ Ġnode Ġ?: Ġreturn Ġnull ĊĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue Ġ== Ġnode . value Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Child Ġ== Ġnull Ġ&& Ġnode . right Child Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Child Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnode . right Child ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . right Child Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnode . left Child ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Child ?. min ?. value ?. let Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . value Ġ= Ġit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Child Ġ= Ġremove ( node . right Child , Ġnode . value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue Ġ< Ġnode . value Ġ-> Ġnode . left Child Ġ= Ġremove ( node . left Child , Ġvalue ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġnode . right Child Ġ= Ġremove ( node . right Child , Ġvalue ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġbal anced Node Ġ= Ġbal anced ( node ) ĊĠĠĠĠĠĠĠ Ġbal anced Node . height Ġ= Ġmax ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbal anced Node . left Height , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbal anced Node . right Height ĊĠĠĠĠĠĠĠ Ġ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġbal anced Node ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString () Ġ= Ġroot ?. toString () Ġ?: Ġ" empty Ġtree " ĊĊĠĠĠ Ġfun Ġcontains ( value : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcurrent Ġ= Ġroot ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( current Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current . value Ġ== Ġvalue ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Ġ= Ġif Ġ( value Ġ< Ġcurrent . value ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent . left Child ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent . right Child ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġbal anced ( node : ĠA VL Node < T >): ĠA VL Node < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ( node . balance Factor ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠ 2 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Child ?. balance Factor Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Right Rotate ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Rotate ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ- 2 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . right Child ?. balance Factor Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġright Left Rotate ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġleft Rotate ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġnode ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġleft Rotate ( node : ĠA VL Node < T >): ĠA VL Node < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġpivot Ġ= Ġnode . right Child !! ĊĠĠĠĠĠĠĠ Ġnode . right Child Ġ= Ġpivot . left Child ĊĠĠĠĠĠĠĠ Ġpivot . left Child Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġnode . height Ġ= Ġmax ( node . left Height , Ġnode . right Height ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġpivot . height Ġ= Ġmax ( pivot . left Height , Ġpivot . right Height ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġpivot ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġright Rotate ( node : ĠA VL Node < T >): ĠA VL Node < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġpivot Ġ= Ġnode . left Child !! ĊĠĠĠĠĠĠĠ Ġnode . left Child Ġ= Ġpivot . right Child ĊĠĠĠĠĠĠĠ Ġpivot . right Child Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġnode . height Ġ= Ġmax ( node . left Height , Ġnode . right Height ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġpivot . height Ġ= Ġmax ( pivot . left Height , Ġpivot . right Height ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġpivot ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġright Left Rotate ( node : ĠA VL Node < T >): ĠA VL Node < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġright Child Ġ= Ġnode . right Child Ġ?: Ġreturn Ġnode ĊĠĠĠĠĠĠĠ Ġnode . right Child Ġ= Ġright Rotate ( right Child ) ĊĠĠĠĠĠĠĠ Ġreturn Ġleft Rotate ( node ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġleft Right Rotate ( node : ĠA VL Node < T >): ĠA VL Node < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġleft Child Ġ= Ġnode . left Child Ġ?: Ġreturn Ġnode ĊĠĠĠĠĠĠĠ Ġnode . left Child Ġ= Ġright Rotate ( left Child ) ĊĠĠĠĠĠĠĠ Ġreturn Ġright Rotate ( node ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġinsert ( node : ĠA VL Node < T > ?, Ġvalue : ĠT ): ĠA VL Node < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġnode Ġ?: Ġreturn ĠA VL Node ( value ) ĊĠĠĠĠĠĠĠ Ġif Ġ( value Ġ< Ġnode . value ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left Child Ġ= Ġinsert ( node . left Child , Ġvalue ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Child Ġ= Ġinsert ( node . right Child , Ġvalue ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġbal anced Node Ġ= Ġbal anced ( node ) ĊĠĠĠĠĠĠĠ Ġbal anced Node . height Ġ= Ġmax ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbal anced Node . left Height , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbal anced Node . right Height ĊĠĠĠĠĠĠĠ Ġ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġreturn Ġbal anced Node ĊĠĠĠ Ġ} Ċ Ċ } Ċ