মৌলিক ধারণা
বহুমাত্রিক বাইনারি সার্চ ট্রি (সংক্ষেপে k-d ট্রি) হলো একটি ডেটা স্ট্রাকচার মাল্টিকী রেকর্ড স্টোর করার জন্য। এই স্ট্রাকচারটি ব্যবহার করা হয়েছেstattistics এবং ডেটা অ্যানালিসিসে অনেক "জ্যামিতিক" সমস্যা সমাধান করতে।
একটি k-d ট্রি (k-ডাইমেনশনাল ট্রির সংক্ষিপ্ত) হলো একটি স্পেস-পার্টিশনিং ডেটা স্ট্রাকচার k-ডাইমেনশনাল স্পেসে পয়েন্ট আর্গানাইজ করার জন্য। k-d ট্রি ডেটা স্ট্রাকচার ব্যবহার করা হয় বিভিন্ন অ্যাপ্লিকেশনে, উদাহরণস্বরূপ, একটি মাল্টিডাইমেনশনাল সার্চ কী ইনভল্ভ করা সার্চ (যেমন রেঞ্জ সার্চ এবং নিরেস্ট নেইবর সার্চ)। k-d ট্রি বাইনারি স্পেস পার্টিশনিং ট্রির একটি স্পেশাল কেস হিসেবে বিবেচিত হয়।
অনौপচারিক বর্ণনা (Informal description)
k-ডি ট্রি হলো একটি বাইনারি ট্রি যেখানে প্রতিটি লিফ নোড বিবেচিত হয় একটি 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; }
