package Ġcom . xr pn . immutable Ċ Ċ import Ġcom . xr pn . im api . IM B Tree Ċ import Ġcom . xr pn . im api . Sym KeyType Ċ import Ġcom . xr pn . immutable . TK V Entry . Companion . to KK Entry Ċ import Ġio . kot est . assertions . fail Ċ import Ġio . kot est . matchers . shouldBe Ċ import Ġkotlin . reflect . K Class Ċ Ċ internal Ġval Ġempty ArrayOf Int : ĠArray < Int > Ġ= ĠarrayOf () Ċ internal Ġval Ġempty ArrayOf Str : ĠArray < String > Ġ= ĠarrayOf () Ċ internal Ġval Ġempty ArrayOf Long : ĠArray < Long > Ġ= ĠarrayOf () Ċ internal Ġval Ġempty ArrayOf Co PA : ĠArray < Co Pa < Int , String >> Ġ= ĠarrayOf () Ċ Ċ internal Ġval Ġa Entry Ġ= ĠT KV Entry . of kv (" A ". hashCode (), Ġ" A ") Ċ internal Ġval Ġb Entry Ġ= ĠT KV Entry . of kv (" B ". hashCode (), Ġ" B ") Ċ internal Ġval Ġc Entry Ġ= ĠT KV Entry . of kv (" C ". hashCode (), Ġ" C ") Ċ internal Ġval Ġd Entry Ġ= ĠT KV Entry . of kv (" D ". hashCode (), Ġ" D ") Ċ internal Ġval Ġe Entry Ġ= ĠT KV Entry . of kv (" E ". hashCode (), Ġ" E ") Ċ internal Ġval Ġf Entry Ġ= ĠT KV Entry . of kv (" F ". hashCode (), Ġ" F ") Ċ internal Ġval Ġg Entry Ġ= ĠT KV Entry . of kv (" G ". hashCode (), Ġ" G ") Ċ internal Ġval Ġh Entry Ġ= ĠT KV Entry . of kv (" H ". hashCode (), Ġ" H ") Ċ internal Ġval Ġi Entry Ġ= ĠT KV Entry . of kv (" I ". hashCode (), Ġ" I ") Ċ internal Ġval Ġj Entry Ġ= ĠT KV Entry . of kv (" J ". hashCode (), Ġ" J ") Ċ internal Ġval Ġk Entry Ġ= ĠT KV Entry . of kv (" K ". hashCode (), Ġ" K ") Ċ internal Ġval Ġl Entry Ġ= ĠT KV Entry . of kv (" L ". hashCode (), Ġ" L ") Ċ internal Ġval Ġm Entry Ġ= ĠT KV Entry . of kv (" M ". hashCode (), Ġ" M ") Ċ internal Ġval Ġn Entry Ġ= ĠT KV Entry . of kv (" N ". hashCode (), Ġ" N ") Ċ internal Ġval Ġo Entry Ġ= ĠT KV Entry . of kv (" O ". hashCode (), Ġ" O ") Ċ internal Ġval Ġp Entry Ġ= ĠT KV Entry . of kv (" P ". hashCode (), Ġ" P ") Ċ internal Ġval Ġr Entry Ġ= ĠT KV Entry . of kv (" R ". hashCode (), Ġ" R ") Ċ internal Ġval Ġs Entry Ġ= ĠT KV Entry . of kv (" S ". hashCode (), Ġ" S ") Ċ internal Ġval Ġu Entry Ġ= ĠT KV Entry . of kv (" U ". hashCode (), Ġ" U ") Ċ internal Ġval Ġz Entry Ġ= ĠT KV Entry . of kv (" Z ". hashCode (), Ġ" Z ") Ċ internal Ġval Ġn 4 4 Entry Ġ= ĠT KV Entry . of kv ( 4 4 , Ġ 4 4 ) Ċ internal Ġval Ġn 1 7 Entry Ġ= ĠT KV Entry . of kv ( 1 7 , Ġ 1 7 ) Ċ internal Ġval Ġn 3 2 Entry Ġ= ĠT KV Entry . of kv ( 3 2 , Ġ 3 2 ) Ċ internal Ġval Ġn 7 8 Entry Ġ= ĠT KV Entry . of kv ( 7 8 , Ġ 7 8 ) Ċ internal Ġval Ġn 5 0 Entry Ġ= ĠT KV Entry . of kv ( 5 0 , Ġ 5 0 ) Ċ internal Ġval Ġn 4 8 Entry Ġ= ĠT KV Entry . of kv ( 4 8 , Ġ 4 8 ) Ċ internal Ġval Ġn 6 2 Entry Ġ= ĠT KV Entry . of kv ( 6 2 , Ġ 6 2 ) Ċ internal Ġval Ġn 8 8 Entry Ġ= ĠT KV Entry . of kv ( 8 8 , Ġ 8 8 ) Ċ Ċ internal Ġval Ġf rb Wiki In order Ġ= ĠF List . of ( a Entry , Ġb Entry , Ġc Entry , Ġd Entry , Ġe Entry , Ġf Entry , Ġg Entry , Ġh Entry , Ġi Entry ) Ċ internal Ġval Ġf rb Wiki B read th First Ġ= ĠF List . of ( d Entry , Ġb Entry , Ġh Entry , Ġa Entry , Ġc Entry , Ġf Entry , Ġi Entry , Ġe Entry , Ġg Entry ) Ċ internal Ġval Ġf rb Wiki Tree : ĠF RB Tree < Int , ĠString > Ġ= ĠF RB Tree . Companion . rb t Inser ts ( FR BT Nil , Ġf rb Wiki In order ) Ċ internal Ġvar Ġrb Wiki Tree Ġ= ĠRB Tree . of ( fr b Wiki In order ) Ċ internal Ġval Ġf rb Wiki Pre order Ġ= Ġf rb Wiki Tree . pre order () Ċ internal Ġval Ġf rb Wiki Post order Ġ= Ġf rb Wiki Tree . post order () Ċ Ċ internal Ġval Ġf rb Slide Share In order Ġ= ĠF List . of ( n 1 7 Entry , n 3 2 Entry , n 4 4 Entry , n 4 8 Entry , n 5 0 Entry , n 6 2 Entry , n 7 8 Entry , n 8 8 Entry ) Ċ internal Ġval Ġf rb Slide Share B read th First Ġ= ĠF List . of ( n 4 8 Entry , n 3 2 Entry , n 6 2 Entry , n 1 7 Entry , n 4 4 Entry , n 5 0 Entry , n 8 8 Entry , n 7 8 Entry ) Ċ internal Ġval Ġf rb Slide Share Tree : ĠF RB Tree < Int , ĠInt > Ġ= ĠF RB Tree . Companion . rb t Inser ts ( FR BT Nil , Ġf rb Slide Share In order ) Ċ internal Ġvar Ġrb Slide Share Tree Ġ= ĠRB Tree . of ( fr b Slide Share In order ) Ċ internal Ġval Ġf rb Slide Share Pre order Ġ= Ġf rb Slide Share Tree . pre order () Ċ internal Ġval Ġf rb Slide Share Post order : ĠF List < TK V Entry < Int , ĠInt >> Ġ= Ġf rb Slide Share Tree . post order () Ċ Ċ val Ġreverse Int Compare : ĠComparator < Int > Ġ= ĠComparator Ġ{ Ġp 0 , Ġp 1 Ġ-> ĊĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠ Ġp 0 !! Ġ== Ġp 1 !! Ġ-> Ġ 0 ĊĠĠĠĠĠĠĠ Ġp 0 Ġ< Ġp 1 Ġ-> Ġ 1 ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ- 1 ĊĠĠĠ Ġ} Ċ } Ċ Ċ val Ġint Compare : ĠComparator < Int > Ġ= ĠComparator Ġ{ Ġp 0 , Ġp 1 Ġ-> ĊĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠ Ġp 0 !! Ġ== Ġp 1 !! Ġ-> Ġ 0 ĊĠĠĠĠĠĠĠ Ġp 0 Ġ< Ġp 1 Ġ-> Ġ 1 ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ- 1 ĊĠĠĠ Ġ} Ċ } Ċ Ċ val Ġreverse Str Compare : ĠComparator < String > Ġ= ĠComparator Ġ{ Ġp 0 , Ġp 1 Ġ-> ĊĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠ Ġp 0 !! Ġ== Ġp 1 !! Ġ-> Ġ 0 ĊĠĠĠĠĠĠĠ Ġp 0 Ġ< Ġp 1 Ġ-> Ġ 1 ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ- 1 ĊĠĠĠ Ġ} Ċ } Ċ Ċ val Ġtt Depth One Right : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Nil , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( n Entry , ĠF RB Tree . BLACK )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ Ċ val Ġf rb Depth One Left : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( l Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Nil ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ Ċ val Ġf rb Depth One Full : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( l Entry , ĠF RB Tree . BLACK )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( n Entry , ĠF RB Tree . BLACK )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ Ċ internal Ġval Ġf rb Depth One Full Pre order Ġ= ĠF List . of ( m Entry , l Entry , n Entry ) Ċ internal Ġval Ġf rb Depth One Full In order Ġ= ĠF List . of ( l Entry , m Entry , n Entry ) Ċ internal Ġval Ġf rb Depth One Full Post order Ġ= ĠF List . of ( l Entry , n Entry , m Entry ) Ċ internal Ġval Ġf rb Depth One Full B read th First Ġ= ĠF List . of ( m Entry , l Entry , n Entry ) Ċ Ċ val Ġtt Depth Two Left Partial : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( l Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( s Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ val Ġtt Depth Two Left Right : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġl Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Nil , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( m Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( s Entry , ĠF RB Tree . BLACK )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġtt Depth Two Left Right Pre order Ġ= ĠF List . of ( n Entry , l Entry , m Entry , s Entry ) Ċ internal Ġval Ġtt Depth Two Left Right In order Ġ= ĠF List . of ( l Entry , m Entry , n Entry , s Entry ) Ċ internal Ġval Ġtt Depth Two Left Right Post order Ġ= ĠF List . of ( m Entry , l Entry , s Entry , n Entry ) Ċ internal Ġval Ġtt Depth Two Left Right B read th First Ġ= ĠF List . of ( n Entry , l Entry , s Entry , m Entry ) Ċ Ċ val Ġf rb Depth Two Left Left : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġl Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( e Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Nil ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( s Entry , ĠF RB Tree . BLACK )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġf rb Depth Two Left Left Pre order Ġ= ĠF List . of ( n Entry , l Entry , e Entry , s Entry ) Ċ internal Ġval Ġf rb Depth Two Left Left In order Ġ= ĠF List . of ( e Entry , l Entry , n Entry , s Entry ) Ċ internal Ġval Ġf rb Depth Two Left Left Post order Ġ= ĠF List . of ( e Entry , l Entry , s Entry , n Entry ) Ċ internal Ġval Ġf rb Depth Two Left Left B read th First Ġ= ĠF List . of ( n Entry , l Entry , s Entry , e Entry ) Ċ Ċ val Ġtt Depth Two Right Partial : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( m Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( s Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ val Ġf rb Depth Two Right Right : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( m Entry , ĠF RB Tree . BLACK )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Nil , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( u Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġf rb Depth Two Right Right Pre order Ġ= ĠF List . of ( n Entry , m Entry , s Entry , u Entry ) Ċ internal Ġval Ġf rb Depth Two Right Right In order Ġ= ĠF List . of ( m Entry , n Entry , s Entry , u Entry ) Ċ internal Ġval Ġf rb Depth Two Right Right Post order Ġ= ĠF List . of ( m Entry , u Entry , s Entry , n Entry ) Ċ internal Ġval Ġf rb Depth Two Right Right B read th First Ġ= ĠF List . of ( n Entry , m Entry , s Entry , u Entry ) Ċ Ċ val Ġf rb Depth Two Right Left : ĠF RB Tree < Int , ĠString > Ġ= ĊĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( m Entry , ĠF RB Tree . BLACK )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Node . of ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Entry , ĠF RB Tree . BLACK , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠF RB Tree . fr bt Part Assert ( FR BT Node . of ( r Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFR BT Nil ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġf rb Depth Two Right Left Pre order Ġ= ĠF List . of ( n Entry , m Entry , s Entry , r Entry ) Ċ internal Ġval Ġf rb Depth Two Right Left In order Ġ= ĠF List . of ( m Entry , n Entry , r Entry , s Entry ) Ċ internal Ġval Ġf rb Depth Two Right Left Post order Ġ= ĠF List . of ( m Entry , r Entry , s Entry , n Entry ) Ċ internal Ġval Ġf rb Depth Two Right Left B read th First Ġ= ĠF List . of ( n Entry , m Entry , s Entry , r Entry ) Ċ Ċ // Ġ================================= ===== Ċ Ċ // Ġhttps :// en . wikipedia . org / wiki / Tree _ traversal Ċ val Ġwiki Tree : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġf Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , a Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , c Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , e Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , h Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ val Ġwiki Tree L oose : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠ Ġf Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġa Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġc Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġe Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Generic . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġh Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Generic . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġwiki Pre order Ġ= ĠF List . of ( f Entry , b Entry , a Entry , d Entry , c Entry , e Entry , g Entry , i Entry , h Entry ) Ċ internal Ġval Ġwiki In order Ġ= ĠF List . of ( a Entry , b Entry , c Entry , d Entry , e Entry , f Entry , g Entry , h Entry , i Entry ) Ċ internal Ġval Ġwiki Post order Ġ= ĠF List . of ( Ġa Entry , c Entry , e Entry , d Entry , b Entry , h Entry , i Entry , g Entry , f Entry ) Ċ Ċ // Ġhttps :// www . slide share . net / ER P unit J ain / binary - search - tree - 4 7 2 n 8 8 Entry 6 1 2 Ċ val Ġslide Share Tree : ĠFB ST ree < Int , ĠInt > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn 4 4 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn 1 7 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , n 3 2 Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn 7 8 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn 5 0 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , n 4 8 Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , n 6 2 Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , n 8 8 Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ val Ġslide Share Tree L oose : ĠFB ST ree < Int , ĠInt > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠ Ġn 4 4 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn 1 7 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Generic . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġn 3 2 Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn 7 8 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( true , ĠĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn 5 0 Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġn 4 8 Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġn 6 2 Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( true , Ġn 8 8 Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġslide Share Pre order Ġ= ĠF List . of ( n 4 4 Entry , n 1 7 Entry , n 3 2 Entry , n 7 8 Entry , n 5 0 Entry , n 4 8 Entry , n 6 2 Entry , n 8 8 Entry ) Ċ internal Ġval Ġslide Share In order Ġ= ĠF List . of ( n 1 7 Entry , n 3 2 Entry , n 4 4 Entry , n 4 8 Entry , n 5 0 Entry , n 6 2 Entry , n 7 8 Entry , n 8 8 Entry ) Ċ internal Ġval Ġslide Share Post order Ġ= ĠF List . of ( n 3 2 Entry , n 1 7 Entry , n 4 8 Entry , n 6 2 Entry , n 5 0 Entry , n 8 8 Entry , n 7 8 Entry , n 4 4 Entry ) Ċ internal Ġval Ġslide Share B read th First Ġ= ĠF List . of ( n 4 4 Entry , n 1 7 Entry , n 7 8 Entry , n 3 2 Entry , n 5 0 Entry , n 8 8 Entry , n 4 8 Entry , n 6 2 Entry ) Ċ Ċ val Ġdepth One Right : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , n Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ Ċ val Ġdepth One Left : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , l Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ Ċ val Ġdepth One Full : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , l Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , n Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġdepth One Full Pre order Ġ= ĠF List . of ( m Entry , l Entry , n Entry ) Ċ internal Ġval Ġdepth One Full In order Ġ= ĠF List . of ( l Entry , m Entry , n Entry ) Ċ internal Ġval Ġdepth One Full Post order Ġ= ĠF List . of ( l Entry , n Entry , m Entry ) Ċ internal Ġval Ġdepth One Full B read th First Ġ= ĠF List . of ( m Entry , l Entry , n Entry ) Ċ Ċ val Ġdepth Two Left Partial : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , l Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , s Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ val Ġdepth Two Left Right : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġl Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , m Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , s Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġdepth Two Left Right Pre order Ġ= ĠF List . of ( n Entry , l Entry , m Entry , s Entry ) Ċ internal Ġval Ġdepth Two Left Right In order Ġ= ĠF List . of ( l Entry , m Entry , n Entry , s Entry ) Ċ internal Ġval Ġdepth Two Left Right Post order Ġ= ĠF List . of ( m Entry , l Entry , s Entry , n Entry ) Ċ internal Ġval Ġdepth Two Left Right B read th First Ġ= ĠF List . of ( n Entry , l Entry , s Entry , m Entry ) Ċ Ċ val Ġdepth Two Left Left : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġl Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , e Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , s Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġdepth Two Left Left Pre order Ġ= ĠF List . of ( n Entry , l Entry , e Entry , s Entry ) Ċ internal Ġval Ġdepth Two Left Left In order Ġ= ĠF List . of ( e Entry , l Entry , n Entry , s Entry ) Ċ internal Ġval Ġdepth Two Left Left Post order Ġ= ĠF List . of ( e Entry , l Entry , s Entry , n Entry ) Ċ internal Ġval Ġdepth Two Left Left B read th First Ġ= ĠF List . of ( n Entry , l Entry , s Entry , e Entry ) Ċ Ċ val Ġdepth Two Right Partial : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , m Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , s Entry )) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ val Ġdepth Two Right Right : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , m Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , u Entry )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġdepth Two Right Right Pre order Ġ= ĠF List . of ( n Entry , m Entry , s Entry , u Entry ) Ċ internal Ġval Ġdepth Two Right Right In order Ġ= ĠF List . of ( m Entry , n Entry , s Entry , u Entry ) Ċ internal Ġval Ġdepth Two Right Right Post order Ġ= ĠF List . of ( m Entry , u Entry , s Entry , n Entry ) Ċ internal Ġval Ġdepth Two Right Right B read th First Ġ= ĠF List . of ( n Entry , m Entry , s Entry , u Entry ) Ċ Ċ val Ġdepth Two Right Left : ĠFB ST ree < Int , ĠString > Ġ= ĊĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn Entry , ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , m Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Node . of ( false , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Entry , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST ree . fb t Assert Node Invariant ( FB ST Node . of ( false , r Entry )), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠFB ST Unique . empty ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠ Ġ) Ċ internal Ġval Ġdepth Two Right Left Pre order Ġ= ĠF List . of ( n Entry , m Entry , s Entry , r Entry ) Ċ internal Ġval Ġdepth Two Right Left In order Ġ= ĠF List . of ( m Entry , n Entry , r Entry , s Entry ) Ċ internal Ġval Ġdepth Two Right Left Post order Ġ= ĠF List . of ( m Entry , r Entry , s Entry , n Entry ) Ċ internal Ġval Ġdepth Two Right Left B read th First Ġ= ĠF List . of ( n Entry , m Entry , s Entry , r Entry ) Ċ Ċ internal Ġdata Ġclass ĠCo Pa < A , ĠB >( val Ġp : ĠPair < A , ĠB >): ĠComparable < Co Pa < A , B >> Ġwhere ĠA : ĠAny , ĠA : ĠComparable < A > Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġcompare To ( other : ĠCo Pa < A , ĠB >): ĠInt Ġ= Ġp . first . compareTo ( other . p . first ) Ċ } Ċ Ċ internal Ġval Ġcop a 1 : ĠCo Pa < Int , ĠString > Ġ= ĠCo Pa (( 1 Ġto Ġ" 1 ")) Ċ internal Ġval Ġcop a IS : ĠK Class < out ĠCo Pa < Int , ĠString >> Ġ= Ġcop a 1 :: class Ċ internal Ġval Ġcop a Key : ĠSym KeyType < Co Pa < Int , ĠString >> Ġ= ĠSym KeyType ( co pa IS ) Ċ Ċ internal Ġval Ġcop a 2 Ġ= ĠCo Pa (( 2 Ġto Ġ" 1 1 ")) Ċ internal Ġval Ġcop a 3 Ġ= ĠCo Pa (( 3 Ġto Ġ" 1 1 1 ")) Ċ internal Ġval Ġcop a 4 Ġ= ĠCo Pa (( 4 Ġto Ġ" 1 1 1 1 ")) ĊĊ Ċ internal Ġval Ġn node R bt Of 3 Ġ= ĠF RB Tree . of ( TK V Entry . of kv ( co pa 1 , Ġ" foo 1 "), ĠT KV Entry . of kv ( co pa 2 , Ġ" foo 2 "), ĠT KV Entry . of kv ( co pa 3 , Ġ" foo 3 ")) Ċ internal Ġval Ġk node R bt Of 3 Ġ= ĠF RB Tree . of ( co pa 1 . to KK Entry (), Ġcop a 2 . to KK Entry (), Ġcop a 3 . to KK Entry ()) Ċ internal Ġval Ġinode R bt Of 3 Ġ= ĠF RB Tree . of vi ( co pa 1 , Ġcop a 2 , Ġcop a 3 ) Ċ internal Ġval Ġs node R bt Of 3 Ġ= ĠF RB Tree . of vs ( co pa 1 , Ġcop a 2 , Ġcop a 3 ) Ċ internal Ġval Ġn node R bt Of 4 Ġ= ĠF RB Tree . of ( TK V Entry . of kv ( co pa 1 , Ġ" foo 1 "), ĠT KV Entry . of kv ( co pa 2 , Ġ" foo 2 "), ĠT KV Entry . of kv ( co pa 3 , Ġ" foo 3 "), ĠT KV Entry . of kv ( co pa 4 , Ġ" foo 4 ")) Ċ internal Ġval Ġk node R bt Of 4 Ġ= ĠF RB Tree . of ( co pa 1 . to KK Entry (), Ġcop a 2 . to KK Entry (), Ġcop a 3 . to KK Entry (), Ġcop a 4 . to KK Entry ()) Ċ internal Ġval Ġinode R bt Of 4 Ġ= ĠF RB Tree . of vi ( co pa 1 , Ġcop a 2 , Ġcop a 3 , Ġcop a 4 ) Ċ internal Ġval Ġs node R bt Of 4 Ġ= ĠF RB Tree . of vs ( co pa 1 , Ġcop a 2 , Ġcop a 3 , Ġcop a 4 ) Ċ Ċ internal Ġval Ġn node B st Of 3 Ġ= ĠFB ST ree . of ( TK V Entry . of kv ( co pa 1 , Ġ" foo 1 "), ĠT KV Entry . of kv ( co pa 2 , Ġ" foo 2 "), ĠT KV Entry . of kv ( co pa 3 , Ġ" foo 3 ")) Ċ internal Ġval Ġk node B st Of 3 Ġ= ĠFB ST ree . of ( co pa 1 . to KK Entry (), Ġcop a 2 . to KK Entry (), Ġcop a 3 . to KK Entry ()) Ċ internal Ġval Ġinode B st Of 3 Ġ= ĠFB ST ree . of vi ( co pa 1 , Ġcop a 2 , Ġcop a 3 ) Ċ internal Ġval Ġs node B st Of 3 Ġ= ĠFB ST ree . of vs ( co pa 1 , Ġcop a 2 , Ġcop a 3 ) Ċ internal Ġval Ġn node B st Of 4 Ġ= ĠFB ST ree . of ( TK V Entry . of kv ( co pa 1 , Ġ" foo 1 "), ĠT KV Entry . of kv ( co pa 2 , Ġ" foo 2 "), ĠT KV Entry . of kv ( co pa 3 , Ġ" foo 3 "), ĠT KV Entry . of kv ( co pa 4 , Ġ" foo 4 ")) Ċ internal Ġval Ġk node B st Of 4 Ġ= ĠFB ST ree . of ( co pa 1 . to KK Entry (), Ġcop a 2 . to KK Entry (), Ġcop a 3 . to KK Entry (), Ġcop a 4 . to KK Entry ()) Ċ internal Ġval Ġinode B st Of 4 Ġ= ĠFB ST ree . of vi ( co pa 1 , Ġcop a 2 , Ġcop a 3 , Ġcop a 4 ) Ċ internal Ġval Ġs node B st Of 4 Ġ= ĠFB ST ree . of vs ( co pa 1 , Ġcop a 2 , Ġcop a 3 , Ġcop a 4 ) Ċ Ċ internal Ġval Ġcop aN Set Of 3 Ġ= Ġof Body ( n node R bt Of 3 ) Ċ internal Ġval Ġcop a KK Set Of 3 Ġ= Ġof Body ( k node R bt Of 3 ) !! Ċ internal Ġval Ġcop a I Set Of 3 Ġ= Ġof Body ( inode R bt Of 3 ) !! Ċ internal Ġval Ġcop a S Set Of 3 Ġ= Ġof Body ( s node R bt Of 3 ) !! Ċ internal Ġval Ġcop an Set Of 4 Ġ= Ġof Body ( n node R bt Of 4 ) Ċ internal Ġval Ġcop a KK Set Of 4 Ġ= Ġof Body ( k node R bt Of 4 ) !! Ċ internal Ġval Ġcop a I Set Of 4 Ġ= Ġof Body ( inode R bt Of 4 ) !! Ċ internal Ġval Ġcop a S Set Of 4 Ġ= Ġof Body ( s node R bt Of 4 ) !! Ċ Ċ tail rec Ġfun Ġ< A : ĠComparable < A >, ĠB : ĠAny > Ġgo Drop Item All ( t : ĠI MB Tree < A , ĠB >, Ġacc : ĠF List < TK V Entry < A , ĠB >>, Ġin order : ĠF List < TK V Entry < A , ĠB >> ): ĠF List < TK V Entry < A , ĠB >> Ġ= ĊĠĠĠ Ġwhen Ġ( acc ) Ġ{ ĊĠĠĠĠĠĠĠ Ġis ĠFL Nil Ġ-> ĠFL Nil ĊĠĠĠĠĠĠĠ Ġis ĠFL Cons Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdel enda Ġ= Ġacc . head ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdeleted : ĠI MB Tree < A , ĠB > Ġ= Ġt . fd rop Item All ( del enda ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġoracle Ġ= Ġin order . ff ilter Not Ġ{ Ġit Ġ== Ġdel enda Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġaut Ġ= Ġdeleted . in order () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( deleted ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠFB ST Node Ġ-> Ġaut ĠshouldBe Ġoracle ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠFB ST Unique Ġ-> Ġfail (" empty Ġtree Ġshould Ġnot Ġbe Ġempty ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgo Drop Item All ( t , Ġacc . tail , Ġin order ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ internal Ġtail rec Ġfun Ġ< A : ĠComparable < A >, ĠB : ĠAny > Ġgo Drop Item Tele ( t : ĠI MB Tree < A , ĠB >, Ġacc : ĠF List < TK V Entry < A , ĠB >>, Ġin order : ĠF List < TK V Entry < A , ĠB >> ): ĠF List < TK V Entry < A , ĠB >> Ġ= ĊĠĠĠ Ġwhen Ġ( acc ) Ġ{ ĊĠĠĠĠĠĠĠ Ġis ĠFL Nil Ġ-> ĠFL Nil ĊĠĠĠĠĠĠĠ Ġis ĠFL Cons Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdel enda Ġ= Ġacc . head ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdeleted : ĠI MB Tree < A , ĠB > Ġ= Ġt . fd rop Item ( del enda ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġoracle Ġ= Ġin order . fd rop First Ġ{ Ġit Ġ== Ġdel enda Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġaut Ġ= Ġdeleted . in order () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( deleted ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠFB ST Node Ġ-> Ġaut ĠshouldBe Ġoracle ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġis ĠFB ST Unique Ġ-> Ġdeleted . size ĠshouldBe Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgo Drop Item Tele ( deleted , Ġacc . tail , Ġoracle ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ