Snip

kd tree 

Categories 


For Snip 
loading snip actions ... 

For Page 
loading url actions ... 
(data structure)
Definition: A multidimensional search tree for points in k dimensional space. Levels of the tree are split along successive dimensions at the points.
See also binary search tree, adaptive kd tree, point access method.
Note: After [GG98]. Robert Keith Oswald (rko9h@virginia.edu) explains, In a traditional binary search tree, records are defined by only one key. In a kd tree, records are defined by k keys. Like a traditional binary search trees, records are inserted and returned using < and ≥. However, the key that determines the subtree to use (i.e. left or right) varies with the level in the tree. At level L, key number L mod k + 1 is used, where the root is at level 0. Therefore, the first key is used at the root, the second key at level 1, and so on until all keys have been used. The keys are used again beginning at level k.
HTML 
<h1>kd tree</h1> <p> (data structure) </p> <p> <strong>Definition:</strong> A multidimensional <a href="searchtree.html"><em>search tree</em></a> for points in k dimensional space. Levels of the tree are split along successive dimensions at the points. </p> <p> <strong>See also</strong> <a href="binarySearchTree.html"><em>binary search tree</em></a>, <a href="adaptkdtree.html"><em>adaptive kd tree</em></a>, <a href="pointAccessMethod.html"><em>point access method</em></a>. </p> <p> <em>Note: After <a href="../terms.html#GG98">[GG98]</a>. Robert Keith Oswald (rko9h@virginia.edu) explains, In a traditional binary search tree, records are defined by only one key. In a kd tree, records are defined by k keys. Like a traditional binary search trees, records are inserted and returned using < and ≥. However, the key that determines the subtree to use (i.e. left or right) varies with the level in the tree. At level L, key number L mod k + 1 is used, where the root is at level 0. Therefore, the first key is used at the root, the second key at level 1, and so on until all keys have been used. The keys are used again beginning at level k.</em></p> 
