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)।
অ্যাপ/ওয়েবসাইটে রুটিনভিত্তিক নিয়মিত লাইভ পরীক্ষা হচ্ছে।
Exam - 86
কোর্স নামঃ
ব্যাংক নিয়োগ প্রস্তুতি'র লং কোর্স (২৭৬ দিন)
টপিকসঃ
General Knowledge
পরিবেশ সম্মেলন: স্টকহোম সামিট, ধরিত্রী সম্মেলনসমূহ, COP সমূহ, ব্ল্যাক সেপ্টেম্বর।
চুক্তিসমূহ: প্যারিস চুক্তিসমূহ, ডেটন চুক্তি, ক্যাম্প ডেভিড চুক্তি এবং বিভিন্ন অস্ত্র চুক্তি, জেনেভা কনভেনশন।
পরিবেশ সম্মেলন: স্টকহোম সামিট, ধরিত্রী সম্মেলনসমূহ, COP সমূহ, ব্ল্যাক সেপ্টেম্বর।
চুক্তিসমূহ: প্যারিস চুক্তিসমূহ, ডেটন চুক্তি, ক্যাম্প ডেভিড চুক্তি এবং বিভিন্ন অস্ত্র চুক্তি, জেনেভা কনভেনশন।
এই রুটিনের সাথে ৩ বার ভোকাবুলারি রিভিশন।
রুটিন দেখুন
পরীক্ষা – ৩৫
কোর্স নামঃ
১৯ তম শিক্ষক নিবন্ধন - লেকচারশীট ভিত্তিক।
টপিকসঃ
English
Number, Gender
Number, Gender
পরীক্ষা শুরুঃ (৫ম ব্যাচ) শুরু ৫ মে, ২০২৬।
রুটিন দেখুন
Practice More Questions on Our App!
Download our app for free and access thousands of MCQ questions with detailed solutions