資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告