- একটি ডাইনামিক ফিংগার সার্চ ডেটা স্ট্রাকচার উচিত ফিংগার সার্চের পাশাপাশি এলিমেন্ট ইনসার্শন এবং ডিলিশন পারফর্ম করতে একটি পজিশন যা একটি ফিংগার দ্বারা দেওয়া।
- ফিংগার সার্চ ট্রি ডিফাইন করা হয় B-ট্রির একটি ভ্যারিয়েন্ট হিসেবে ফিংগার সার্চ সাপোর্ট করে O(log d) টাইমে এবং আপডেট O(1) টাইমে, অনুমান করে যে শুধু 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(log n) টাইমে। স্প্লে ট্রি কার্যকর ফিংগার সার্চ ট্রি হিসেবে বাস্তবায়িত হতে পারে।
- একটি O(n) ইনিশিয়ালাইজেশন কস্ট দেওয়া, একটি স্প্লে ট্রিতে প্রিভিয়াস অ্যাক্সেস থেকে দূরত্ব d-এ একটি অ্যাক্সেসের এমরটাইজড কস্ট O(log d) যেখানে অ্যাক্সেস কনসিস্ট অফ সার্চ, ইনসার্শন, এবং ডিলিশন।
- লক্ষ্য করুন যে স্টেটমেন্টটি শুধু অ্যাপ্লাই হয় এক ফিংগারের প্রেজেন্সে, যা সর্বদা লাস্ট অ্যাক্সেসড এলিমেন্টকে পয়েন্ট করে।
- উপরোক্ত সকল কনস্ট্রাকশন পয়েন্টার মেশিনে অ্যাপ্লাই করা যায় যেখানে এলিমেন্টের ওপর একমাত্র অপারেশন অ্যালোড হলো দুটি এলিমেন্ট কমপেয়ার করা।
- র্যান্ডম অ্যাক্সেস মেশিন মডেল অফ কম্পুটেশন (RAM)-এর জন্য, একটি ফিংগার সার্চ ট্রি ডেভেলপ করা হয়েছে কনস্ট্যান্ট আপডেট টাইম এবং O(log d) সার্চ টাইমের সাথে। এই রেজাল্ট অর্জিত হয়েছে ছোট ট্রি স্ট্রাকচার ট্যাবুলেট করে, কিন্তু শুধু এলিমেন্ট কমপেয়ার পারফর্ম করে।
