যে tree সংখ্যাগুলো সাজিয়ে রাখে, যাতে left বা right-এ গিয়ে যেকোনো সংখ্যা খুঁজে পাওয়া যায়।
মূল ধারণা (tree আকারে সাজানো phone book)
Binary search tree (BST) প্রতিটি node-এ একটি নিয়ম মানে: left subtree-র সবকিছু ছোট, right subtree-র সবকিছু বড়। এটা আসলে binary search-কে একটা আকার দেওয়া: প্রতিটি node-এ আপনি জিজ্ঞেস করেন "আমার সংখ্যাটা কি ছোট, না বড়?" এবং বাকিটার অর্ধেক বাদ দেন।
Search: root থেকে শুরু করুন। সমান? পেয়ে গেছেন। ছোট? left-এ যান। বড়? right-এ যান। খালি জায়গা (nil) পেলে বুঝবেন সংখ্যাটা নেই।
Insert: একই পথে হাঁটুন। যে খালি জায়গায় পৌঁছান, নতুন মানটা সেখানেই বসবে।
Tree balanced থাকলে প্রতিটি ধাপে সমস্যা অর্ধেক হয়, তাই lookup দ্রুত হয়। কিন্তু insert-এর order গুরুত্বপূর্ণ: আগে থেকে sorted সংখ্যা insert করে দেখুন tree-র আকার কী হয়।
একই সংখ্যাগুলো 30, 20, 40, 10, 50 order-এ insert করুন। আকার আর search-এর খরচ তুলনা করুন।
55-এর মতো এমন মান খুঁজুন যা tree-তে নেই। search কোথায় শেষ হয়?
30, 30-এর মতো duplicate insert করুন। এই code সেটাকে কীভাবে সামলায়?
সাধারণ ভুল
শুধু সরাসরি child দেখা। নিয়মটা পুরো subtree-র জন্য, শুধু পরের level-এর জন্য নয়।
nil case ভুলে যাওয়া।if root == nil ছাড়া recursion tree-র বাইরে পৌঁছে যায় এবং nil pointer-এ panic করে।
ধরে নেওয়া যে এটা সবসময় দ্রুত। Sorted order-এ insert করলে tree একটা লম্বা chain-এর মতো হয়ে যায়, আর প্রতিটি search সেই chain ধরে ধীরে নামে।
duplicate-এর নিয়ম অস্পষ্ট রাখা। আগেই ঠিক করে নিন duplicate ignore হবে, count হবে, নাকি এক পাশে যাবে। এই page-এ ignore করা হয়।
Complexity, সহজ ভাষায়: search বা insert root থেকে একটা path ধরে যায়, তাই খরচ প্রায় tree-র height-এর সমান। 1,000,000 মানের balanced tree-র height প্রায় 20 (O(log n)); chain-এর মতো tree-র height n (O(n))।