- একটি গতিশীল আঙুল অনুসন্ধান ডেটা কাঠামো আঙুল অনুসন্ধান ছাড়াও একটি আঙুল দ্বারা প্রদত্ত অবস্থানে উপাদান সন্নিবেশ এবং মুছে ফেলার কাজ করা উচিত৷
- আঙুল অনুসন্ধান গাছগুলিকে O(লগ ডি) সময়ে আঙুল অনুসন্ধান এবং O(1) সময়ে আপডেটগুলি সমর্থনকারী B-বৃক্ষের একটি বৈকল্পিক হিসাবে সংজ্ঞায়িত করা হয়, ধরে নেওয়া হয় যে শুধুমাত্র O(1) নড়াচড়াযোগ্য আঙ্গুলগুলি বজায় রাখা হয়৷
- একটি আঙুলের d অবস্থান অতিক্রম করার জন্য O(log d) সময় প্রয়োজন।
- আঙুল অনুসন্ধান গাছ (অর্থাৎ AVL-বৃক্ষ, লাল-কালো গাছ) নির্মাণগুলি হয় আঙ্গুলের একটি নির্দিষ্ট ধ্রুবক সংখ্যা বিবেচনা করে বা শুধুমাত্র পরিমার্জিত ধ্রুবক সময়ে আপডেট সমর্থন করে৷
- নির্মাণগুলি নির্বিচারে আঙ্গুলের সংখ্যাকে সমর্থন করে এবং সবচেয়ে খারাপ ক্ষেত্রে আপডেট করা হয়েছে৷
- একটি অনুসন্ধান ট্রি যেটি সবচেয়ে খারাপ ক্ষেত্রে O(1) সময়ে একটি ইচ্ছামত অবস্থানে আপডেট সমর্থন করে, কিন্তু শুধুমাত্র O(log n) সময়ে অনুসন্ধান সমর্থন করে৷
- O(log d) সময় অনুসন্ধান এবং O(log d n) সময় সন্নিবেশ এবং মুছে ফেলার সমর্থনকারী নির্মাণগুলি৷
- আঙুল অনুসন্ধান গাছ সবচেয়ে খারাপ-কেস ধ্রুবক সময় সন্নিবেশ এবং O(log d n) সময় মুছে ফেলার খরচ করে।
- সংযুক্ত স্তরের (2,4)- গাছের জন্য একটি স্থান দক্ষ বিকল্প সমাধান অনুসারে, একটি একক আঙুল অনুমোদিত, যা (2,4)-বৃক্ষের মতো একই কার্যক্ষমতা খরচ দ্বারা এগিয়ে যেতে পারে। সমাধানে কোন লেভেল লিঙ্ক এবং প্যারেন্ট পয়েন্টারের প্রয়োজন নেই, পরিবর্তে একটি বিশেষ O(log n) স্পেস ডেটা স্ট্রাকচার, হাত, আঙুলের জন্য তৈরি করা হয়েছে যা আঙুলটিকে দক্ষতার সাথে অতিক্রম করতে দেয়।
- স্প্লে ট্রিগুলিকে স্ব-সামঞ্জস্যকারী বাইনারি অনুসন্ধান গাছের একটি শ্রেণি হিসাবে সংজ্ঞায়িত করা হয় যা পরিমার্জিত O(লগ n) সময়ে অনুসন্ধান, সন্নিবেশ এবং মুছে ফেলাকে সমর্থন করে। সেই স্প্লে ট্রিগুলিকে দক্ষ আঙুল অনুসন্ধান গাছ হিসাবে প্রয়োগ করা যেতে পারে৷
- একটি O(n) প্রারম্ভিক খরচ দেওয়া হলে, একটি স্প্লে ট্রিতে পূর্ববর্তী অ্যাক্সেস থেকে d দূরত্বে অ্যাক্সেসের পরিমার্জিত খরচ হল O(লগ ডি) যেখানে অ্যাক্সেসগুলি অনুসন্ধান, সন্নিবেশ এবং মুছে ফেলার সমন্বয়ে গঠিত।
- লক্ষ্য করুন যে বিবৃতিটি শুধুমাত্র একটি আঙুলের উপস্থিতিতে প্রয়োগ করা হয়, যা সর্বদা সর্বশেষ অ্যাক্সেস করা উপাদানটিকে নির্দেশ করে৷
- উপরে উল্লেখিত সমস্ত নির্মাণ একটি পয়েন্টার মেশিনে প্রয়োগ করা যেতে পারে যেখানে উপাদানগুলির উপর একমাত্র অপারেশন অনুমোদিত দুটি উপাদানের তুলনা।
- কম্পিউটেশন (RAM) এর র্যান্ডম অ্যাক্সেস মেশিন মডেলের জন্য, ধ্রুবক আপডেট সময় এবং O(লগ ডি) অনুসন্ধান সময় সহ একটি আঙুল অনুসন্ধান ট্রি তৈরি করা হয়েছে। এই ফলাফলটি ছোট গাছের কাঠামোর ট্যাবুলেটিং করে অর্জন করা হয়, কিন্তু শুধুমাত্র উপাদানগুলির তুলনা করে।
