/* Ċ Ġ* ĠCopyright Ġ( c ) Ġ 2 0 1 0 - 2 0 1 6 ĠW illiam ĠBit tle Ġ Ġhttp :// www . dyn 4 j . org / Ċ Ġ* ĠAll Ġrights Ġreserved . Ċ Ġ* ĠĊ Ġ* ĠRedistribution Ġand Ġuse Ġin Ġsource Ġand Ġbinary Ġforms , Ġwith Ġor Ġwithout Ġmodification , Ġare Ġpermitted ĠĊ Ġ* Ġprovided Ġthat Ġthe Ġfollowing Ġconditions Ġare Ġmet : Ċ Ġ* ĠĊ Ġ* ĠĠ Ġ* ĠRedistributions Ġof Ġsource Ġcode Ġmust Ġretain Ġthe Ġabove Ġcopyright Ġnotice , Ġthis Ġlist Ġof Ġconditions ĠĊ Ġ* ĠĠĠĠ Ġand Ġthe Ġfollowing Ġdisclaimer . Ċ Ġ* ĠĠ Ġ* ĠRedistributions Ġin Ġbinary Ġform Ġmust Ġreproduce Ġthe Ġabove Ġcopyright Ġnotice , Ġthis Ġlist Ġof Ġconditions ĠĊ Ġ* ĠĠĠĠ Ġand Ġthe Ġfollowing Ġdisclaimer Ġin Ġthe Ġdocumentation Ġand / or Ġother Ġmaterials Ġprovided Ġwith Ġthe ĠĊ Ġ* ĠĠĠĠ Ġdistribution . Ċ Ġ* ĠĠ Ġ* ĠNeither Ġthe Ġname Ġof Ġdyn 4 j Ġnor Ġthe Ġnames Ġof Ġits Ġcontributors Ġmay Ġbe Ġused Ġto Ġendorse Ġor ĠĊ Ġ* ĠĠĠĠ Ġpromote Ġproducts Ġderived Ġfrom Ġthis Ġsoftware Ġwithout Ġspecific Ġprior Ġwritten Ġpermission . Ċ Ġ* ĠĊ Ġ* ĠTHIS ĠSOFTWARE ĠIS ĠPROVIDED ĠBY ĠTHE ĠCOPYRIGHT ĠHOLDERS ĠAND ĠCONTRIBUTORS Ġ" AS ĠIS " ĠAND ĠANY ĠEXPRESS ĠOR ĠĊ Ġ* ĠIMPLIED ĠWARRANTIES , ĠINCLUDING , ĠBUT ĠNOT ĠLIMITED ĠTO , ĠTHE ĠIMPLIED ĠWARRANTIES ĠOF ĠMERCHANTABILITY ĠAND ĠĊ Ġ* ĠFITNESS ĠFOR ĠA ĠPARTICULAR ĠPURPOSE ĠARE ĠDISCLAIMED . ĠIN ĠNO ĠEVENT ĠSHALL ĠTHE ĠCOPYRIGHT ĠOWNER ĠOR ĠĊ Ġ* ĠCONTRIBUTORS ĠBE ĠLIABLE ĠFOR ĠANY ĠDIRECT , ĠINDIRECT , ĠINCIDENTAL , ĠSPECIAL , ĠEXEMPLARY , ĠOR ĠCONSEQUENTIAL ĠĊ Ġ* ĠDAMAGES Ġ( INCLUDING , ĠBUT ĠNOT ĠLIMITED ĠTO , ĠPROCUREMENT ĠOF ĠSUBSTITUTE ĠGOODS ĠOR ĠSERVICES ; ĠLOSS ĠOF ĠUSE , ĠĊ Ġ* ĠDATA , ĠOR ĠPROFITS ; ĠOR ĠBUSINESS ĠINTERRUPTION ) ĠHOWEVER ĠCAUSED ĠAND ĠON ĠANY ĠTHEORY ĠOF ĠLIABILITY , ĠWHETHER ĠĊ Ġ* ĠIN ĠCONTRACT , ĠSTRICT ĠLIABILITY , ĠOR ĠTORT Ġ( INCLUDING ĠNEGLIGENCE ĠOR ĠOTHERWISE ) ĠARISING ĠIN ĠANY ĠWAY ĠOUT ĠĊ Ġ* ĠOF ĠTHE ĠUSE ĠOF ĠTHIS ĠSOFTWARE , ĠEVEN ĠIF ĠADVISED ĠOF ĠTHE ĠPOSSIBILITY ĠOF ĠSUCH ĠDAMAGE . Ċ Ġ*/ Ċ package Ġorg . dyn 4 j Ċ Ċ import Ġkotlin . jvm . Jvm Field Ċ import Ġkotlin . math . max Ċ Ċ /** Ċ Ġ* ĠRepresents Ġan Ġ( option ally Ġbal anced ) ĠBinary ĠSearch ĠTree . Ċ Ġ* Ċ Ġ* Ċ Ġ* ĠNull Ġelements Ġare Ġnot Ġallowed Ġand Ġduplicates Ġcan Ġhave Ġunexpected Ġbehavior . ĠChanging Ġthe Ġvalue Ċ Ġ* Ġof Ġthe Ġelements Ġafter Ġbeing Ġinserted Ġinto Ġthe Ġtree Ġis Ġundefined . ĠIt 's Ġalso Ġundefined Ġbehavior Ċ Ġ* Ġif Ġthe Ġelements Ġare Ġnot Ġconsistent Ġwith Ġequals . Ċ Ġ* Ċ Ġ* Ċ Ġ* ĠUse Ġthe Ġ[. is Self Bal ancing ] Ġand Ġ[. set Self Bal ancing ] Ġmethods Ġto Ġenable Ċ Ġ* Ġor Ġdisable Ġself Ġbal ancing . ĠA Ġbal anced Ġtree Ġminim izes Ġthe Ġtree Ġdepth Ġand Ġimproves Ġsearch Ċ Ġ* Ġperformance . ĠWhen Ġself Ġbal ancing Ġis Ġenabled , Ġeach Ġinsert Ġor Ġremoval Ġre balances Ġthe Ġtree Ċ Ġ* Ġas Ġnecessary . Ċ Ġ* Ċ Ġ* Ċ Ġ* ĠThis Ġclass Ġcan Ġbe Ġused Ġin Ġconjunction Ġwith Ġthe Ġ[ Binary Search Tree Search Criteria ] Ġinterface Ċ Ġ* Ġto Ġperform Ġarbitrary Ġsearches Ġon Ġthe Ġtree . Ċ Ġ* Ġ@ author ĠW illiam ĠBit tle Ċ Ġ* Ġ@ version Ġ 3 . 2 . 3 Ċ Ġ* Ġ@ since Ġ 2 . 2 . 0 Ċ Ġ* Ġ@ param Ġ< E > ĠComparable Ċ </ E > Ġ*/ Ċ class ĠBinary Search Tree < E Ġ: ĠComparable < E >> Ġ: ĠIterable < E > Ġ{ ĊĊĠĠĠ Ġ/** ĠThe Ġroot Ġnode Ġof Ġthe Ġtree ; Ġnull Ġwhen Ġempty Ġ Ġ*/ ĊĠĠĠ Ġprivate Ġvar Ġ_ root : ĠBinary Search TreeNode < E >? Ġ= Ġnull ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġroot Ġof Ġthe Ġtree . ĊĠĠĠĠ Ġ* Ġ@ return ĠE Ġthe Ġroot Ġvalue ; Ġnull Ġif Ġthe Ġtree Ġis Ġempty ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġroot : ĠE ? Ġget () Ġ= Ġif Ġ(_ root Ġ== Ġnull ) Ġnull Ġelse Ġ_ root !!. comp arable ĊĊĠĠĠ Ġ/** ĠThe Ġcurrent Ġsize Ġof Ġthe Ġtree Ġ Ġ*/ ĊĠĠĠ Ġ@ Jvm Field ĊĠĠĠ Ġvar Ġsize Ġ= Ġ 0 ĊĊĠĠĠ Ġ/** ĠWhether Ġto Ġkeep Ġthe Ġtree Ġbal anced Ġor Ġnot Ġ Ġ*/ ĊĠĠĠ Ġvar Ġself Bal ancing : ĠBoolean ĊĠĠĠĠĠĠĠ Ġset ( value ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġflag Ġis Ġtrue Ġ( indic ating Ġthe Ġtree Ġshould Ġself Ġbalance ) Ġand ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġtree Ġis Ġnot Ġalready Ġself Ġbal ancing ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( value Ġ&& Ġ! field ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġelements Ġ( 0 , Ġ 1 , Ġor Ġ 2 Ġelement Ġtrees Ġdon 't Ġhave Ġto Ġbe Ġre - balanced ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( size Ġ> Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġtree Ġwas Ġnot Ġalready Ġself Ġbal ancing Ġand Ġthe Ġnew Ġflag Ġis Ġto Ġhave ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġtree Ġself Ġbalance Ġitself Ġwe Ġneed Ġto Ġrecreate Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . balance Tree () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġlocal Ġflag ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfield Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCreates Ġa Ġnew Ġbinary Ġsearch Ġtree Ġwith Ġautomatic Ġbal ancing Ġoff . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor () Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġself Bal ancing Ġ= Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCreates Ġa Ġnew Ġbinary Ġsearch Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġself Bal ancing Ġtrue Ġif Ġthe Ġtree Ġshould Ġautomatically Ġbalance ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor ( self Bal ancing : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġthis . self Bal ancing Ġ= Ġself Bal ancing ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCopy Ġconstructor . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġperforms Ġa Ġdeep Ġcopy Ġof Ġthe Ġelements Ġin Ġthe Ġtree . Ġ ĠThe Ġvalues Ġcontained ĊĠĠĠĠ Ġ* Ġin Ġthe Ġtree Ġare Ġshallow Ġcopied . ĊĠĠĠĠ Ġ* Ġ@ param Ġtree Ġthe Ġtree Ġto Ġcopy ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor ( tree : ĠBinary Search Tree < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġself Bal ancing Ġ= Ġtree . self Bal ancing ĊĠĠĠĠĠĠĠ Ġthis . insert Sub tree ( tree ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCopy Ġconstructor . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġperforms Ġa Ġdeep Ġcopy Ġof Ġthe Ġelements Ġin Ġthe Ġtree . Ġ ĠThe Ġvalues Ġcontained ĊĠĠĠĠ Ġ* Ġin Ġthe Ġtree Ġare Ġshallow Ġcopied . ĊĠĠĠĠ Ġ* Ġ@ param Ġtree Ġthe Ġtree Ġto Ġcopy ĊĠĠĠĠ Ġ* Ġ@ param Ġself Bal ancing Ġtrue Ġif Ġthe Ġtree Ġshould Ġself Ġbalance ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor ( tree : ĠBinary Search Tree < E > ?, Ġself Bal ancing : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠ Ġthis . self Bal ancing Ġ= Ġself Bal ancing ĊĠĠĠĠĠĠĠ Ġthis . insert Sub tree ( tree ) ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInser ts Ġthe Ġgiven Ġcomp arable Ġinto Ġthis Ġbinary Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠReturns Ġfalse Ġif Ġthe Ġgiven Ġcomp arable Ġis Ġnull . ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġobject Ġto Ġinsert ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġinsert Ġwas Ġsuccessful ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġinsert ( comp arable : ĠE ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( comp arable Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcreate Ġa Ġnode Ġfor Ġthis Ġobject ĊĠĠĠĠĠĠĠ Ġval Ġnode : ĠBinary Search TreeNode < E > Ġ= ĠBinary Search TreeNode ( comp arable ) ĊĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġwe Ġneed Ġto Ġfind Ġwhere Ġto Ġinsert Ġthis Ġnode ĊĠĠĠĠĠĠĠ Ġreturn Ġthis . insert ( node ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġcomp arable Ġobject Ġfrom Ġthe Ġtree Ġreturning Ġtrue ĊĠĠĠĠ Ġ* Ġif Ġthe Ġcomp arable Ġwas Ġfound Ġand Ġremoved ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠIf Ġthe Ġgiven Ġcomp arable Ġis Ġnull , Ġfalse Ġis Ġreturned . ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġobject ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġelement Ġwas Ġfound Ġand Ġremoved ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove ( comp arable : ĠE ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( comp arable Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġval Ġroot Ġ= Ġ_ root ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( root Ġ== Ġnull ) Ġfalse Ġelse Ġthis . remove ( root , Ġcomp arable ) Ġ!= Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġwe Ġneed Ġto Ġfind Ġand Ġremove Ġthe Ġnode ĊĠĠĠĠĠĠĠ Ġ// Ġret aining Ġany Ġchildren Ġof Ġthe Ġremoved Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġminimum Ġvalue Ġnode Ġfrom Ġthis Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠReturns Ġnull Ġif Ġthe Ġtree Ġis Ġempty . ĊĠĠĠĠ Ġ* Ġ@ return ĠE Ġthe Ġminimum Ġvalue ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove Minimum (): ĠE ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(_ root Ġ== Ġnull ) Ġnull Ġelse Ġthis . remove Minimum (_ root ) !!. comp arable ĊĠĠĠĠĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġminimum ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġmaximum Ġvalue Ġnode Ġfrom Ġthis Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠReturns Ġnull Ġif Ġthe Ġtree Ġis Ġempty . ĊĠĠĠĠ Ġ* Ġ@ return ĠE Ġthe Ġmaximum Ġvalue ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove Maximum (): ĠE ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(_ root Ġ== Ġnull ) Ġnull Ġelse Ġthis . remove Maximum (_ root ) !!. comp arable ĊĠĠĠĠĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġmaximum ĊĠĠĠ Ġ}// Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġminimum ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġminimum Ġvalue Ġof Ġthe Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠReturns Ġnull Ġif Ġthe Ġtree Ġis Ġempty . ĊĠĠĠĠ Ġ* Ġ@ return ĠE Ġthe Ġminimum Ġvalue ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġminimum : ĠE ? ĊĠĠĠĠĠĠĠ Ġget () Ġ= // Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġnull Ġelse Ġget Minimum (_ root ) !!. comp arable ĊĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġminimum Ċ // Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġmaximum ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġmaximum Ġvalue Ġof Ġthe Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠReturns Ġnull Ġif Ġthe Ġtree Ġis Ġempty . ĊĠĠĠĠ Ġ* Ġ@ return ĠE Ġthe Ġmaximum Ġvalue ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġmaximum : ĠE ? ĊĠĠĠĠĠĠĠ Ġget () Ġ= // Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġnull Ġelse Ġget Maximum (_ root ) !!. comp arable ĊĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġmaximum ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAt tempts Ġto Ġfind Ġthe Ġgiven Ġcomp arable Ġobject Ġwithin Ġthe Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġobject Ġto Ġfind ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġgiven Ġcomp arable Ġobject Ġwas Ġfound ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoperator Ġfun Ġcontains ( comp arable : ĠE ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull Ġcomp arable ĊĠĠĠĠĠĠĠ Ġif Ġ( comp arable Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(_ root Ġ== Ġnull ) Ġfalse Ġelse Ġthis . contains (_ root , Ġcomp arable ) Ġ!= Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġcomp arable ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġits Ġnot Ġfound Ġthen Ġnull Ġwill Ġbe Ġreturned ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠPerforms Ġa Ġbinary Ġsearch Ġon Ġthis Ġtree Ġgiven Ġthe Ġcriteria . ĊĠĠĠĠ Ġ* Ġ@ param Ġcriteria Ġthe Ġcriteria ĊĠĠĠĠ Ġ* Ġ@ param Ġ< T > Ġthe Ġ[ Binary Search Tree Search Criteria ] Ġtype ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġcriteria Ġfor Ġchaining ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 2 . 0 ĊĠĠĠ Ġ</ T > Ġ*/ ĊĠĠĠ Ġfun Ġ< T Ġ: ĠBinary Search Tree Search Criteria < E >> Ġsearch ( criteria : ĠT ): ĠT ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġa Ġnull Ġroot Ġnode ĊĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġreturn Ġcriteria ĊĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġcurrent Ġnode Ġto Ġthe Ġroot ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġ_ root ĊĠĠĠĠĠĠĠ Ġ// Ġloop Ġuntil Ġthe Ġcurrent Ġnode Ġis Ġnull ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġperform Ġthe Ġsearch Ġcriteria ĠĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġresult : ĠInt Ġ= Ġcriteria . evaluate ( node . comp arable ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġif Ġ( result Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( result Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcriteria ĊĠĠĠ Ġ} ĊĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠE mpt ies Ġthis Ġtree . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġjust Ġset Ġthe Ġroot Ġto Ġnull ĊĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġif Ġthis Ġtree Ġis Ġempty . ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġempty ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval ĠisEmpty : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġ_ root Ġ== Ġnull ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġmaximum Ġdepth Ġof Ġthe Ġtree . ĊĠĠĠĠ Ġ* Ġ@ return Ġint Ġthe Ġmaximum Ġdepth ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġheight : ĠInt ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġget Height (_ root ) ĊĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġin - order Ġ( ascending ) Ġiterator . ĊĠĠĠĠ Ġ* Ġ@ return ĠIterator & lt ; E & gt ; ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoverride Ġfun Ġiterator (): ĠIterator < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġin Order Iterator () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġin - order Ġ( ascending ) Ġiterator Ġstarting Ġfrom Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġfrom Ġthe Ġstarting Ġvalue ĊĠĠĠĠ Ġ* Ġ@ return ĠIterator & lt ; E & gt ; ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġtail Iterator ( from : ĠE ): ĠMutable Iterator < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠBinary Search Tree Iterator < E >(_ root , Ġfrom , Ġnull ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġin - order Ġ( ascending ) Ġiterator . ĊĠĠĠĠ Ġ* Ġ@ param Ġto Ġthe Ġending Ġvalue ĊĠĠĠĠ Ġ* Ġ@ return ĠIterator & lt ; E & gt ; ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġhead Iterator ( to : ĠE ): ĠMutable Iterator < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠBinary Search Tree Iterator < E >(_ root , Ġnull , Ġto ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġin - order Ġ( ascending ) Ġiterator . ĊĠĠĠĠ Ġ* Ġ@ param Ġfrom Ġthe Ġstarting Ġvalue ĊĠĠĠĠ Ġ* Ġ@ param Ġto Ġthe Ġending Ġvalue ĊĠĠĠĠ Ġ* Ġ@ return ĠIterator & lt ; E & gt ; ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsubset Iterator ( from : ĠE , Ġto : ĠE ): ĠMutable Iterator < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠBinary Search Tree Iterator < E >(_ root , Ġfrom , Ġto ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġnew Ġiterator Ġfor Ġtra ver sing Ġthe Ġtree Ġin Ġorder . ĊĠĠĠĠ Ġ* Ġ@ return ĠIterator & lt ; E & gt ; ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġin Order Iterator (): ĠMutable Iterator < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠBinary Search Tree Iterator < E >(_ root , Ġtrue ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġnew Ġiterator Ġfor Ġtra ver sing Ġthe Ġtree Ġin Ġreverse Ġorder . ĊĠĠĠĠ Ġ* Ġ@ return ĠIterator & lt ; E & gt ; ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġreverse Order Iterator (): ĠMutable Iterator < E ?> ? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠBinary Search Tree Iterator < E >(_ root , Ġfalse ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* Ġ( non - Javadoc ) Ċĉ Ġ* Ġ@ see Ġjava . lang . Object # toString () Ċĉ Ġ*/ ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsb : ĠStringBuilder Ġ= ĠStringBuilder () ĊĠĠĠĠĠĠĠ Ġval Ġiterator Ġ= Ġin Order Iterator () ĊĠĠĠĠĠĠĠ Ġsb . append (" Binary Search Tree [ ") ĊĠĠĠĠĠĠĠ Ġwhile Ġ( iterator . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ( iterator . next ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( iterator . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append (",") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġsb . append (" ]") ĊĠĠĠĠĠĠĠ Ġreturn Ġsb . toString () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġminimum Ġvalue Ġof Ġthe Ġsubtree Ġof Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnode Ġfound ; Ġnull Ġif Ġsubtree Ġis Ġempty ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġget Minimum ( node : ĠBinary Search TreeNode < E >? ): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġa Ġnull Ġnode ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode Ġ?: Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġloop Ġuntil Ġwe Ġfind Ġthe Ġminimum ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node !!. left Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcontinue Ġto Ġthe Ġleft Ġsince Ġthe Ġminimum Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwill Ġalways Ġbe Ġthe Ġleft Ġmost Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . left !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġminimum Ġwill Ġbe Ġlast Ġnode Ġtra versed ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġmaximum Ġvalue Ġof Ġthe Ġsubtree Ġof Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnode Ġfound ; Ġnull Ġif Ġsubtree Ġis Ġempty ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġget Maximum ( node : ĠBinary Search TreeNode < E >? ): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġa Ġnull Ġnode ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E > Ġ= Ġnode Ġ?: Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġloop Ġuntil Ġwe Ġfind Ġthe Ġmaximum ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcontinue Ġto Ġthe Ġright Ġsince Ġthe Ġmaximum Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwill Ġalways Ġbe Ġthe Ġright Ġmost Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . right !! ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġmaximum Ġwill Ġbe Ġlast Ġnode Ġtra versed ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġminimum Ġvalue Ġnode Ġfrom Ġthe Ġsubtree Ġof Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnode Ġremoved ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove Minimum ( node : ĠBinary Search TreeNode < E >? ): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġfind Ġthe Ġminimum ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġnode Ġ= Ġget Minimum ( node ) ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġgiven Ġsubtree Ġroot Ġnode Ġis Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġis Ġthe Ġminimum Ġthe Ġroot Ġnode ? ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpreserve Ġthe Ġright Ġsubtree Ġby Ġsetting Ġthe Ġnew Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġthe Ġtree Ġto Ġthe Ġroot Ġof Ġthe Ġright Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnode . right ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . parent !!. right Ġ=== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġthe Ġminimum Ġnode Ġis Ġthe Ġright Ġnode Ġof Ġits Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġoverwrite Ġthe Ġright Ġpointer Ġof Ġthe Ġparent Ġto Ġthe Ġminimum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode 's Ġright Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnode . right ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġthe Ġminimum Ġnode Ġis Ġthe Ġleft Ġnode Ġof Ġits Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġoverwrite Ġthe Ġleft Ġpointer Ġof Ġthe Ġparent Ġto Ġthe Ġminimum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode 's Ġright Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnode . right ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġdecrement Ġthe Ġsize Ġof Ġthe Ġtree ĊĠĠĠĠĠĠĠ Ġsize -- ĊĠĠĠĠĠĠĠ Ġ// Ġreturn Ġthe Ġminimum ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġmaximum Ġvalue Ġnode Ġfrom Ġthe Ġsubtree Ġof Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnode Ġremoved ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove Maximum ( node : ĠBinary Search TreeNode < E >? ): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġfind Ġthe Ġmaximum ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġnode Ġ= Ġget Maximum ( node ) ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġgiven Ġsubtree Ġroot Ġnode Ġis Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġis Ġthe Ġmaximum Ġthe Ġroot Ġnode ? ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpreserve Ġthe Ġleft Ġsubtree Ġby Ġsetting Ġthe Ġnew Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġthe Ġtree Ġto Ġthe Ġroot Ġof Ġthe Ġleft Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . parent !!. right Ġ=== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġthe Ġmaximum Ġnode Ġis Ġthe Ġright Ġnode Ġof Ġits Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġoverwrite Ġthe Ġright Ġpointer Ġof Ġthe Ġparent Ġto Ġthe Ġmaximum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode 's Ġleft Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġthe Ġmaximum Ġnode Ġis Ġthe Ġleft Ġnode Ġof Ġits Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġoverwrite Ġthe Ġleft Ġpointer Ġof Ġthe Ġparent Ġto Ġthe Ġmaximum ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode 's Ġleft Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġdecrement Ġthe Ġsize Ġof Ġthe Ġtree ĊĠĠĠĠĠĠĠ Ġsize -- ĊĠĠĠĠĠĠĠ Ġ// Ġreturn Ġthe Ġmaximum ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġmaximum Ġdepth Ġof Ġthe Ġsubtree Ġof Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġroot Ġnode Ġof Ġthe Ġsubtree ĊĠĠĠĠ Ġ* Ġ@ return Ġint Ġthe Ġmaximum Ġdepth ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġget Height ( node : ĠBinary Search TreeNode < E >? ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull Ġnode ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġthe Ġleaf Ġnode ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( node . left Ġ== Ġnull Ġ&& Ġnode . right Ġ== Ġnull ) Ġ 1 Ġelse Ġ 1 Ġ+ Ġmax ( getHeight ( node . left ), Ġget Height ( node . right )) ĊĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġrecurse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġnumber Ġof Ġelements Ġin Ġthe Ġsubtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġroot Ġnode Ġof Ġthe Ġsubtree ĊĠĠĠĠ Ġ* Ġ@ return Ġint ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsize ( node : ĠBinary Search TreeNode < E >? ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull Ġnode ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġthe Ġleaf Ġnode ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( node . left Ġ== Ġnull Ġ&& Ġnode . right Ġ== Ġnull ) Ġ 1 Ġelse Ġ 1 Ġ+ Ġthis . size ( node . left ) Ġ+ Ġthis . size ( node . right ) ĊĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġrecurse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġif Ġthe Ġgiven Ġnode Ġ( not Ġthe Ġnode 's Ġcomp arable ) Ġis Ġcontained Ġin Ġthis Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġperforms Ġa Ġreference Ġequals Ġcomparison Ġon Ġthe Ġnodes ĊĠĠĠĠ Ġ* Ġrather Ġthan Ġa Ġcomparison Ġon Ġthe Ġnode 's Ġcomp arable . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġnode Ġto Ġfind ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoperator Ġfun Ġcontains ( node : ĠBinary Search TreeNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġroot Ġnode ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ// Ġstart Ġat Ġthe Ġroot Ġnode ĊĠĠĠĠĠĠĠ Ġvar Ġcurr : ĠBinary Search TreeNode < E >? Ġ= Ġ_ root ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġsure Ġthe Ġnode Ġis Ġnot Ġnull ĊĠĠĠĠĠĠĠ Ġwhile Ġ( curr Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġreference Ġequality ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( curr Ġ=== Ġnode ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġpick Ġthe Ġdirection Ġto Ġsearch ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġby Ġcomparing Ġthe Ġdata Ġin Ġthe Ġnodes ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiff : ĠInt Ġ= Ġnode . compareTo ( curr ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġthe Ġdifference ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcurr Ġ= Ġif Ġ( diff Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġhave Ġfound Ġwhere Ġthe Ġitem Ġshould Ġbe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnow Ġcompare Ġby Ġreference ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcurr Ġ=== Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( diff Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġcomp arable Ġmust Ġbe Ġto Ġthe Ġleft Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsince Ġits Ġless Ġthan Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurr . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġcomp arable Ġmust Ġbe Ġto Ġthe Ġright Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsince Ġits Ġgreater Ġthan Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcurr . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġnode Ġwas Ġnot Ġfound ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġnode Ġthat Ġcontains Ġthe Ġgiven Ġvalue Ġor Ġnull Ġif Ġthe ĊĠĠĠĠ Ġ* Ġvalue Ġis Ġnot Ġfound . ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġvalue ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnode Ġcontaining Ġthe Ġgiven Ġvalue ; Ġnull Ġif Ġits Ġnot Ġfound ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġoperator Ġfun Ġget ( comp arable : ĠE ?): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull Ġcomp arable ĊĠĠĠĠĠĠĠ Ġif Ġ( comp arable Ġ== Ġnull ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(_ root Ġ== Ġnull ) Ġnull Ġelse Ġthis . contains (_ root , Ġcomp arable ) ĊĠĠĠĠĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġcomp arable ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInser ts Ġthe Ġgiven Ġsubtree Ġinto Ġthis Ġbinary Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġcopies Ġthe Ġelements Ġfrom Ġthe Ġgiven Ġsubtree . ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġinsertion Ġwas Ġsuccessful ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġinsert Sub tree ( node : ĠBinary Search TreeNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġget Ġan Ġiterator Ġto Ġgo Ġthrough Ġall Ġthe Ġnodes ĊĠĠĠĠĠĠĠ Ġval Ġiterator : ĠMutable Iterator < E ?> Ġ= ĠBinary Search Tree Iterator < E >( node ) ĊĠĠĠĠĠĠĠ Ġ// Ġiterate Ġover Ġthe Ġnodes ĊĠĠĠĠĠĠĠ Ġwhile Ġ( iterator . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcreate Ġa Ġcopy Ġof Ġthe Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewNode : ĠBinary Search TreeNode < E > Ġ= ĠBinary Search TreeNode < E >( iterator . next ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġinsert Ġthe Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . insert ( new Node ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġinserts Ġwere Ġsuccessful ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInser ts Ġthe Ġgiven Ġsubtree Ġinto Ġthis Ġbinary Ġtree . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġcopies Ġthe Ġelements Ġfrom Ġthe Ġgiven Ġtree . ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġinsertion Ġwas Ġsuccessful ĊĠĠĠĠ Ġ* Ġ@ param Ġtree Ġthe Ġsubtree ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprotected Ġfun Ġinsert Sub tree ( tree : ĠBinary Search Tree < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( tree Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġsource Ġtree ĊĠĠĠĠĠĠĠ Ġif Ġ( tree ._ root Ġ== Ġnull ) Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ// Ġget Ġan Ġiterator Ġto Ġgo Ġthrough Ġall Ġthe Ġnodes ĊĠĠĠĠĠĠĠ Ġval Ġiterator Ġ= Ġtree . in Order Iterator () ĊĠĠĠĠĠĠĠ Ġ// Ġiterate Ġover Ġthe Ġnodes ĊĠĠĠĠĠĠĠ Ġwhile Ġ( iterator !!. hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcreate Ġa Ġcopy Ġof Ġthe Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval ĠnewNode : ĠBinary Search TreeNode < E > Ġ= ĠBinary Search TreeNode < E >( iterator . next ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġinsert Ġthe Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . insert ( new Node ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġinserts Ġwere Ġsuccessful ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġnode Ġcontaining Ġthe Ġgiven Ġvalue Ġand Ġthe Ġcorresponding ĊĠĠĠĠ Ġ* Ġsubtree Ġfrom Ġthis Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġto Ġsearch Ġfor ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġelement Ġwas Ġfound Ġand Ġits Ġsubtree Ġwas Ġremoved ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprotected Ġfun Ġremove Sub tree ( comp arable : ĠE ?): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull Ġinput ĊĠĠĠĠĠĠĠ Ġif Ġ( comp arable Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġattempt Ġto Ġfind Ġthe Ġnode ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġ_ root ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcompare Ġthe Ġdata Ġto Ġthe Ġcurrent Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiff Ġ= Ġcomp arable . compareTo ( node . comp arable ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġthe Ġdifference ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( diff Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġgiven Ġcomp arable Ġis Ġless Ġthan Ġthe Ġcurrent ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġthen Ġgo Ġto Ġthe Ġleft Ġon Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( diff Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġgiven Ġcomp arable Ġis Ġgreater Ġthan Ġthe Ġcurrent ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġthen Ġgo Ġto Ġthe Ġright Ġon Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġfound Ġwhere Ġthe Ġvalue Ġshould Ġbe , Ġnow Ġcheck Ġfor Ġequality ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( node . comp arable . equals ( comp arable )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġfound Ġthe Ġnode , Ġnow Ġremove Ġit ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdecrement Ġthe Ġsize Ġby Ġthe Ġsize Ġof Ġthe Ġremoved Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize Ġ-= Ġthis . size ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġre - balance Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( self Bal ancing ) Ġthis . balance Tree ( node . parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreturn Ġsuccess ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwasn 't Ġfound ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġwe Ġget Ġhere Ġthe Ġnode Ġwas Ġnot Ġfound ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġgiven Ġnode Ġ( not Ġthe Ġnode 's Ġcomp arable ) Ġand Ġthe Ġcorresponding Ġsubtree Ġfrom Ġthis Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġnode Ġand Ġsubtree Ġto Ġremove ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġnode Ġwas Ġfound Ġand Ġremoved Ġsuccessfully ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove Sub tree ( node : ĠBinary Search TreeNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull Ġinput ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġroot Ġnode ĊĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ=== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġroot Ġnode Ġto Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsee Ġif Ġthe Ġtree Ġcontains Ġthe Ġgiven Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . contains ( node )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwhich Ġchild Ġis Ġthe Ġnode ? ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdecrement Ġthe Ġsize Ġby Ġthe Ġsize Ġof Ġthe Ġremoved Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsize Ġ-= Ġthis . size ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġre - balance Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( self Bal ancing ) Ġthis . balance Tree ( node . parent ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreturn Ġsuccess ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġif Ġwe Ġget Ġhere Ġthe Ġnode Ġwas Ġnot Ġfound ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInser ts Ġthe Ġgiven Ġnode Ġinto Ġthe Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġitem Ġthe Ġnew Ġnode Ġto Ġinsert ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean Ġtrue Ġif Ġthe Ġinsertion Ġwas Ġsuccessful ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġinsert ( item : ĠBinary Search TreeNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġan Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ(_ root Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġroot Ġto Ġthe Ġnew Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġincrement Ġthe Ġsize Ġot Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsize ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreturn Ġa Ġsuccess ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtrue ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġuse Ġthe Ġinternal Ġinsert Ġmethod ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . insert ( item , Ġ_ root ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInternal Ġinsertion Ġmethod . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġcannot Ġinsert Ġinto Ġthe Ġtree Ġif Ġthe Ġgiven Ġnode Ġparameter Ġis Ġnull . Ġ ĠUse Ġthe ĊĠĠĠĠ Ġ* Ġ[. insert ] Ġmethod Ġinstead Ġto Ġensure Ġthat Ġthe Ġnode Ġis Ġinserted . ĊĠĠĠĠ Ġ* Ġ@ param Ġitem Ġthe Ġnode Ġto Ġinsert ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode Ġto Ġstart Ġthe Ġsearch ĊĠĠĠĠ Ġ* Ġ@ return Ġtrue Ġif Ġthe Ġinsertion Ġwas Ġsuccessful ĊĠĠĠĠ Ġ* Ġ@ see Ġ. insert ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġinsert ( item : ĠBinary Search TreeNode < E > ?, Ġnode : ĠBinary Search TreeNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġsure Ġthe Ġgiven Ġnode Ġis Ġnot Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode Ġ?: Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġloop Ġuntil Ġwe Ġfind Ġwhere Ġthe Ġnode Ġshould Ġbe Ġplaced ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcompare Ġthe Ġitem Ġto Ġthe Ġcurrent Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( item !!. compareTo ( node ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġnew Ġitem Ġis Ġless Ġthan Ġthe Ġcurrent Ġitem , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthen Ġcheck Ġthe Ġleft Ġnode Ġof Ġthe Ġcurrent Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġits Ġnull Ġthen Ġwe Ġcan Ġgo Ġahead Ġand Ġadd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġitem Ġto Ġthe Ġtree Ġat Ġthis Ġlocation ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdon 't Ġforget Ġto Ġset Ġthe Ġparent Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġare Ġdone , Ġso Ġbreak Ġfrom Ġthe Ġloop ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġleft Ġnode Ġis Ġnot Ġnull Ġthen Ġwe Ġneed ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġto Ġcontinue Ġsearching Ġfor Ġa Ġplace Ġto ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġinsert Ġthe Ġnew Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġnew Ġitem Ġis Ġgreater Ġthan Ġ( or Ġequal ) Ġto ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġcurrent Ġitem , Ġthen Ġcheck Ġthe Ġright Ġnode ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġthe Ġcurrent Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . right Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġits Ġnull Ġthen Ġwe Ġcan Ġgo Ġahead Ġand Ġadd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġitem Ġto Ġthe Ġtree Ġat Ġthis Ġlocation ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Ġ= Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdon 't Ġforget Ġto Ġset Ġthe Ġparent Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġitem . parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġare Ġdone , Ġso Ġbreak Ġfrom Ġthe Ġloop ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġright Ġnode Ġis Ġnot Ġnull Ġthen Ġwe Ġneed ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġto Ġcontinue Ġsearching Ġfor Ġa Ġplace Ġto ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġinsert Ġthe Ġnew Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġincrement Ġthe Ġsize ĊĠĠĠĠĠĠĠ Ġsize ++ ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġsure Ġthe Ġtree Ġremains Ġbal anced ĊĠĠĠĠĠĠĠ Ġif Ġ( self Bal ancing ) Ġthis . balance Tree ( node ) ĊĠĠĠĠĠĠĠ Ġ// Ġreturn Ġsuccess ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRemoves Ġthe Ġgiven Ġnode Ġfrom Ġthis Ġtree Ġand Ġreturns ĊĠĠĠĠ Ġ* Ġtrue Ġif Ġthe Ġnode Ġ( not Ġthe Ġnode 's Ġcomp arable ) Ġexisted Ġand Ġwas Ġremoved . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġnode Ġto Ġremove ĊĠĠĠĠ Ġ* Ġ@ return Ġboolean ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove ( node : ĠBinary Search TreeNode < E >? ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġfor Ġempty Ġtree ĊĠĠĠĠĠĠĠ Ġif Ġ(_ root Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġsure Ġthis Ġnode Ġis Ġcontained Ġin Ġthe Ġtree ĊĠĠĠĠĠĠĠ Ġif Ġ( this . contains ( node )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġremove Ġthe Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġremove Node ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreturn Ġtrue Ġthat Ġthe Ġnode Ġwas Ġremoved ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġnode Ġremoved Ġif Ġthe Ġcomp arable Ġis Ġfound , Ġnull Ġotherwise . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġnode Ġto Ġstart Ġthe Ġsearch ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġobject Ġto Ġremove ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġnull Ġif Ġthe Ġgiven Ġcomp arable Ġwas Ġnot Ġfound ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove ( node : ĠBinary Search TreeNode < E > ?, Ġcomp arable : ĠE ?): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġperform Ġan Ġiter ative Ġversion Ġof Ġthe Ġremove Ġmethod Ġso Ġthat ĊĠĠĠĠĠĠĠ Ġ// Ġwe Ġcan Ġreturn Ġa Ġboolean Ġresult Ġabout Ġremoval ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġgiven Ġcomp arable Ġobject Ġis Ġless Ġthan Ġthe Ġcurrent ĠĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsubtree Ġroot Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiff Ġ= Ġcomp arable !!. compareTo ( node . comp arable ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġif Ġ( diff Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġits Ġless Ġthan , Ġwe Ġneed Ġto Ġcontinue Ġto Ġsearch Ġfor Ġthe Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġin Ġthe Ġleft Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( diff Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġits Ġgreater Ġthan , Ġwe Ġneed Ġto Ġcontinue Ġto Ġsearch Ġfor Ġthe Ġitem ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġin Ġthe Ġright Ġsubtree ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġwe Ġgot Ġhere Ġwe Ġknow Ġthat Ġwe Ġfound Ġwhere ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġcomp arable Ġwould Ġbe , Ġnow Ġcheck Ġequ all ity ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( node . comp arable . equals ( comp arable )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġremove Node ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreturn Ġthe Ġnode Ġremoved ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġif Ġwe Ġget Ġhere Ġwe Ġdidn 't Ġfind Ġthe Ġnode Ġin Ġthe Ġtree ĊĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInternal Ġmethod Ġto Ġremove Ġthe Ġgiven Ġnode Ġfrom Ġthe Ġtree Ġret aining ĊĠĠĠĠ Ġ* Ġall Ġthe Ġsubtree Ġnodes . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġassumes Ġthat Ġthe Ġnode Ġis Ġcontained Ġin Ġthis Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġnode Ġto Ġremove ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġremove Node ( node : ĠBinary Search TreeNode < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġis Left Child : ĠBoolean Ġ= Ġnode . is Left Child ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġhow Ġmany Ġchildren Ġit Ġhas ĊĠĠĠĠĠĠĠ Ġif Ġ( node . left Ġ!= Ġnull Ġ&& Ġnode . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfind Ġthe Ġminimum Ġnode Ġin Ġthe Ġright Ġsubtree Ġand ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġuse Ġit Ġas Ġa Ġreplacement Ġfor Ġthe Ġnode Ġwe Ġare Ġremoving ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmin Ġ= Ġget Minimum ( node . right ) !! ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġremove Ġthe Ġminimum Ġnode Ġfrom Ġthe Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( min Ġ!== Ġnode . right ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġminimum Ġnode 's Ġparent 's Ġleft Ġpointer Ġto ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġminimum Ġnode 's Ġright Ġpointer Ġ( this Ġremoves Ġthe Ġminimum ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġfrom Ġthe Ġtree Ġand Ġpre serves Ġthe Ġelements Ġto Ġthe Ġright ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġthe Ġminimum Ġnode ; Ġno Ġelements Ġshould Ġexist Ġto Ġthe Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġthe Ġminimum Ġnode Ġsince Ġthis Ġis Ġthe Ġminimum Ġfor Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsubtree ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin . parent !!. left Ġ= Ġmin . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġneed Ġto Ġchange Ġthe Ġparent Ġof Ġthe Ġright Ġsubtree Ġalso ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( min . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin . right !!. parent Ġ= Ġmin . parent ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġpreserve Ġthe Ġsubtree Ġto Ġthe Ġright Ġof Ġthe Ġnode Ġwe Ġplan Ġto ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġremove Ġby Ġsetting Ġthe Ġminimum Ġnode 's Ġright Ġpointer ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin . right Ġ= Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġchange Ġthe Ġnode 's Ġright Ġsubtree 's Ġparent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . right Ġ!= Ġnull ) Ġnode . right !!. parent Ġ= Ġmin ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Ġ!= Ġnull ) Ġnode . left !!. parent Ġ= Ġmin ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġnode Ġwe Ġare Ġremoving Ġis Ġthe Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġjust Ġset Ġthe Ġroot Ġpointer Ġto Ġthe Ġreplacement Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġmin ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġparent 's Ġleft Ġpointer Ġof Ġthe Ġnode Ġwe Ġplan Ġto Ġdelete ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġto Ġthe Ġreplacement Ġnode Ġ( the Ġminimum Ġnode Ġin Ġthe Ġright Ġsubtree ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġmin ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġparent 's Ġright Ġpointer Ġof Ġthe Ġnode Ġwe Ġplan Ġto Ġdelete ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġto Ġthe Ġreplacement Ġnode Ġ( the Ġminimum Ġnode Ġin Ġthe Ġright Ġsubtree ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġmin ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġleft Ġsubtree Ġof Ġthe Ġreplacement Ġnode Ġto Ġthe Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsubtree Ġof Ġthe Ġnode Ġwe Ġare Ġremoving ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmin . left Ġ= Ġnode . left ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġset Ġthe Ġparent Ġof Ġthe Ġreplacement Ġnode Ġto Ġthe Ġparent Ġof Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġwe Ġare Ġremoving ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmin . parent Ġ= Ġnode . parent ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfinally Ġmake Ġsure Ġthe Ġtree Ġremains Ġbal anced ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( self Bal ancing ) Ġthis . balance Tree ( min . parent ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . left Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġthe Ġright Ġnode Ġof Ġthe Ġnode Ġwe Ġwant Ġto Ġremove Ġis Ġnull ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġnode Ġwe Ġare Ġremoving Ġis Ġthe Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġjust Ġset Ġthe Ġroot Ġpointer Ġto Ġthe Ġleft Ġsubtree Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġnode Ġwe Ġare Ġtrying Ġto Ġremove Ġis Ġthe Ġleft Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġits Ġparent , Ġthen Ġset Ġthe Ġleft Ġnode Ġof Ġthe Ġparent Ġto Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġleft Ġsubtree Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġnode Ġwe Ġare Ġtrying Ġto Ġremove Ġis Ġthe Ġright Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġits Ġparent , Ġthen Ġset Ġthe Ġright Ġnode Ġof Ġthe Ġparent Ġto Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġleft Ġsubtree Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġneed Ġto Ġchange Ġthe Ġparent Ġof Ġthe Ġleft Ġsubtree Ġalso ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left !!. parent Ġ= Ġnode . parent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise Ġthe Ġleft Ġnode Ġof Ġthe Ġnode Ġwe Ġwant Ġto Ġremove Ġis Ġnull ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġnode Ġwe Ġare Ġremoving Ġis Ġthe Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġjust Ġset Ġthe Ġroot Ġpointer Ġto Ġthe Ġright Ġsubtree Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġnode Ġwe Ġare Ġtrying Ġto Ġremove Ġis Ġthe Ġleft Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġits Ġparent , Ġthen Ġset Ġthe Ġleft Ġnode Ġof Ġthe Ġparent Ġto Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġright Ġsubtree Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġthe Ġnode Ġwe Ġare Ġtrying Ġto Ġremove Ġis Ġthe Ġright Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġof Ġits Ġparent , Ġthen Ġset Ġthe Ġright Ġnode Ġof Ġthe Ġparent Ġto Ġthe ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġright Ġsubtree Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġneed Ġto Ġchange Ġthe Ġparent Ġof Ġthe Ġright Ġsubtree Ġalso ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right !!. parent Ġ= Ġnode . parent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġif Ġboth Ġare Ġnull Ġthen Ġwe Ġcan Ġjust Ġremove Ġthe Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthis Ġnode Ġis Ġthe Ġroot Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( node Ġ=== Ġ_ root ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. left Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent !!. right Ġ= Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġdecrement Ġthe Ġsize ĊĠĠĠĠĠĠĠ Ġsize -- ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInternal Ġiter ative Ġmethod Ġto Ġfind Ġan Ġitem Ġin Ġthe Ġtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġsubtree Ġroot Ġnode ĊĠĠĠĠ Ġ* Ġ@ param Ġcomp arable Ġthe Ġcomp arable Ġto Ġfind ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnode Ġfound ; Ġnull Ġif Ġnot Ġfound ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcontains ( node : ĠBinary Search TreeNode < E > ?, Ġcomp arable : ĠE ?): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġsure Ġthe Ġnode Ġis Ġnot Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcompare Ġthe Ġcomp arable ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode Data : ĠE Ġ= Ġnode . comp arable ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiff Ġ= Ġcomp arable !!. compareTo ( node Data ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġif Ġ( diff Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġfound Ġwhere Ġthe Ġitem Ġshould Ġbe Ġnow Ġwe Ġto Ġtest ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfor Ġequality ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( node . comp arable . equals ( comp arable )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( diff Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġcomp arable Ġmust Ġbe Ġto Ġthe Ġleft Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsince Ġits Ġless Ġthan Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġcomp arable Ġmust Ġbe Ġto Ġthe Ġright Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsince Ġits Ġgreater Ġthan Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġthe Ġnode Ġwas Ġnot Ġfound ĊĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRe - balances Ġthe Ġentire Ġtree . ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprotected Ġfun Ġbalance Tree () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġsave Ġthe Ġcurrent Ġtree ĊĠĠĠĠĠĠĠ Ġval Ġroot : ĠBinary Search TreeNode < E >? Ġ= Ġ_ root ĊĠĠĠĠĠĠĠ Ġval Ġbal ancing Ġ= Ġself Bal ancing ĊĠĠĠĠĠĠĠ Ġ// Ġempty Ġthe Ġtree ĊĠĠĠĠĠĠĠ Ġthis ._ root Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġsize Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġself Bal ancing Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġ// Ġcreate Ġan Ġiterator Ġfor Ġthe Ġold Ġtree ĊĠĠĠĠĠĠĠ Ġval Ġiterator : ĠMutable Iterator < E > Ġ= ĠBinary Search Tree Iterator < E >( root ) ĊĠĠĠĠĠĠĠ Ġ// Ġadd Ġall Ġthe Ġelements Ġfrom Ġthe Ġold Ġtree Ġinto Ġthe Ġnew Ġtree ĊĠĠĠĠĠĠĠ Ġwhile Ġ( iterator . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcreate Ġa Ġnew Ġnode Ġfor Ġeach Ġold Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnode : ĠBinary Search TreeNode < E > Ġ= ĠBinary Search TreeNode < E >( iterator . next ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġadd Ġthe Ġnew Ġnode Ġto Ġthis Ġtree ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis . insert ( node ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġself Bal ancing Ġ= Ġbal ancing ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠBal ances Ġthe Ġtree Ġiter atively Ġto Ġthe Ġroot Ġstarting Ġat Ġthe Ġgiven Ġnode . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġnode Ġto Ġbegin Ġbal ancing ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġbalance Tree ( node : ĠBinary Search TreeNode < E > ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġloop Ġuntil Ġwe Ġreach Ġthe Ġroot Ġnode ĊĠĠĠĠĠĠĠ Ġvar Ġnode : ĠBinary Search TreeNode < E >? Ġ= Ġnode ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbalance Ġthe Ġtree ; Ġthis Ġcan Ġreturn Ġa Ġnew Ġroot ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode Ġbecause Ġof Ġthe Ġrot ations Ġthat Ġhappen Ġtherefore ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġneed Ġto Ġupdate Ġthe Ġcurrent Ġnode Ġwe Ġare Ġon ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġbalance ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnext Ġbalance Ġthe Ġparent Ġof Ġthis Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode !!. parent ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠBal ances Ġthe Ġgiven Ġnode 's Ġsubtree . ĊĠĠĠĠ Ġ* Ġ@ param Ġnode Ġthe Ġroot Ġnode Ġof Ġthe Ġsubtree ĊĠĠĠĠ Ġ* Ġ@ return Ġ[ Binary Search TreeNode ] Ġthe Ġnew Ġroot ĊĠĠĠĠ Ġ* Ġ@ since Ġ 3 . 0 . 0 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġbalance ( node : ĠBinary Search TreeNode < E >? ): ĠBinary Search TreeNode < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġnode Ġis Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġif Ġthe Ġnode Ġhas Ġa Ġheight Ġof Ġ 2 Ġor Ġmore ĊĠĠĠĠĠĠĠ Ġif Ġ( getHeight ( node ) Ġ< Ġ 2 ) Ġreturn Ġnode ĊĊĠĠĠĠĠĠĠ Ġ// Ġget Ġthe Ġchild Ġnodes ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġnode . parent ĊĠĠĠĠĠĠĠ Ġval Ġa Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġnode . right ĊĠĠĠĠĠĠĠ Ġ// Ġget Ġthe Ġheight s Ġof Ġthe Ġchildren ĊĠĠĠĠĠĠĠ Ġval Ġah Ġ= Ġget Height ( a ) ĊĠĠĠĠĠĠĠ Ġval Ġbh Ġ= Ġget Height ( b ) ĊĠĠĠĠĠĠĠ Ġ// Ġcompute Ġthe Ġbalance ĊĠĠĠĠĠĠĠ Ġval Ġbalance Ġ= Ġah Ġ- Ġbh ĊĠĠĠĠĠĠĠ Ġ// Ġcheck Ġthe Ġbalance ĊĠĠĠĠĠĠĠ Ġif Ġ( balance Ġ> Ġ 1 ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĉĠĠĠ Ġnode Ġ Ġor ĠĠĠ Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġ/ ĠĠĠĠĠĠĠĠĠĠ Ġ/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠ Ġa ĠĠĠĠĠĠĠĠĠĠ Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠ Ġ/ ĠĠĠĠĠĠĠĠĠĠĠĠ Ġ\ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġc ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġach Ġ= Ġget Height ( a !!. right ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġget Ġthe Ġsubtree Ġinto Ġleft - left Ġcase ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ach Ġ> Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthe Ġsubtree Ġof Ġnode Ġis Ġleft - right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġchange Ġit Ġto Ġbe Ġleft - left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġc : ĠBinary Search TreeNode < E > Ġ= Ġa . right !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa . right Ġ= Ġc . left ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( c . left Ġ!= Ġnull ) Ġc . left !!. parent Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . left Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa . parent Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĉ ĉ node ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġ/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠ Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠ Ġ/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġc : ĠBinary Search TreeNode < E > Ġ= Ġnode . left !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left Ġ= Ġc . right ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( c . right Ġ!= Ġnull ) Ġc . right !!. parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc . right Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc . parent Ġ= Ġnode . parent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p . left Ġ=== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . left Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . right Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠ Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġ/ Ġ\ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġa ĠĠ Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġc ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( balance Ġ< Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode ĠĠ Ġor ĠĠĠ Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġ\ ĠĠĠĠĠĠĠĠĠĠĠ Ġ\ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠ Ġb ĠĠĠĠĠĠĠĠĠĠĠ Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠ Ġ\ ĠĠĠĠĠĠĠĠĠ Ġ/ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġd ĠĠĠĠĠĠĠ Ġd ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthen Ġthe Ġright Ġsubtree Ġneed Ġto Ġrotate ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb ch Ġ= Ġget Height ( b !!. left ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b ch Ġ> Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd : ĠBinary Search TreeNode < E > Ġ= Ġb . left !! ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb . left Ġ= Ġd . right ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d . right Ġ!= Ġnull ) Ġd . right !!. parent Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd . right Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb . parent Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd . parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġ\ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠ Ġd ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠ Ġ\ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠĠĠ Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd : ĠBinary Search TreeNode < E > Ġ= Ġnode . right !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Ġ= Ġd . left ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d . left Ġ!= Ġnull ) Ġd . left !!. parent Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd . left Ġ= Ġnode ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd . parent Ġ= Ġnode . parent ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . parent Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( p . left Ġ=== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . left Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . right Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ root Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠĠ Ġd ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠĠĠĠ Ġ/ Ġ\ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġnode ĠĠ Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġd ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnode ĊĠĠĠ Ġ} Ċ }