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