Home PageTitle PageContentsJJ IIJ IPage 1 of 100Go BackFull ScreenCloseQuitIntroduction to kd-trees• Dimension of data is k (but common to say k-d tree of dimension3 instead of 3d-tree).• kd-trees are binary trees• Designed to handle spatial data in a simple way• For n points, O(n) space, O(log n) height (if balanced), supportsrange and nearest-neighbor queries.• Node consists of– Two child pointers,– Satellite information (such as name).– A key: Either a single float representing a coordinate value, ora pair of floats (representing a dimension of a rectangle)Home PageTitle PageContentsJJ IIJ IPage 2 of 100Go BackFull ScreenCloseQuitBasic Idea Behind kd-treesConstruct a binary tree• At each step, choose one of the coordinate as a basis of dividing therest of the points• For example, at the root, choose x as the basis– Like binary search trees, all items to the left of root will havethe x-coordinate less than that of the root– All items to the right of the root will have the x-coordinategreater than (or equal to) that of the root• Choose y as the basis for discrimination for the root’s children• And choose x again for the root’s grandchildrenNote: Equality (corresponding to right child) is significantHome PageTitle PageContentsJJ IIJ IPage 3 of 100Go BackFull ScreenCloseQuitExample: Construct kd-tree Given Points• Coordinates ofpoints are (35, 90),(70, 80), (10, 75)(80, 40), (50, 90),(70, 30), (90, 60),(50, 25), (25, 10),(20, 50), and (60, 10)• Points may be givenone a time, or all atonce.• Data best visualizedas shown belowHome PageTitle PageContentsJJ IIJ IPage 4 of 100Go BackFull ScreenCloseQuitExample: kdtree InsertionHome PageTitle PageContentsJJ IIJ IPage 5 of 100Go BackFull ScreenCloseQuitBuilding: Dynamic InsertionKDNode i n s e r t ( point p , KDNode t , int cd ) {i f ( t == n u l l ) t = new KDNode ( p ) ;// s e t s up node . data . x and node . data . yel se i f ( p == t . data ) . . . / / d u p l i c at eel se i f ( p . cd < t . data . cd )t . l e f t = i n s e r t ( p , t . l e f t , cd +1);el se t . r i g h t = i n s e r t ( p , t . r i g h t , cd +1);return t ;}• Initial call: root = insert (p, root, 0);• Each node is associated with a rectangular region• Tree is “balanced” if points are given in random order• Or if all points are given in advanceHome PageTitle PageContentsJJ IIJ IPage 6 of 100Go BackFull ScreenCloseQuitBuilding: The Static Case• Assume points are sorted on both x and y in a composite array S• S[x] corresponds to a list of points sorted by x.KDNode bui l d Tree ( SortedArray S , int cd ) {i f ( S . empty ( ) ) return n u l lel se i f S . s i n g l e t o n ( ) return new KDNode( S [ x ] [ 0 ] , cd ) ;el se {m = median ( S , cd ) // median ( c u tt in g dimension )l e f t = l e f t P o i n t s ( S , cd ) ; r i g h t = S − l e f t ;t = new KDNode(m) ;t . l e f t = b uild T r ee ( l e f t , cd +1);t . r i g h t = b u i ldTre e ( r i g h t , cd +1);return t}}• T (n) = kn + 2T (n/2), so the algorithm takes O(n log n) time.Home PageTitle PageContentsJJ IIJ IPage 7 of 100Go BackFull ScreenCloseQuitRemove Requires Finding Minimum• Given a node, and a cutting dimension, find the node with minimumvalue (with respect to that cutting dimension)Point findmin ( KDNode t , int whichAxis , int cd ) {i f ( t == n u l l ) return n u l l ;el se i f ( whichAxis == cd )i f ( t . l e f t == n u l l ) return t . data ;el se return findmin ( t . l e f t , whichAxis , cd+1)el se returnminimum( t . data , findmin ( t . l e f t , whichAxis , cd +1),findmin ( t . r i g h t , whichAxis , cd +1), i ) ;}• If tree is balanced, findmin (root) takes no more than O(√n)time in the worst case.Home PageTitle PageContentsJJ IIJ IPage 8 of 100Go BackFull ScreenCloseQuitExample: findmin(root, x, y)Home PageTitle PageContentsJJ IIJ IPage 9 of 100Go BackFull ScreenCloseQuitBasic Idea Behind Removing• Want to remove point p = (a, b)• First find node t which has this point• Node t discriminates on x (say)– If t is a leaf node, replace it by null– Otherwise, find a replacement node r with coordinates (c, d)– Replace the data at t by (c, d). The kd-tree structure must notbe violated– Recursively remove point p = (c, d)• Finding the replacement– If t has a right child, use the inorder successor– Otherwise minimum value of the left child is appropriately usedHome PageTitle PageContentsJJ IIJ IPage 10 of 100Go BackFull ScreenCloseQuitRemove Example: Delete Point At RootHome PageTitle PageContentsJJ IIJ IPage 11 of 100Go BackFull ScreenCloseQuitRemove Example: Delete PointHome PageTitle PageContentsJJ IIJ IPage 12 of 100Go BackFull ScreenCloseQuitRemove Example: Delete PointHome PageTitle PageContentsJJ IIJ IPage 13 of 100Go BackFull ScreenCloseQuitRemove Takes O(log n) TimeKDNode remove ( KDNode t , Point p , int cd ) {i f ( t == n u l l ) return n u l l ;el se i f (p . cd < t . data ) t . l e f t = remove ( t . l e f t , p , cd +1);el se i f (p . cd > t . data ) t . r i g h t = remove ( t . r i g h t , p , cd +1);el se {i f ( t . r i g h t == n u l l && t . l e f t == n u l l ) return n u l l ;i f ( t . r i g h t ! = n u l l )t . data = findmin ( t . r i g h t , cd , cd +1);el se {t . data = findmin ( t . l e f t , cd , cd +1);t . l e f t = n u l l ;}t . r i g h t = remove ( t . r i g h t , t . data , cd +1);return t ;}}We expect to delete nodes at leaf level. If tree is balanced, we expectremove() to take O(log n) timeHome PageTitle PageContentsJJ IIJ IPage 14 of 100Go BackFull ScreenCloseQuitRemove Example: Delete Point At RootHome PageTitle PageContentsJJ IIJ IPage …