What is the time complexity of searching for an element in a balanced binary search tree?
সমাধান
সঠিক উত্তর: 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)।
