ডেটা স্ট্রাকচারে এলোমেলো আঙুল অনুসন্ধান গাছ

ডিটারমিনিস্টিক সার্চ ট্রির দুটি এলোমেলো বিকল্প হল র্যান্ডমাইজড বাইনারি সার্চ ট্রি, ট্রিপস এবং স্কিপ লিস্ট। ট্রিপস এবং স্কিপ লিস্ট উভয়ই মার্জিত ডেটা স্ট্রাকচার হিসাবে সংজ্ঞায়িত করা হয়েছে, যেখানে র্যান্ডমাইজেশন সহজ এবং দক্ষ আপডেট অপারেশনগুলিকে সহজতর করে৷

এই বিভাগে আমরা ব্যাখ্যা করি যে কীভাবে ডেটা স্ট্রাকচার পরিবর্তন না করেই ট্রিপস এবং স্কিপ লিস্ট উভয়ই দক্ষ ফিঙ্গার সার্চ ট্রি হিসাবে প্রয়োগ করা যেতে পারে। উভয় ডেটা স্ট্রাকচারই প্রত্যাশিত O(লগ ডি) সময় ব্যবহার করে আঙ্গুলের অনুসন্ধানগুলিকে সমর্থন করে, যেখানে ডেটা স্ট্রাকচার নির্মাণের সময় অ্যালগরিদম দ্বারা তৈরি এলোমেলো পছন্দগুলির উপর প্রত্যাশাগুলি নেওয়া হয়৷

তালিকাগুলি এড়িয়ে যান

একটি এড়িয়ে যাওয়ার তালিকায়, এই বিন্দু থেকে অনুসন্ধান চালিয়ে যাওয়ার মাধ্যমে b এলিমেন্ট ধারণকারী নোড থেকে এলিমেন্ট a-এর জন্য কেউ আঙুল দিয়ে অনুসন্ধান করতে পারে। মনে রাখবেন যে যদি a b, তাহলে অনুসন্ধানটি সামনের দিকে এগিয়ে যায়। ব্যাকওয়ার্ড কেসটি স্কিপ লিস্টে সাধারন সার্চের সাথে সিমেট্রিক, কিন্তু ফরোয়ার্ড কেস আসলে আরো জটিল। সাধারণত, একটি এড়িয়ে যাওয়ার তালিকায় অনুসন্ধান দ্রুত হবে বলে আশা করা হয় কারণ তালিকার শুরুতে সেন্টিনেলটিকে সবচেয়ে লম্বা নোড হিসাবে বিবেচনা করা হয়। যাইহোক, আমাদের আঙুল উচ্চতা 1 এর একটি নোডের সাথে যুক্ত হতে পারে। এই কারণে, অনুসন্ধান করার চেষ্টা করার সময় আমরা খুব কমই আরোহণ করতে পারি; এমন কিছু যা সাধারণত ঘটে না। যাইহোক, এমনকি এই জটিলতার সাথেও, আমরা O(log d) প্রত্যাশিত অনুসন্ধান সময় অর্জন করতে সক্ষম হতে পারি।

ট্রেপস

একটি ট্রিপকে একটি এলোমেলো বাইনারি অনুসন্ধান গাছ (BST) হিসাবে সংজ্ঞায়িত করা হয়। একটি ট্রিপে অনুসন্ধান করা অন্য যেকোনো BST-তে একটি উপাদান অনুসন্ধান করার মতোই। যদিও Treaps-এর বৈশিষ্ট্য রয়েছে যে দূরত্বের দুটি উপাদানের মধ্যে প্রত্যাশিত পথের দৈর্ঘ্যকে O(log d) হিসাবে চিহ্নিত করা হয়। এইভাবে, a এলিমেন্টের b এলিমেন্ট সম্বলিত নোড থেকে আঙ্গুল দিয়ে সার্চ করার জন্য, a এলিমেন্টের পূর্বপুরুষ না পাওয়া পর্যন্ত একজন b এলিমেন্ট থেকে গাছে আরোহণ করতে পারে, যেখানে স্বাভাবিক BST সার্চ যথারীতি চলতে থাকে। একটি নোড অন্যটির পূর্বপুরুষ কিনা তা গণনা করার সময় অ-তুচ্ছ, প্রত্যাশিত O(লগ ডি) আঙুল অনুসন্ধানের সময় প্রদান করতে এই ফর্মের প্রশ্নগুলিকে সমর্থন করার জন্য কেউ গাছটিকে বাড়িয়ে তুলতে পারে৷