package Ġchapter 3 . section 2 Ċ Ċ import Ġchapter 1 . section 4 . factor ial Ċ import Ġchapter 2 . sleep Ċ import Ġedu . pr inc et on . cs . al gs 4 . Std Draw Ċ import Ġextensions . format Double Ċ Ċ /** Ċ Ġ* Ġ åĩĨ ç¡® çļĦ æ¦Ĥ çİĩ Ċ Ġ* Ġ è®¡ç®Ĺ çĶ¨ N ä¸ª éļıæľº çļĦ äºĴ ä¸į çĽ¸åĲĮ çļĦ éĶ® æŀĦéĢł åĩº ç»ĥ ä¹ł 3 . 2 . 9 ä¸Ń æ¯ı ä¸Ģ æ£ µ æłĳ çļĦ æ¦Ĥ çİĩ Ċ Ġ* Ċ Ġ* Ġ è§£ ï¼ļ åĪĽå»ºä¸Ģä¸ª æĸ° ç±» ï¼Į ç»§æī¿ Binary Search Tree ï¼Į å¹¶ å®ŀçİ° Comparable æİ¥åı£ ï¼Į Ċ Ġ* Ġä»¥ äºĮ åıī æŁ¥æī¾ æłĳ ä¸º key ï¼Į åĩºçİ° æ¬¡æķ° ä¸º value ï¼Į å°Ĩ 3 . 2 . 9 ä¸Ń æľª åİ» éĩį çļĦ åħ¨ éĩı äºĮ åıī æŁ¥æī¾ æłĳ åĪĹè¡¨ ä¾Ŀ æ¬¡ æıĴåħ¥ åı¦ ä¸Ģ é¢ Ĺ äºĮ åıī æŁ¥æī¾ æłĳ ä¸Ń ï¼Į Ċ Ġ* Ġ éģįåİĨ æīĢæľī äºĮ åıī æŁ¥æī¾ æłĳ ï¼Į æīĵåį° åĩº äºĮ åıī æŁ¥æī¾ æłĳ çļĦ åĽ¾ å½¢ ä»¥åıĬ æ¦Ĥ çİĩ Ċ Ġ*/ Ċ fun Ġex 2 6 _ Exact Prob abilities ( N : ĠInt , Ġdelay : ĠLong ) Ġ{ ĊĠĠĠ Ġval Ġall Binary Tree Ġ= Ġcreate All Comparable B ST ( N ) ĊĠĠĠ Ġval Ġb st Ġ= ĠBinary Search Tree < Comparable B ST < Int , ĠInt >, ĠInt >() ĊĠĠĠ Ġall Binary Tree . forEach Ġ{ Ġtree Ġ-> ĊĠĠĠĠĠĠĠ Ġval Ġcount Ġ= Ġb st . get ( tree ) ĊĠĠĠĠĠĠĠ Ġif Ġ( count Ġ== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb st . put ( tree , Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb st . put ( tree , Ġcount Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġtotal Ġ= Ġall Binary Tree . size ĊĠĠĠ Ġb st . keys (). forEach Ġ{ Ġtree Ġ-> ĊĠĠĠĠĠĠĠ Ġdraw B ST ( tree ) ĊĠĠĠĠĠĠĠ Ġval Ġcount Ġ= Ġb st . get ( tree ) Ġ?: Ġ 1 ĊĠĠĠĠĠĠĠ ĠStd Draw . text Left ( 0 . 0 2 , Ġ 0 . 9 8 , Ġ"${ count }/ $ total Ġ= Ġ${ format Double ( count . toDouble () Ġ/ Ġtotal Ġ* Ġ 1 0 0 , Ġ 2 )} % ") ĊĠĠĠĠĠĠĠ Ġsleep ( delay ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġcreate All Comparable B ST ( N : ĠInt ): ĠArray < Comparable B ST < Int , ĠInt >> Ġ{ ĊĠĠĠ Ġval Ġarray Ġ= ĠArray ( N ) Ġ{ Ġit Ġ+ Ġ 1 Ġ} ĊĠĠĠ Ġval Ġlist Ġ= ĠArrayList < Array < Int >>() ĊĠĠĠ Ġfull Array ( array , Ġ 0 , Ġlist ) ĊĠĠĠ Ġcheck ( list . size Ġ== Ġfactor ial ( N ). toInt ()) ĊĠĠĠ Ġreturn ĠArray ( list . size ) Ġ{ Ġindex Ġ-> ĊĠĠĠĠĠĠĠ ĠComparable B ST < Int , ĠInt >(). apply Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlist [ index ]. forEach Ġ{ Ġkey Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġput ( key , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* Ġåı¯ æ¯Ķè¾ĥ å¤§å°ı çļĦ äºĮ åıī æŁ¥æī¾ æłĳ Ċ Ġ*/ Ċ class ĠComparable B ST < K Ġ: ĠComparable < K >, ĠV Ġ: ĠAny > Ġ: ĠBinary Search Tree < K , ĠV >(), ĠComparable < Comparable B ST < K , ĠV >> Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġcompare To ( other : ĠComparable B ST < K , ĠV >): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġcompare ( this . root , Ġother . root ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcompare ( node 1 : ĠNode < K , ĠV > ?, Ġnode 2 : ĠNode < K , ĠV >? ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( node 1 Ġ== Ġnull Ġ&& Ġnode 2 Ġ== Ġnull ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġif Ġ( node 1 Ġ== Ġnull ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( node 2 Ġ== Ġnull ) Ġreturn Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġresult 1 Ġ= Ġnode 1 . key . compareTo ( node 2 . key ) ĊĠĠĠĠĠĠĠ Ġif Ġ( result 1 Ġ!= Ġ 0 ) Ġreturn Ġresult 1 ĊĠĠĠĠĠĠĠ Ġval Ġresult 2 Ġ= Ġcompare ( node 1 . left , Ġnode 2 . left ) ĊĠĠĠĠĠĠĠ Ġif Ġ( result 2 Ġ!= Ġ 0 ) Ġreturn Ġresult 2 ĊĠĠĠĠĠĠĠ Ġreturn Ġcompare ( node 1 . right , Ġnode 2 . right ) ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval ĠN Ġ= Ġ 5 ĊĠĠĠ Ġval Ġdelay Ġ= Ġ 1 0 0 0 L ĊĠĠĠ Ġex 2 6 _ Exact Prob abilities ( N , Ġdelay ) Ċ }