private Node buildFromPoints ( int lower , int upper ) { if ( upper == lower ) { return null ; } final Node node = new Node ( ) ; node . index = lower ; if ( upper - lower > 1 ) { // choose an arbitrary vantage point and move it to the start int i = random . nextInt ( upper - lower - 1 ) + lower ; listSwap ( items , lower , i ) ; listSwap ( indexes , lower , i ) ; int median = ( upper + lower + 1 ) / 2 ; // partition around the median distance // TODO: use the QuickSelect class? nthElement ( lower + 1 , upper , median , items [ lower ] ) ; // what was the median? node . threshold = distance ( items [ lower ] , items [ median ] ) ; node . index = lower ; node . left = buildFromPoints ( lower + 1 , median ) ; node . right = buildFromPoints ( median , upper ) ; } return node ; }
Builds the tree from a set of points by recursively partitioning them according to a random pivot .