বহুমাত্রিক বাইনারি অনুসন্ধান গাছ

মৌলিক ধারণা

মাল্টিডাইমেনশনাল বাইনারি সার্চ ট্রি (সংক্ষেপে কে-ডি ট্রি) মাল্টিকি রেকর্ড সংরক্ষণের জন্য একটি ডেটা স্ট্রাকচার হিসেবে সংজ্ঞায়িত করা হয়েছে। পরিসংখ্যান এবং ডেটা বিশ্লেষণে বেশ কয়েকটি "জ্যামিতিক" সমস্যা সমাধানের জন্য এই কাঠামোটি প্রয়োগ করা হয়েছে৷

একটি কে-ডি ট্রি (কে-ডাইমেনশনাল ট্রির জন্য সংক্ষিপ্ত) কে-ডাইমেনশনাল স্পেসে বিন্দু সংগঠিত করার জন্য স্পেস-পার্টিশনিং ডেটা স্ট্রাকচার হিসাবে সংজ্ঞায়িত করা হয়। ডেটা স্ট্রাকচার কে-ডি ট্রিগুলি বেশ কয়েকটি অ্যাপ্লিকেশনের জন্য প্রয়োগ করা হয়, উদাহরণস্বরূপ, একটি বহুমাত্রিক অনুসন্ধান কী যুক্ত অনুসন্ধানগুলি (যেমন পরিসর অনুসন্ধান এবং নিকটতম প্রতিবেশী অনুসন্ধান)। k-d গাছগুলিকে বাইনারি স্পেস পার্টিশনিং ট্রিগুলির একটি বিশেষ ক্ষেত্রে হিসাবে বিবেচনা করা হয়।

অনানুষ্ঠানিক বর্ণনা

কে-ডি ট্রি হল একটি বাইনারি গাছ যেখানে প্রতিটি পাতার নোডকে কে-মাত্রিক বিন্দু হিসেবে ধরা হয়। প্রতিটি নন-লিফ নোডকে পরোক্ষভাবে একটি বিভক্ত হাইপারপ্লেন (মাঝারি হিসাবে ব্যবহার করা হয়) তৈরি করা হিসাবে কল্পনা করা যেতে পারে যা স্থানটিকে দুটি অংশে বিভক্ত করে, যাকে অর্ধ-স্পেস বলা হয়। এই হাইপারপ্লেনের বাম দিকের পয়েন্টগুলি সেই নোডের বাম সাবট্রি দ্বারা চিকিত্সা করা হয় এবং হাইপারপ্লেনের ডানদিকের পয়েন্টগুলিকে ডান সাবট্রি দ্বারা চিকিত্সা করা হয়। আমরা নিম্নলিখিত উপায়ে হাইপারপ্লেন দিক নির্বাচন করতে পারি:গাছের প্রতিটি নোড সেই মাত্রার অক্ষের হাইপারপ্লেন লম্বের সাথে 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;
}