Multidimensional Binary Search Trees (k-d Trees) ในโครงสร้างข้อมูล

k-d Tree (k-dimensional Tree) คืออะไร?

Multidimensional Binary Search Tree (k-d Tree) = Data Structure สำหรับจัดเก็บ Multi-key Records ใช้แก้ "Geometric Problems" ใน Statistics และ Data Analysis

Space-Partitioning Data Structure สำหรับ Organize Points ใน k-Dimensional Space
Applications: Range Searches, Nearest Neighbor Searches
Special Case ของ Binary Space Partitioning Trees

Informal Description

• Binary Tree: Leaf = k-Dimensional Point
• Non-Leaf Node = Implicit Splitting Hyperplane (Median) → แบ่ง Space เป็น 2 Half-Spaces
• Points ซ้าย Hyperplane → Left Subtree, Points ขวา → Right Subtree
• Hyperplane Direction: Node แต่ละตัว Associated กับ 1 ใน k Dimensions, Hyperplane ⟂ Axis ของ Dimension นั้น

Example: Split ด้วย "x" Axis → Points x < Node.x → Left, x > Node.x → Right
Hyperplane = x = Node.x, Normal = Unit x-axis

Practice: Sort Random Sample Points → Median = Splitting Plane

Algorithm: Balanced k-d Tree Construction

function KDtree(PointList, Depth) {
    // Choose Axis based on Depth (Cycle through all k dimensions)
    axis := Depth mod k;

    // Sort PointList by Axis, Select Median as Pivot
    median := Choose Median by Axis from PointList;

    // Create Node
    node.location := median;
    node.leftChild := KDtree(Points before Median, Depth+1);
    node.rightChild := KDtree(Points after Median, Depth+1);
    return node;
}

Complexity

• Construction: O(n log n) (Median Finding + Sorting)
• Range Search: O(n^1-1/k + k) Average
• Nearest Neighbor: O(log n) Average
• Space: O(n)

สรุป

k-d Trees = Fundamental Spatial Data Structure สำหรับ Multi-dimensional Data
Simple, Efficient, ใช้กันกว้างใน Computer Graphics, ML, Databases, GIS