private Node < K , V > randomizedInsert ( Node < K , V > x , Interval1D < K > interval , V value ) { if ( x == null ) { return new Node <> ( interval , value ) ; } if ( java . lang . Math . random ( ) * size ( x ) < 1.0 ) { return rootInsert ( x , interval , value ) ; } int cmp = interval . compareTo ( x . interval ) ; if ( cmp < 0 ) { x . left = randomizedInsert ( x . left , interval , value ) ; } else { x . right = randomizedInsert ( x . right , interval , value ) ; } fix ( x ) ; return x ; }
make new node the root with uniform probability