数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学多维二叉搜索树
基本概念
多维二叉搜索树（简称k-d树）被定义为一种用于存储多键记录的数据结构。这种结构已被用于解决统计和数据分析中许多“几何”问题。
k-d树（k维树的简称）被定义为一种空间划分数据结构，用于组织k维空间中的点。数据结构k-d树被用于多种应用，例如涉及多维搜索键的搜索（例如范围搜索和最近邻搜索）。k-d树被视为二叉空间划分树的特例。
非正式描述
k-d树是一个二叉树，其中每个叶子节点都被视为一个k维点。每个非叶子节点都可以想象成隐式地生成一个分割超平面（用作中位数），将空间分成两部分，称为半空间。此超平面左侧的点由该节点的左子树处理，超平面右侧的点由右子树处理。我们可以按以下方式选择超平面的方向：树中的每个节点都与k个维度中的一个相关联，以及垂直于该维度轴的超平面。因此，例如，如果对于特定分割选择“x”轴，则“x”值小于节点的子树中的所有点将出现在左子树中，“x”值较高的所有点将出现在右子树中。在这种情况下，超平面将由点的x值设置，其法线表示单位x轴。一种常用的做法是对固定数量的随机选取的点进行排序，并使用这些点的中位数作为分割平面。
给定一个包含n个点的列表，以下算法使用中位数查找排序来构建包含这些点的平衡k-d树。
function KDtree (list of points PointList, int Depth) {
// Choose axis based on Depth so that axis cycles through all valid values
var int axis := Depth mod k;
// Sort point list and select median as pivot element
choose median by axis from PointList;
// Node is created as node1 and construct subtree
node1.location := median;
node1.leftChild := KDtree(points in PointList before median, Depth+1);
node1.rightChild := KDtree(points in PointList after median, Depth+1);
return node1;
}
更新于：2020年1月3日
1K+ 次浏览
广告