10. Binary Search Tree (BST)
📘 কনসেপ্ট (থিওরি)
একটি বাইনারি সার্চ ট্রি (Binary Search Tree বা BST) হলো একটি বিশেষ ধরণের বাইনারি ট্রি।
BST এর বৈশিষ্ট্য:
- একটি নোডের বাম সাবট্রিতে (subtree) কেবল সেই নোডগুলো থাকে যাদের মান ওই নোডের মানের চেয়ে কম (LESS)।
- একটি নোডের ডান সাবট্রিতে কেবল সেই নোডগুলো থাকে যাদের মান ওই নোডের মানের চেয়ে বেশি (GREATER)।
এই বৈশিষ্ট্যটি দ্রুত খোঁজা, ঢোকানো এবং মুছে ফেলার অনুমতি দেয়, যার গড় সময় O(log n)।
💡 উদাহরণ
BST এর গঠন:
10
/ \
5 15
১৫ খোঁজা:
১. রুট (১০) থেকে শুরু করুন।
২. ১৫ > ১০, তাই ডানদিকে যান।
৩. ১৫ পাওয়া গেছে!
🎯 আপনার কাজ (প্র্যাকটিস)
একটি রুট নোড (মান: 10) দেওয়া আছে এবং আপনি 8 ঢোকাতে চান। 8 কোন দিকে (
left বা right) যাবে?main.dsa
Loading...
OUTPUT
Run your code to see the output here...