ต้นไม้การค้นหาไบนารีหลายมิติ

แนวคิดพื้นฐาน

แผนผังการค้นหาแบบไบนารีหลายมิติ (ตัวย่อ k-d tree) ถูกกำหนดให้เป็นโครงสร้างข้อมูลสำหรับการจัดเก็บเร็กคอร์ดแบบมัลติคีย์ โครงสร้างนี้ถูกนำมาใช้เพื่อแก้ปัญหา "เรขาคณิต" จำนวนมากในสถิติและการวิเคราะห์ข้อมูล

k-d tree (ย่อมาจาก k-dimensional tree) ถูกกำหนดให้เป็นโครงสร้างข้อมูลการแบ่งพื้นที่สำหรับการจัดจุดในพื้นที่ k-dimensional โครงสร้างข้อมูล k-d tree ถูกนำมาใช้สำหรับแอพพลิเคชั่นต่างๆ เช่น การค้นหาที่เกี่ยวข้องกับคีย์การค้นหาแบบหลายมิติ (เช่น การค้นหาพิสัยและการค้นหาเพื่อนบ้านที่ใกล้ที่สุด) ต้นไม้ 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;
}