স্থানিক অনুসন্ধান কাঠামোগুলি একই ধারণার উপর ভিত্তি করে তৈরি করা হয়েছে যা 60 এবং 70 এর দশকে কম্পিউটার সায়েন্সে উদ্ভাবিত হয়েছিল জ্যামিতিক ডেটার বিপরীতে, যেমন মানুষের নামের তালিকার বিপরীতে সিম্বলিক ডেটার বড় সেট প্রক্রিয়াকরণের সমস্যা সমাধানের জন্য। এটি উদ্ভাবিত হয়েছিল যে প্রথমে বর্ণমালা অনুসারে নামের তালিকা বাছাই করে এবং বাছাই করা তালিকাটিকে একটি অ্যারেতে সংরক্ষণ করে, n/2 এর পরিবর্তে একটি বাইনারি অনুসন্ধান অ্যালগরিদম ব্যবহার করে log2n অপারেশনে তালিকায় কিছু নতুন নাম ইতিমধ্যেই রয়েছে কিনা তা গণনা করতে পারে। একটি অনুক্রমিক অনুসন্ধানের সাহায্যে প্রত্যাশিত অপারেশন প্রয়োজন। নামের তালিকায় বিদ্যমান কাঠামো (বর্ণানুক্রমিক ক্রম) বের করার এবং গণনা হ্রাস করার জন্য পরবর্তী ক্রিয়াকলাপগুলিতে (একটি নাম খোঁজা) সেই কাঠামোকে কাজে লাগানোর এটি একটি ভাল উদাহরণ।
যাইহোক, যদি কেউ একটি সাজানো তালিকা বজায় রাখার সময় নামগুলি সংযোজন এবং মুছে ফেলার অনুমতি দিতে চায়, তাহলে একটি গতিশীল ডেটা কাঠামো প্রয়োজন, যেমন একটি বাস্তবায়নকারী পয়েন্টার। এই ধরনের ডেটা স্ট্রাকচারের সবচেয়ে সাধারণ উদাহরণগুলির মধ্যে একটি হল বাইনারি সার্চ ট্রি ছাড়া আর কিছুই নয়৷
৷একটি বাইনারি সার্চ ট্রির ক্ষেত্রে, যেখানে এটি বাস্তব রেখায় পড়ে থাকা A ={1, 2, 5, 6, 7, 9} এর মতো পূর্ণসংখ্যার সেটকে উপস্থাপন করার জন্য প্রয়োগ করা হচ্ছে। একটি সংখ্যা/বিন্দু ইতিমধ্যেই গাছে আছে কিনা তা গণনা করতে, কেউ গাছের মধ্যে বিন্দুটি সন্নিবেশ করতে সক্ষম হয় এবং বিন্দু নিয়ে গঠিত নেস্টেড বিরতির ক্রম অনুসারে পথ অনুসরণ করতে পারে। একটি ভারসাম্যপূর্ণ গাছের জন্য, এই প্রক্রিয়াটি O(log n) ধাপের বেশি ব্যবহার করবে না; প্রকৃতপক্ষে, আমরা একটি বাইনারি অনুসন্ধান করেছি, কিন্তু একটি অ্যারের পরিবর্তে একটি গাছ বাস্তবায়ন করছে। এখন, ট্রি নিজেই অনুসন্ধান অ্যালগরিদমের একটি অংশকে এনকোড করতে সক্ষম কারণ এটি অনুসন্ধানের অগ্রগতির ক্রম নির্ধারণ করে৷
এটি এখন আমাদের পার্টিশনিং ট্রি-এ ফিরে আসে, এগুলিকে বাইনারি সার্চ ট্রিগুলির মাত্রা> 1 অর্থাৎ বহুমাত্রিক (1D-তে, এগুলি মূলত একই) হিসাবে গণ্য করা হয়। প্রকৃতপক্ষে, একটি পার্টিশনিং ট্রি নির্মাণকে দ্রুত সাজানোর জ্যামিতিক সংস্করণ হিসাবে কল্পনা করা যেতে পারে।
পরিবর্তনগুলি (মুছে ফেলা এবং সন্নিবেশ) বৃক্ষ মার্জ করে অর্জন করা হয়, মার্জ সর্টে বাছাই করা তালিকাগুলিকে একত্রিত করার অনুরূপ৷
যাইহোক, যেহেতু পয়েন্টগুলি কোন মাত্রা> 1 এর জন্য স্থানকে ভাগ করে না, তাই আমাদের অবশ্যই হাইপারপ্লেনগুলি প্রয়োগ করতে হবে বিন্দুগুলির পরিবর্তে যার দ্বারা উপবিভাজন করতে হবে৷
হাইপারপ্লেনগুলি সর্বদা একটি অঞ্চলকে দুই অর্ধেক স্থানে ভাগ করে বা বিভক্ত করে মাত্রা নির্বিশেষে৷
