📄 kdtree.html

📁 数据结构词典（英文）
💻 HTML
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD W3 HTML 2.0//EN">
<HTML lang="en-US">
<HEAD>
<TITLE>k-d tree</TITLE>
<META name="description"
  content="Definition of k-d tree,
	possibly with links to more information and implementations.">
<META name="keywords" content="k-d tree">
</HEAD>
<BODY BGCOLOR="#FFFFFF">

<H1>k-d tree</H1>
<P>
(data structure)

<P>
<strong>Definition:</strong>
A multidimensional <a href="searchtree.html" tppabs="http://hissa.nist.gov/dads/HTML/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><strong>See also</strong>
<a href="binarysrchtr.html" tppabs="http://hissa.nist.gov/dads/HTML/binarysrchtr.html"><em>binary search tree</em></a>, <a href="adaptkdtree.html" tppabs="http://hissa.nist.gov/dads/HTML/adaptkdtree.html"><em>adaptive k-d tree</em></a>, <a href="pointaccess.html" tppabs="http://hissa.nist.gov/dads/HTML/pointaccess.html"><em>point access method</em></a>.
<P><em>Note:
After [1].  Robert Keith Oswald (rko9h@virginia.edu) explains, In a traditional binary search tree, records are  defined by only one key. In a k-d tree, records are defined  by k keys. Like a traditional binary search trees, records  are inserted and returned using &lt; and  <img src="geq.gif" tppabs="http://hissa.nist.gov/dads/HTML/Images/geq.gif" border=0 height=7  width=14 alt="greater than or equal to">.  However, the key which 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>Author: <a href="terms.html#authorPEB" tppabs="http://hissa.nist.gov/dads/terms.html#authorPEB">PEB</a>
<H2>Implementation</H2>
<A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sunysb.edu/%7Ealgorith/files/kd-trees.shtml  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sunysb.edu/%7Ealgorith/files/kd-trees.shtml'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sunysb.edu/%7Ealgorith/files/kd-trees.shtml">C, Pascal, or FORTRAN</A>, <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.ins.c.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.ins.c.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.ins.c.html">insert (C)</A>, <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.range.c.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.range.c.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.range.c.html">range search (C)</A>, and <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.srch.c.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.srch.c.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.dcc.uchile.cl/%7Eoalonso/handbook/algs/3/352.srch.c.html">search (C)</A>. <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sunysb.edu/%7Ealgorith/files/kd-trees.shtml  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sunysb.edu/%7Ealgorith/files/kd-trees.shtml'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://www.cs.sunysb.edu/%7Ealgorith/files/kd-trees.shtml">(C, Pascal, and Fortran)</A>
<H2>More information</H2>
Some <A HREF="javascript:if(confirm('http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://fbox.vt.edu:10021/J/jegrant/stuff/kdtrees.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://fbox.vt.edu:10021/J/jegrant/stuff/kdtrees.html'" tppabs="http://www.nist.gov/cgi-bin/exit_nist.cgi?url=http://fbox.vt.edu:10021/J/jegrant/stuff/kdtrees.html">notes on k-d trees</A> and other spatial data structures.

<hr>

Go to the
<A HREF="terms.html" tppabs="http://hissa.nist.gov/dads/terms.html">Algorithms, Data Structures, and Problems</A>
home page.

<hr>

If you have suggestions, corrections, or comments, please get in touch
with
<a href="javascript:if(confirm('http://hissa.nist.gov/~black/black.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://hissa.nist.gov/~black/black.html'" tppabs="http://hissa.nist.gov/~black/black.html">Paul E. Black</a>
&nbsp;(<a href="mailto:paul.black@nist.gov">paul.black@nist.gov</a>).

<p>
Entry modified Wed Nov 24 13:57:59 1999.<BR>
HTML page formatted Wed Dec 22 09:35:38 1999.

<P>
This page's URL is
<A href="kdtree.html" tppabs="http://hissa.nist.gov/dads/HTML/kdtree.html">http://hissa.nist.gov/dads/HTML/kdtree.html</A>

</BODY>
</HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -