মডিউল ১৭-১ঃ What is BST

এই module এ আমরা Binary Search Tree এর সম্পর্কে জানবো। সহজ ভাষায় BST হলো Binary Search করার জন্য সাজানো Tree. আমরা ইতোমধ্যে জেনেছি binary search করার জন্য data কে অবশ্যই sorted হতে হবে। এই BST তে আমরা value গুলো ছোট থেকে বড় একটা sorting maintain করে রাখবো। এখানে root এর left node গুলো হবে root থেকে ছোট আর right node গুলো হবে বড়।

উপরের binary tree টা দেখুন এখানে প্রতিটি root or parent node দেখুন। Left side এর node গুলো উপরের value গুলো থেকে ছোট আর right side এর গুলো বড়। এখানে যদি আমাদের x=12 খুঁজতে হয় তাহলে কিভাবে খুঁজা যায়? প্রথমে দেখবো root 10 এর সাথে match করে কিনা। left or right এর মধ্যে দেখবো right থেকে ছোট আর left থেকে বড় কিনা। 10 থেকে বড় আর 30 থেকে ছোট। আর root থেকেও ছোট তাই আমরা left subtree তে যাবো। তারপর একইভাবে 10 এর থেকে 12 বড় তাই 15 এর দিকে যেতে হবে।

15 তে এসে আমরা left এ গেলেই 12 পেয়ে গেলাম। এটাই হলো binary search tree এর সুবিধা। কম operation চালাতে হয় ও Time complexityও কম।