What is the time complexity of searching for an element in a balanced binary search tree?
Solution
Correct Answer: Option C
- বাইনারি সার্চ ট্রি (BST) হলো এমন এক ধরনের ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের মান তার বামদিকের নোডের চেয়ে বড় এবং ডানদিকের নোডের চেয়ে ছোট হয়।
- একটি ব্যালেন্সড বাইনারি সার্চ ট্রিতে (Balanced BST) উচ্চতা বা হাইট সর্বদা log(n) এর অনুপাতে থাকে, যেখানে n হলো মোট নোডের সংখ্যা।
- কোনো উপাদান খোঁজার সময়, প্রতি ধাপে আমরা সিদ্ধান্ত নিই যে বাম দিকে যাবো নাকি ডান দিকে, ফলে প্রতিবার ডেটার পরিমাণ অর্ধেক হয়ে যায়।
- এই অর্ধেক করে খোঁজার পদ্ধতির কারণে ব্যালেন্সড বাইনারি সার্চ ট্রিতে কোনো উপাদান খুঁজতে O(log n) সময় লাগে।
- যদি ট্রি-টি ব্যালেন্সড না হয়ে একপেশে বা স্কিউড (Skewed) হয়, তবে সেক্ষেত্রে সময় লাগতে পারে O(n), কিন্তু ব্যালেন্সড অবস্থায় এটি সর্বদা O(log n)।
- একটি ব্যালেন্সড বাইনারি সার্চ ট্রিতে (Balanced BST) উচ্চতা বা হাইট সর্বদা log(n) এর অনুপাতে থাকে, যেখানে n হলো মোট নোডের সংখ্যা।
- কোনো উপাদান খোঁজার সময়, প্রতি ধাপে আমরা সিদ্ধান্ত নিই যে বাম দিকে যাবো নাকি ডান দিকে, ফলে প্রতিবার ডেটার পরিমাণ অর্ধেক হয়ে যায়।
- এই অর্ধেক করে খোঁজার পদ্ধতির কারণে ব্যালেন্সড বাইনারি সার্চ ট্রিতে কোনো উপাদান খুঁজতে O(log n) সময় লাগে।
- যদি ট্রি-টি ব্যালেন্সড না হয়ে একপেশে বা স্কিউড (Skewed) হয়, তবে সেক্ষেত্রে সময় লাগতে পারে O(n), কিন্তু ব্যালেন্সড অবস্থায় এটি সর্বদা O(log n)।
অ্যাপ/ওয়েবসাইটে রুটিনভিত্তিক নিয়মিত লাইভ পরীক্ষা হচ্ছে।
পরীক্ষা - ১৩
কোর্স নামঃ
১৯তম নিবন্ধন (প্রভাষক): গ্রন্থাগার ও তথ্য বিজ্ঞান
টপিকসঃ
আধুনিক প্রযুক্তি ও সাম্প্রতিক উন্নয়ন:
গ্রন্থাগার বিজ্ঞান ও তথ্যপ্রযুক্তির সাম্প্রতিক উন্নয়ন, ই-লাইব্রেরি ও ডিজিটাল তথ্য ব্যবস্থাপনা।
গ্রন্থাগার বিজ্ঞান ও তথ্যপ্রযুক্তির সাম্প্রতিক উন্নয়ন, ই-লাইব্রেরি ও ডিজিটাল তথ্য ব্যবস্থাপনা।
পরীক্ষা শুরুঃ ২৫ জুলাই, ২০২৬
রুটিন দেখুন
Practice More Questions on Our App!
Download our app for free and access thousands of MCQ questions with detailed solutions