package Ġlesson 3 Ċ Ċ import Ġjava . util . Sorted Set Ċ import Ġkotlin . NoSuch ElementException Ċ import Ġjava . util . Tree Set Ċ Ċ // ĠAtt ention : Ġcomp arable Ġsupported Ġbut Ġcomparator Ġis Ġnot Ċ class ĠK t Binary Tree < T Ġ: ĠComparable < T >> Ġ: ĠAbstract Mutable Set < T >(), ĠCheck able Sorted Set < T > Ġ{ ĊĊĠĠĠ Ġprivate Ġvar Ġroot : ĠNode < T >? Ġ= Ġnull ĊĊĠĠĠ Ġoverride Ġvar Ġsize Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġset ĊĊĠĠĠ Ġprivate Ġclass ĠNode < T >( var Ġvalue : ĠT ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġvar Ġleft : ĠNode < T >? Ġ= Ġnull ĊĊĠĠĠĠĠĠĠ Ġvar Ġright : ĠNode < T >? Ġ= Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġadd ( element : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġclosest Ġ= Ġfind ( element ) ĊĠĠĠĠĠĠĠ Ġval Ġcomparison Ġ= Ġif Ġ( closest Ġ== Ġnull ) Ġ- 1 Ġelse Ġelement . compareTo ( closest . value ) ĊĠĠĠĠĠĠĠ Ġif Ġ( comparison Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval ĠnewNode Ġ= ĠNode ( element ) ĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġclosest Ġ== Ġnull Ġ-> Ġroot Ġ= ĠnewNode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomparison Ġ< Ġ 0 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( closest . left Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġclosest . left Ġ= ĠnewNode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( closest . right Ġ== Ġnull ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġclosest . right Ġ= ĠnewNode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġsize ++ ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcheck Invariant (): ĠBoolean Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot ?. let Ġ{ Ġcheck Invariant ( it ) Ġ} Ġ?: Ġtrue ĊĊĠĠĠ Ġprivate Ġfun Ġcheck Invariant ( node : ĠNode < T >): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġleft Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġif Ġ( left Ġ!= Ġnull Ġ&& Ġ( left . value Ġ>= Ġnode . value Ġ|| Ġ! check Invariant ( left ))) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġval Ġright Ġ= Ġnode . right ĊĠĠĠĠĠĠĠ Ġreturn Ġright Ġ== Ġnull Ġ|| Ġright . value Ġ> Ġnode . value Ġ&& Ġcheck Invariant ( right ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠÐ£ Ð´Ð°Ð» ÐµÐ½Ð¸Ðµ ĠÑįÐ»ÐµÐ¼ÐµÐ½ÑĤ Ð° ĠÐ² ĠÐ´ ÐµÑĢ ÐµÐ² Ðµ ĊĠĠĠĠ Ġ* ĠÐ¡ ÑĢÐµÐ´ Ð½Ñı Ñı ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ// ĠÐ¢ ÑĢÑĥ Ð´ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠÐ¢ Ġ= ĠO ( log N ) ĊĠĠĠ Ġ// ĠÐł ÐµÑģ ÑĥÑĢ Ñģ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠR Ġ= ĠO ( 1 ) ĊĊĠĠĠ Ġprivate Ġfun Ġenter ( node : ĠNode < T >, ĠnewNode : ĠNode < T > ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġparent Ġ= Ġfind Parent ( node . value ) ĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent Ġ== Ġnull Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( new Node Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot !!. value Ġ= ĠnewNode . value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot !!. left Ġ= ĠnewNode . left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġroot !!. right Ġ= ĠnewNode . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . left Ġ== Ġnode Ġ-> Ġparent . left Ġ= ĠnewNode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġparent . right Ġ== Ġnode Ġ-> Ġparent . right Ġ= ĠnewNode ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġdel ( node : ĠNode < T >) Ġ{ ĊĠĠĠĠĠĠĠ Ġenter ( node , Ġnull ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġremove ( element : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġelement 2 Ġ= Ġfind ( element ) ĊĠĠĠĠĠĠĠ Ġif Ġ( element 2 Ġ== Ġnull Ġ|| Ġelement 2 . value Ġ!= Ġelement ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelement 2 . left Ġ== Ġnull Ġ&& Ġelement 2 . right Ġ== Ġnull Ġ-> Ġdel ( element 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelement 2 . left Ġ== Ġnull Ġ-> Ġenter ( element 2 , Ġelement 2 . right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelement 2 . right Ġ== Ġnull Ġ-> Ġenter ( element 2 , Ġelement 2 . left ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġchange Ġ= Ġmin ( element 2 . right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġvalue Ġ= Ġchange !!. value ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremove ( change . value ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelement 2 . value Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġsize -- ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġmin ( root : ĠNode < T >? ): ĠNode < T >? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot Ġ== Ġnull Ġ-> Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot . left Ġ!= Ġnull Ġ-> Ġmin ( root . left ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġroot ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Parent ( value : ĠT , Ġstart : ĠNode < T >): ĠNode < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( start . left Ġ!= Ġnull Ġ&& Ġstart . left !!. value Ġ== Ġvalue Ġ|| Ġstart . right Ġ!= Ġnull Ġ&& Ġstart . right !!. value Ġ== Ġvalue ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġstart ĊĠĠĠĠĠĠĠ Ġval Ġcomparison Ġ= Ġvalue . compareTo ( start . value ) ĊĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomparison Ġ> Ġ 0 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( start . right Ġ== Ġnull ) Ġreturn Ġstart ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfind Parent ( value , Ġstart . right !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomparison Ġ< Ġ 0 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( start . left Ġ== Ġnull ) Ġreturn Ġstart ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfind Parent ( value , Ġstart . left !! ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġreturn Ġstart ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind Parent ( value : ĠT ): ĠNode < T >? Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull Ġ|| Ġ( root Ġas ĠNode < T >). value Ġ== Ġvalue ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġreturn Ġfind Parent ( value , Ġroot !! ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġoperator Ġfun Ġcontains ( element : ĠT ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġclosest Ġ= Ġfind ( element ) ĊĠĠĠĠĠĠĠ Ġreturn Ġclosest Ġ!= Ġnull Ġ&& Ġelement . compareTo ( closest . value ) Ġ== Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind ( value : ĠT ): ĠNode < T >? Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot ?. let Ġ{ Ġfind ( it , Ġvalue ) Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfind ( start : ĠNode < T >, Ġvalue : ĠT ): ĠNode < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġcomparison Ġ= Ġvalue . compareTo ( start . value ) ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomparison Ġ== Ġ 0 Ġ-> Ġstart ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcomparison Ġ< Ġ 0 Ġ-> Ġstart . left ?. let Ġ{ Ġfind ( it , Ġvalue ) Ġ} Ġ?: Ġstart ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġstart . right ?. let Ġ{ Ġfind ( it , Ġvalue ) Ġ} Ġ?: Ġstart ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġinner Ġclass ĠBinary Tree Iterator Ġ: ĠMutable Iterator < T > Ġ{ ĊĊĠĠĠĠĠĠĠ Ġprivate Ġvar Ġcurrent : ĠNode < T >? Ġ= Ġnull ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠÐŁ Ð¾ Ð¸Ñģ Ðº ĠÑģÐ»ÐµÐ´ÑĥÑİ Ñī ÐµÐ³Ð¾ ĠÑįÐ»ÐµÐ¼ÐµÐ½ÑĤ Ð° ĊĠĠĠĠĠĠĠĠ Ġ* ĠÐ¡ ÑĢÐµÐ´ Ð½Ñı Ñı ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġ// ĠÐ¢ ÑĢÑĥ Ð´ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠÐ¢ Ġ= ĠÐŀ ( N ) ĊĠĠĠĠĠĠĠ Ġ// ĠÐł ÐµÑģ ÑĥÑĢ Ñģ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠR Ġ= ĠÐŀ ( N ) ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġfind Next (): ĠNode < T >? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current Ġ== Ġnull ) Ġreturn Ġmin ( root ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoint Ġ= Ġcurrent Ġas ĠNode < T > ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoint . right Ġ!= Ġnull Ġ-> Ġmin ( point . right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġsearch Point : ĠNode < T >? Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġparent Ġ= Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( parent Ġ!= Ġpoint Ġ&& Ġparent Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcomparison Ġ= Ġpoint . value . compareTo ( parent . value ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcomparison Ġ> Ġ 0 Ġ-> Ġparent Ġ= Ġparent . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsearch Point Ġ= Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġparent Ġ= Ġparent . left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsearch Point ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġhas Next (): ĠBoolean Ġ= Ġfind Next () Ġ!= Ġnull ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġnext (): ĠT Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Ġ= Ġfind Next () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ( current Ġ?: Ġthrow ĠNoSuch ElementException ()). value ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠÐ£ Ð´Ð°Ð» ÐµÐ½Ð¸Ðµ ĠÑģÐ»ÐµÐ´ÑĥÑİ Ñī ÐµÐ³Ð¾ ĠÑįÐ»ÐµÐ¼ÐµÐ½ÑĤ Ð° ĊĠĠĠĠĠĠĠĠ Ġ* ĠÐ¡ Ð» Ð¾Ð¶ Ð½Ð°Ñı ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġ// ĠÐ¢ ÑĢÑĥ Ð´ Ð¾ ÐµÐ¼ Ðº Ð¾ÑĤ ÑĮ ĠÐ¢ Ġ= ĠO ( log N ) ĊĠĠĠĠĠĠĠ Ġ// ĠÐł ÐµÑģ ÑĥÑĢ Ñģ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠR Ġ= ĠO ( 1 ) ĊĊĠĠĠĠĠĠĠ Ġoverride Ġfun Ġremove () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current Ġ!= Ġnull ) Ġremove ( current !!. value ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġiterator (): ĠMutable Iterator < T > Ġ= ĠBinary Tree Iterator () ĊĊĠĠĠ Ġoverride Ġfun Ġcomparator (): ĠComparator < in ĠT >? Ġ= Ġnull ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠÐĶ Ð»Ñı ĠÑįÑĤ Ð¾Ð¹ ĠÐ·Ð°Ð´ Ð°Ñĩ Ð¸ ĠÐ½ ÐµÑĤ ĠÑĤ ÐµÑģÑĤ Ð¾Ð² Ġ( ÐµÑģÑĤ ÑĮ ĠÑĤÐ¾Ð»ÑĮÐºÐ¾ ĠÐ· Ð°Ð³ Ð¾ÑĤ Ð¾Ð² ÐºÐ° Ġsub Set Test ), ĠÐ½Ð¾ ĠÐµ Ñĳ ĠÑĤ Ð¾Ð¶ Ðµ ĠÐ¼Ð¾Ð¶Ð½Ð¾ ĠÑĢ ÐµÑĪ Ð¸ÑĤÑĮ ĠÐ¸ ĠÐ¸ Ñħ ĠÐ½Ð°Ð¿ Ð¸Ñģ Ð°ÑĤÑĮ ĊĠĠĠĠ Ġ* ĠÐŀ Ñĩ ÐµÐ½ÑĮ ĠÑģÐ» Ð¾Ð¶ Ð½Ð°Ñı ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġsub Set ( from Element : ĠT , Ġto Element : ĠT ): ĠSorted Set < T > Ġ{ ĊĠĠĠĠĠĠĠ ĠTODO () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠÐĿ Ð°Ð¹ ÑĤÐ¸ ĠÐ¼ Ð½ Ð¾Ð¶ ÐµÑģÑĤÐ²Ð¾ ĠÐ²ÑģÐµ Ñħ ĠÑįÐ»ÐµÐ¼ÐµÐ½ÑĤ Ð¾Ð² ĠÐ¼ ÐµÐ½ÑĮ ÑĪÐµ ĠÐ·Ð°Ð´ Ð°Ð½ Ð½Ð¾Ð³Ð¾ ĊĠĠĠĠ Ġ* ĠÐ¡ Ð» Ð¾Ð¶ Ð½Ð°Ñı ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ// ĠÐ¢ ÑĢÑĥ Ð´ Ð¾ ÐµÐ¼ Ðº Ð¾ÑĤ ÑĮ ĠÐ¢ Ġ= ĠO ( N ) ĊĠĠĠ Ġ// ĠÐł ÐµÑģ ÑĥÑĢ Ñģ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠR Ġ= ĠO ( N ) ĊĊĠĠĠ Ġoverride Ġfun Ġhead Set ( to Element : ĠT ): ĠSorted Set < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsorted Set Ġ= ĠTree Set < T >() ĊĠĠĠĠĠĠĠ Ġreturn Ġhead Set ( root , Ġlast (), Ġsorted Set ). head Set ( to Element ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġhead Set ( root : ĠNode < T > ?, Ġto Element : ĠT , Ġsorted Set : ĠSorted Set < T >): ĠSorted Set < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn Ġsorted Set ĊĠĠĠĠĠĠĠ Ġval Ġcomparison Ġ= Ġto Element . compareTo ( root . value ) ĊĠĠĠĠĠĠĠ Ġif Ġ( comparison Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsorted Set . add ( root . value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhead Set ( root . right , Ġto Element , Ġsorted Set ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġhead Set ( root . left , Ġto Element , Ġsorted Set ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġsorted Set ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠÐĿ Ð°Ð¹ ÑĤÐ¸ ĠÐ¼ Ð½ Ð¾Ð¶ ÐµÑģÑĤÐ²Ð¾ ĠÐ²ÑģÐµ Ñħ ĠÑįÐ»ÐµÐ¼ÐµÐ½ÑĤ Ð¾Ð² ĠÐ± Ð¾Ð»ÑĮ ÑĪÐµ ĠÐ¸Ð»Ð¸ ĠÑĢÐ°Ð ² Ð½ÑĭÑħ ĠÐ·Ð°Ð´ Ð°Ð½ Ð½Ð¾Ð³Ð¾ ĊĠĠĠĠ Ġ* ĠÐ¡ Ð» Ð¾Ð¶ Ð½Ð°Ñı ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ// ĠÐ¢ ÑĢÑĥ Ð´ Ð¾ ÐµÐ¼ Ðº Ð¾ÑĤ ÑĮ ĠÐ¢ Ġ= ĠO ( N ) ĊĠĠĠ Ġ// ĠÐł ÐµÑģ ÑĥÑĢ Ñģ Ð¾ ÐµÐ¼ Ðº Ð¾ÑģÑĤ ÑĮ ĠR Ġ= ĠO ( N ) ĊĊĠĠĠ Ġoverride Ġfun Ġtail Set ( from Element : ĠT ): ĠSorted Set < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsorted Set Ġ= ĠTree Set < T >() ĊĠĠĠĠĠĠĠ Ġreturn Ġtail Set ( root , Ġfirst (), Ġsorted Set ). tail Set ( from Element ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġtail Set ( root : ĠNode < T > ?, Ġfrom Element : ĠT , Ġsorted Set : ĠSorted Set < T >): ĠSorted Set < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( root Ġ== Ġnull ) Ġreturn Ġsorted Set ĊĠĠĠĠĠĠĠ Ġval Ġcomparison Ġ= Ġfrom Element . compareTo ( root . value ) ĊĠĠĠĠĠĠĠ Ġif Ġ( comparison Ġ<= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsorted Set . add ( root . value ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtail Set ( root . right , Ġfrom Element , Ġsorted Set ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtail Set ( root . left , Ġfrom Element , Ġsorted Set ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġsorted Set ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġfirst (): ĠT Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcurrent : ĠNode < T > Ġ= Ġroot Ġ?: Ġthrow ĠNoSuch ElementException () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( current . left Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Ġ= Ġcurrent . left !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcurrent . value ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġlast (): ĠT Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcurrent : ĠNode < T > Ġ= Ġroot Ġ?: Ġthrow ĠNoSuch ElementException () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( current . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurrent Ġ= Ġcurrent . right !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcurrent . value ĊĠĠĠ Ġ} Ċ } Ċ