public void splitNode ( KDTreeNode node , int numNodesCreated , double [ ] [ ] nodeRanges , double [ ] [ ] universe ) throws Exception { correctlyInitialized ( ) ; int splitDim = widestDim ( nodeRanges , universe ) ; //In this case median is defined to be either the middle value (in case of //odd number of values) or the left of the two middle values (in case of //even number of values). int medianIdxIdx = node . m_Start + ( node . m_End - node . m_Start ) / 2 ; //the following finds the median and also re-arranges the array so all //elements to the left are < median and those to the right are > median. int medianIdx = select ( splitDim , m_InstList , node . m_Start , node . m_End , ( node . m_End - node . m_Start ) / 2 + 1 ) ; node . m_SplitDim = splitDim ; node . m_SplitValue = m_Instances . instance ( m_InstList [ medianIdx ] ) . value ( splitDim ) ; node . m_Left = new KDTreeNode ( numNodesCreated + 1 , node . m_Start , medianIdxIdx , m_EuclideanDistance . initializeRanges ( m_InstList , node . m_Start , medianIdxIdx ) ) ; node . m_Right = new KDTreeNode ( numNodesCreated + 2 , medianIdxIdx + 1 , node . m_End , m_EuclideanDistance . initializeRanges ( m_InstList , medianIdxIdx + 1 , node . m_End ) ) ; }
Splits a node into two based on the median value of the dimension in which the points have the widest spread . After splitting two new nodes are created and correctly initialised . And node . left and node . right are set appropriately .