class ĠBinary Tree < T > Ġ: ĠI Mutable Set < T > Ġ{ ĊĠ Ġprivate Ġclass ĠTreeNode ( ĊĠĠĠ Ġvar Ġvalue Ġ: ĠT , Ġvar Ġparent Ġ: ĠTreeNode ĊĠ Ġ) Ġ{ ĊĠĠĠ Ġvar Ġleft Ġ: ĠTreeNode ĊĠĠĠ Ġvar Ġright Ġ: ĠTreeNode ĊĊĠ Ġ} ĊĊĠ Ġprivate Ġval Ġcompare Ġ: ĠMatch able Comparison < T > ĊĠ Ġprivate Ġvar Ġroot Ġ: ĠTreeNode ĊĠ Ġprivate Ġvar Ġversion Ġ= Ġ 0 Ċ Ċ // Ġ Ġoverride Ġvar Ġsize Ġ: ĠInt Ġ{ Ġget ; Ġprivate Ġset ; Ġ} ĊĊĠ Ġconstructor ( compare Ġ: ĠComparison < T >) Ġ{ ĊĠĠĠ Ġthis . compare Ġ= Ġas Match able Comparison ( comparison ) ĊĠ Ġ} ĊĊĠ Ġconstructor () Ġ: Ġthis ( natural Order < T >()) Ġ{ ĊĠ Ġ} ĊĊĠ Ġprivate Ġ[ operator ] Ġfun ĠT . compareTo ( other Ġ: ĠT ) Ġ: ĠInt Ġ= Ġcompare ( this , Ġother ) ĊĊĠ Ġoverride Ġfun Ġcontains ( item Ġ: ĠT ) Ġ: ĠBoolean Ġ{ ĊĠĠĠ Ġreturn Ġcontains ( root , Ġitem ) ĊĊĠĠĠ Ġfun Ġcontains ( node Ġ: ĠTreeNode , Ġitem Ġ: ĠT ) Ġ: ĠBoolean Ġ{ ĊĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠĠĠ Ġwhen ( compare ( item , Ġnode . value )) Ġ{ ĊĠĠĠĠĠĠĠ ĠE Q Ġ-> Ġtrue ĊĠĠĠĠĠĠĠ ĠLS Ġ-> Ġcontains ( node . left , Ġitem ) ĊĠĠĠĠĠĠĠ ĠGT Ġ-> Ġcontains ( node . right , Ġitem ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġoverride Ġfun Ġadd ( item Ġ: ĠT ) Ġ: ĠBoolean Ġ{ ĊĠĠĠ Ġif Ġ( add ( Ref ( root ), Ġnull )) Ġ{ ĊĠĠĠĠĠ Ġsize ++ ĊĠĠĠĠĠ Ġversion ++ ĊĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġfalse ĊĊĠĠĠ Ġ// ĠIn Ġprinciple , Ġthis Ġhas Ġaccess Ġto Ġitem Ġanyway , Ġbut Ġthen Ġit 's Ġunreachable Ġcode ĊĠĠĠ Ġ// ĠBAD : Ġthe Ġna ive Ġimplementation Ġof Ġref Ġwill Ġcreate ĠH ( T ) Ġref Ġobjects , Ġbut Ġcan Ġbe Ġoptimized Ġto Ġcreate Ġonly Ġone ĊĠĠĠ Ġfun Ġadd ( node Ġ: ĠRef < TreeNode ? >, Ġparent Ġ: ĠTreeNode ) Ġ: ĠBoolean Ġ{ ĊĠĠĠĠĠ Ġif Ġ( node . value Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġnode . value Ġ= ĠTreeNode ( item , Ġparent ) ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġwhen Ġ( compare ( item , Ġnode . value . value )) Ġ{ ĊĠĠĠĠĠĠĠ ĠE Q Ġ-> Ġfalse ĊĠĠĠĠĠĠĠ ĠLS Ġ-> Ġadd ( ref Ġnode . value . left , Ġnode ) ĊĠĠĠĠĠĠĠ ĠGT Ġ-> Ġadd ( ref Ġnode . value . right , Ġnode ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠIn Ġprinciple , Ġthis Ġhas Ġaccess Ġto Ġitem Ġanyway ĊĠĠĠ Ġfun Ġadd No Ref ( node Ġ: ĠTreeNode ) Ġ: ĠBoolean Ġ{ ĊĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġroot Ġ= ĠTreeNode ( item , Ġnull ) ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġwhen Ġ( compare ( item , Ġnode . value )) Ġ{ ĊĠĠĠĠĠĠĠ ĠE Q Ġ-> Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ ĠLS Ġ-> ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . left Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . left Ġ= ĠTreeNode ( item , Ġnode ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġreturn Ġadd ( node . left ) ĊĠĠĠĠĠĠĠ ĠGT Ġ-> ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( node . right Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode . right Ġ= ĠTreeNode ( item , Ġnode ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġreturn Ġadd ( node . right ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġoverride Ġfun Ġremove ( item Ġ: ĠT ) Ġ: ĠBoolean Ġ{ ĊĠĠĠ Ġval Ġto Remove Ġ= Ġfind ( root , Ġitem ) ĊĠĠĠ Ġif Ġ( to Remove Ġ== Ġnull ) Ġreturn Ġfalse ĊĠĠĠ Ġremove ( to Remove ) ĊĠĠĠ Ġsize -- ĊĠĠĠ Ġversion ++ ĊĠĠĠ Ġreturn Ġtrue ĊĊĠĠĠ Ġfun Ġfind ( node Ġ: ĠTreeNode ) Ġ: ĠTreeNode Ġ{ ĊĠĠĠĠĠ Ġif Ġ( node Ġ== Ġnull ) Ġreturn Ġnull ĊĠĠĠĠĠ Ġwhen Ġ( compare ( item , Ġnode . value )) Ġ{ ĊĠĠĠĠĠĠĠ ĠE Q Ġ-> Ġnode ĊĠĠĠĠĠĠĠ ĠLS Ġ-> Ġfind ( node . left ) ĊĠĠĠĠĠĠĠ ĠGT Ġ-> Ġfind ( node . right ) ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġprivate Ġfun Ġremove ( node Ġ: ĠTreeNode ) Ġ{ ĊĠĠĠ Ġwhen Ġ( node ) Ġ{ ĊĠĠĠĠĠ Ġ// is ĠTreeNode Ġ Ġ#( null , Ġnull ) Ġ-> Ġreplace ( node , Ġnull ) ĊĠĠĠĠĠ Ġ// is ĠTreeNode Ġ Ġ#( null , Ġright ) Ġ-> Ġreplace ( node , Ġright ) ĊĠĠĠĠĠ Ġ// is ĠTreeNode Ġ Ġ#( left , Ġnull ) Ġ-> Ġreplace ( node , Ġleft ) ĊĠĠĠĠĠ Ġ// is ĠTreeNode Ġ Ġ#( left , Ġright ) Ġ-> Ġ{ ĊĠĠĠĠĠ Ġ// Ġ Ġval Ġmin Ġ= Ġmin ( node . right ) ĊĠĠĠĠĠ Ġ// Ġ Ġnode . value Ġ= Ġmin . value ĊĠĠĠĠĠ Ġ// Ġ Ġremove ( min ) ĊĠĠĠĠĠ Ġ//} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġreplace ( node Ġ: ĠTreeNode , Ġreplace Ġ: ĠTreeNode ) Ġ{ ĊĠĠĠĠĠ Ġif Ġ( node Ġ== Ġroot ) Ġ{ ĊĠĠĠĠĠĠĠ Ġroot Ġ= Ġreplace ĊĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġif Ġ( node . parent . left Ġ== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġnode . parent . left Ġ= Ġreplace ĊĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( node . parent . right Ġ== Ġnode ) Ġ{ ĊĠĠĠĠĠĠĠ Ġnode . parent . right Ġ= Ġreplace ĊĠĠĠĠĠ Ġ} Ġelse ĠAssert ( false ) ĊĠĠĠ Ġ} ĊĠ Ġ} ĊĊĠ Ġ// ĠRel ies Ġon Ġtail - recursion Ġoptimization ĊĠ Ġprivate Ġfun Ġmin ( node Ġ: ĠTreeNode ) Ġ{ ĊĠĠĠ Ġif Ġ( node . left Ġ== Ġnull ) Ġnode Ġelse Ġmin ( node . left ) ĊĠ Ġ} ĊĊĠ Ġoverride Ġfun Ġiterator () Ġ: ĠI Iterator < T > Ġ= Ġmutable Iterator () ĊĊĠ Ġoverride Ġfun Ġmutable Iterator () Ġ: ĠI Mutable Iterator < T > Ġ= Ġobject Ġ: ĠI Mutable Iterator Ġ{ ĊĠĠĠ Ġval Ġversion Ġ= ĠBinary Tree . this . version ĊĠĠĠ Ġval Ġdown Ġ= ĠStack < TreeNode >() ĊĠĠĠ Ġval Ġup Ġ= ĠStack < TreeNode >() ĊĠĠĠ Ġvar Ġlast Node Ġ: ĠTreeNode ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠ Ġif Ġ( root Ġ!= Ġnull ) ĊĠĠĠĠĠĠĠ Ġdown . push ( root ) ĠĠĠĠĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġnext () Ġ: ĠT Ġ{ ĊĠĠĠĠĠ Ġif Ġ(! hasNext ) ĊĠĠĠĠĠĠĠ Ġthrow ĠNo More Elements Exception () ĊĠĠĠĠĠ Ġcheck Version () ĊĊĠĠĠĠĠ Ġlast Node Ġ= Ġnext Node () ĊĠĠĠĠĠ Ġreturn Ġlast Node . value ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġnext Node () Ġ: ĠTreeNode Ġ{ ĊĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ(! down . isEmpty ) Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġval Ġcur Node Ġ= Ġdown . pop () ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Node . left Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġup . push ( cur Node ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdown . push ( cur Node . left ) ĊĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Node . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdown . push ( cur Node . right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcur Node ; ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠ Ġval Ġcur Node Ġ= Ġup . pop () ĊĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur Node . right Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdown . push ( cur Node . right ) ĊĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠ Ġreturn Ġcur Node ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġval Ġhas Next Ġ: ĠBoolean ĊĠĠĠĠĠ Ġget () Ġ= Ġ! down . isEmpty Ġ|| Ġ! up . isEmpty ĊĊĊĠĠĠ Ġoverride Ġfun Ġremove () Ġ{ ĊĠĠĠĠĠ Ġcheck Version () ĊĠĠĠĠĠ Ġif Ġ( last Node Ġ== Ġnull ) ĊĠĠĠĠĠĠĠ Ġthrow ĠIteration Exception (" Nothing Ġto Ġremove ") ĊĠĠĠĠĠ Ġremove ( last Node ) ĊĠĠĠĠĠ Ġversion ++ ĊĠĠĠĠĠ ĠBinary Tree . this . version Ġ= Ġversion ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcheck Version () Ġ{ ĊĠĠĠĠĠ Ġif Ġ( version Ġ!= ĠBinary Tree . this . version ) Ġ{ ĊĠĠĠĠĠĠĠ Ġthrow ĠConcurrent Modification Exception () ĊĠĠĠĠĠ Ġ} ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĊĠĠĠ Ġ} ĊĠ Ġ} Ċ Ċ }