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)।
অ্যাপ/ওয়েবসাইটে রুটিনভিত্তিক নিয়মিত লাইভ পরীক্ষা হচ্ছে।
পরীক্ষা – ১১২
কোর্স নামঃ
১৯ তম শিক্ষক নিবন্ধন - লেকচারশীট ভিত্তিক।
টপিকসঃ
সাধারণ জ্ঞান – বাংলাদেশ
বাংলাদেশের জাতিগোষ্ঠী ও উপজাতি সংক্রান্ত বিষয়াদি ষষ্ঠ জনশুমারি ও গৃহগণনা ২০২২। বাংলাদেশের খেলাধুলা বাংলাদেশের কৃষ্টি ও সংস্কৃতি বাংলার সংগীত
বাংলাদেশের জাতিগোষ্ঠী ও উপজাতি সংক্রান্ত বিষয়াদি ষষ্ঠ জনশুমারি ও গৃহগণনা ২০২২। বাংলাদেশের খেলাধুলা বাংলাদেশের কৃষ্টি ও সংস্কৃতি বাংলার সংগীত
পরীক্ষা শুরুঃ ৩য় ব্যাচ শুরু ৫ নভেম্বর, ২০২৫।
রুটিন দেখুন
পরীক্ষা – ৩৮
কোর্স নামঃ
প্রাইমারি প্রধান শিক্ষক নিয়োগ প্রস্তুতি (২য় ব্যাচ)
টপিকসঃ
বাংলা: বানান
ইংরেজি: Literary Terms
গণিত: স্থানাঙ্ক জ্যামিতি, সমস্যা সমাধান
সাধারণ জ্ঞান: শিল্প-বাণিজ্য
ইংরেজি: Literary Terms
গণিত: স্থানাঙ্ক জ্যামিতি, সমস্যা সমাধান
সাধারণ জ্ঞান: শিল্প-বাণিজ্য
৫ ফেব্রুয়ারি থেকে শুরু।
রুটিন দেখুন
Practice More Questions on Our App!
Download our app for free and access thousands of MCQ questions with detailed solutions